Skip to content

Instantly share code, notes, and snippets.

@XiaoxiaoLi
Last active September 29, 2015 16:15
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save XiaoxiaoLi/fb712533a48d73b4415f to your computer and use it in GitHub Desktop.
Save XiaoxiaoLi/fb712533a48d73b4415f to your computer and use it in GitHub Desktop.
#CC150 #CC150-chap3 3.5 Implement a MyQueue class which implements a queue using two stacks.
package chap3;
import java.util.EmptyStackException;
import java.util.Stack;
//3.5 Implement a MyQueue class which implements a queue using two stacks.
//Use one stack as the 'push' stack and another as the 'pop' stack. Push all elements to the push stack, and pop from the pop stack. When the pop stack is empty, push all elements from the push stack to the pop stack
//Time: POP: amortized O(1), worst case O(n), Push is O(1)
//Space: O(n)
public class MyQueue<T> {
private Stack<T> pushStack = new Stack<T>();
private Stack<T> popStack = new Stack<T>();
public void enqueue(T item) {
pushStack.push(item);
}
public T dequeue() {
if (popStack.empty()) {
if (pushStack.empty()) {
throw new EmptyStackException();
// Or return null depending on the interviewer
} else {
// Push every element in the push stack into the pop stack
while (!pushStack.empty()) {
popStack.push(pushStack.pop());
}
}
}
return popStack.pop();
}
public static void main(String[] args) {
MyQueue<Integer> queue = new MyQueue<Integer>();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment