Implement Queue using Stacks
Implement a queue using two stacks. A queue is a First-In-First-Out (FIFO) data structure, meaning the first element that is added will be the first one to be removed. You can use two stacks to implement a queue.
Constraints:
- You must use two stacks to implement the queue.
- You cannot use any other data structures such as arrays or linked lists.
Examples:
Input: MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); queue.pop(); queue.empty()
Output: [null, null, 1, 1, false]
Explanation: We create a new queue and push the elements 1 and 2. Then we peek at the front element which is 1. We pop the front element which is also 1. Finally, we check if the queue is empty which is false because there is still one element left.
Solutions
Two Stacks Approach
We use two stacks, stack1 and stack2. We push elements onto stack1. When we need to pop or peek at the front element, we check if stack2 is empty. If it is, we pop all elements from stack1 and push them onto stack2. Then we can pop or peek at the top element of stack2 which is the front element of the queue.
class MyQueue {
private Stack<Integer> stack1;
private Stack<Integer> stack2;
public MyQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void push(int x) {
stack1.push(x);
}
public int pop() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.pop();
}
public int peek() {
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
return stack2.peek();
}
public boolean empty() {
return stack1.isEmpty() && stack2.isEmpty();
}
}Follow-up:
How would you implement a stack using two queues?
