Skip to content

Instantly share code, notes, and snippets.

@chouclee
Created June 28, 2014 08:56
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 chouclee/9fb80a96222d8b8f9d53 to your computer and use it in GitHub Desktop.
Save chouclee/9fb80a96222d8b8f9d53 to your computer and use it in GitHub Desktop.
[CC150][3.5] Implement a MyQueue class which implements a queue using two stacks
import java.util.Stack;
public class MyQueue<T> {
private Stack<T> pushStack;
private Stack<T> popStack;
public MyQueue() {
pushStack = new Stack<T>();
popStack = new Stack<T>();
}
public void enqueue(T item) { // push element into pushStack
pushStack.push(item); // push() : O(1)
}
public T dequeue() { // if popStack is not empty, pop() from popStack
if (popStack.isEmpty()) { // else, push all elements in pushStack into popStack, then pop one item
if (pushStack.isEmpty()) // pop() : average O(1)
return null;
else {
while (!pushStack.isEmpty())
popStack.add(pushStack.pop());
}
}
return popStack.pop();
}
public static void main(String[] args) {
// TODO Auto-generated method stub
MyQueue<Integer> test = new MyQueue<Integer>();
for (int i = 0; i < 10; i++)
test.enqueue(i);
for (int i = 0; i < 5; i++)
System.out.println(test.dequeue());
for (int i = 10; i < 15; i++)
test.enqueue(i);
for (int i = 0; i < 10; i++)
System.out.println(test.dequeue());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment