Problem Statement:
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).
Implement the MyQueue class:
void push(int x)Pushes element x to the back of the queue.int pop()Removes the element from the front of the queue and returns it.int peek()Returns the element at the front of the queue.boolean empty()Returnstrueif the queue is empty,falseotherwise.
Notes
- You must use only standard operations of a stack, which means only
push to top,peek/pop from top,sizeandis emptyoperations are valid. - Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.
Examples
Example 1:
Input:[“MyQueue”, “push”, “push”, “top”, “pop”, “empty”] [[], [1], [2], [], [], []]
Output:[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2]
(leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
Constraints:
1 <= x <= 9- At most
100calls will be made topush,pop,peek, andempty. - All the calls to
popandpeekare valid.
Follow-up:
Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.
Approach: Using Two Stacks (s1 & s2)
- Use two stacks, s1 and s2.
- For Push, push onto s1.
- For pop, transfer elements from s1 to s2 if s2 is empty, then pop from s2.
- For peek, transfer elements from s1 to s2 if s2 is empty, then return top of s2.
Visualisation:
Time Complexity:
push → O(1)
pop → O(n)
peek → O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input:
Operations: push(1) push(2) push(3) peek() pop() peek() empty()
State Transitions:
After push(1): s1 = [1] s2 = [] After push(2): s1 = [1, 2] s2 = [] After push(3): s1 = [1, 2, 3] s2 = [] peek(): → s2 is empty → move all from s1 to s2 s1.pop() = 3 → s2.push(3) s1.pop() = 2 → s2.push(2) s1.pop() = 1 → s2.push(1) Now: s1 = [], s2 = [3, 2, 1] Top of s2 = 1 → Returns: 1 pop(): → s2 not empty → pop from s2 s2.pop() = 1 Now: s1 = [], s2 = [3, 2] → Returns: 1 peek(): → s2 not empty Top of s2 = 2 → Returns: 2 empty(): s1 = [], s2 = [3, 2] → Not empty → Returns: false
Final State: s1 = [], s2 = [3, 2] (top to bottom)
var MyQueue = function() {
this.s1 = [];
this.s2 = [];
};
MyQueue.prototype.push = function(x) {
this.s1.push(x);
};
MyQueue.prototype.pop = function() {
if(this.s2.length === 0) {
while(this.s1.length) {
this.s2.push(this.s1.pop());
}
}
return this.s2.pop();
};
MyQueue.prototype.peek = function() {
if(this.s2.length === 0) {
while(this.s1.length) {
this.s2.push(this.s1.pop());
}
}
return this.s2[this.s2.length-1];
};
MyQueue.prototype.empty = function() {
return this.s1.length === 0 && this.s2.length === 0;
};
class MyQueue:
def __init__(self):
self.s1 = []
self.s2 = []
def push(self, x: int) -> None:
self.s1.append(x)
def pop(self) -> int:
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2.pop()
def peek(self) -> int:
if not self.s2:
while self.s1:
self.s2.append(self.s1.pop())
return self.s2[-1]
def empty(self) -> bool:
return not self.s1 and not self.s2
import java.util.Stack;
class MyQueue {
Stack s1 = new Stack<>();
Stack s2 = new Stack<>();
public void push(int x) {
s1.push(x);
}
public int pop() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.pop();
}
public int peek() {
if (s2.isEmpty()) {
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
}
return s2.peek();
}
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
#include <stack>
class MyQueue {
std::stack s1, s2;
public:
void push(int x) {
s1.push(x);
}
int pop() {
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}
int val = s2.top();
s2.pop();
return val;
}
int peek() {
if (s2.empty()) {
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
}
return s2.top();
}
bool empty() {
return s1.empty() && s2.empty();
}
};
#include <stdio.h>
#include <stdbool.h>
#define MAX 1000
typedef struct {
int s1[MAX], s2[MAX];
int top1, top2;
} MyQueue;
void initQueue(MyQueue* q) {
q->top1 = -1;
q->top2 = -1;
}
void push(MyQueue* q, int x) {
q->s1[++(q->top1)] = x;
}
int pop(MyQueue* q) {
if (q->top2 == -1) {
while (q->top1 >= 0) {
q->s2[++(q->top2)] = q->s1[(q->top1)--];
}
}
return q->s2[(q->top2)--];
}
int peek(MyQueue* q) {
if (q->top2 == -1) {
while (q->top1 >= 0) {
q->s2[++(q->top2)] = q->s1[(q->top1)--];
}
}
return q->s2[q->top2];
}
bool empty(MyQueue* q) {
return q->top1 == -1 && q->top2 == -1;
}
using System.Collections.Generic;
public class MyQueue {
private Stack s1 = new Stack();
private Stack s2 = new Stack();
public void Push(int x) {
s1.Push(x);
}
public int Pop() {
if (s2.Count == 0) {
while (s1.Count > 0) {
s2.Push(s1.Pop());
}
}
return s2.Pop();
}
public int Peek() {
if (s2.Count == 0) {
while (s1.Count > 0) {
s2.Push(s1.Pop());
}
}
return s2.Peek();
}
public bool Empty() {
return s1.Count == 0 && s2.Count == 0;
}
}
