232 Implement Queue using Stacks – Easy
Problem:
Implement the following operations of a queue using stacks.
push(x) — Push element x to the back of queue. pop() — Removes the element from in front of queue. peek() — Get the front element. empty() — Return whether the queue is empty. Notes: You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid. Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack. You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
Thoughts:
This is very similar to the previous problem Implement Stack using Queues. The solution below is making push expensive.
Solutions:
class MyQueue {
Stack<Integer> data = new Stack<Integer>();
// Push element x to the back of queue.
public void push(int x) {
Stack<Integer> reverse = new Stack<Integer>();
while (data.size() > 0) {
reverse.push(data.pop());
}
data.push(x);
while (reverse.size() > 0) {
data.push(reverse.pop());
}
}
// Removes the element from in front of queue.
public void pop() {
data.pop();
}
// Get the front element.
public int peek() {
return data.peek();
}
// Return whether the queue is empty.
public boolean empty() {
return data.size() == 0;
}
}