Problem Statement:
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).
Implement the MyStack class:
void push(int x)Pushes element x to the top of the stack.int pop()Removes the element on the top of the stack and returns it..int top()Returns the element on the top of the stack.boolean empty()Returns true if the stack is empty,falseotherwise.
Notes
- You must use only standard operations of a queue, which means that only
push to back,peek/pop from front,sizeandis emptyoperations are valid. - Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.
Examples
Example 1:
Input:[“MyStack”, “push”, “push”, “top”, “pop”, “empty”] [[], [1], [2], [], [], []]
Output:[null, null, null, 2, 2, false]
Explanation MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // return 2 myStack.pop(); // return 2 myStack.empty(); // return False
Constraints:
- 1 <= x <= 9
- At most
100calls will be made topush,pop,top, andempty. - All the calls to
popandtopare valid.
Follow-up: Can you implement the stack using only one queue?
Approach
- Initialize Two Queues.
- Just add the element to q1. (q1.push(x))
- Remove the last pushed element (i.e., rear of q1).
- Similar to pop(), but instead of removing the last element.
- Check if q1 is empty.
Visualisation:
Time Complexity:
push → O(1)
pop/top → O(n)
empty → O(1)
Space Complexity:
Space Complexity = O(1)
Dry Run
Input:
Operations: push(1) push(2) push(3) top() pop() top() empty()
State Transitions:
After push(1):
q1 = [1]
q2 = []
After push(2):
q1 = [1, 2]
q2 = []
After push(3):
q1 = [1, 2, 3]
q2 = []
top():
Move q1 → q2 (except last):
q2 = [1, 2]
q1 = [3]
Peek front = 3, push it to q2
q2 = [1, 2, 3]
Swap q1 and q2
q1 = [1, 2, 3]
q2 = []
→ Returns: 3
pop():
Move q1 → q2 (except last):
q2 = [1, 2]
q1 = [3]
Remove last from q1: 3
Swap q1 and q2
q1 = [1, 2]
q2 = []
→ Returns: 3
top():
Move q1 → q2 (except last):
q2 = [1]
q1 = [2]
Peek front = 2, push it to q2
q2 = [1, 2]
Swap q1 and q2
q1 = [1, 2]
q2 = []
→ Returns: 2
empty():
q1 = [1, 2] → Not empty
→ Returns: false
Final State: q1 = [1, 2], Stack (top to bottom): [2, 1]
var MyStack = function() {
this.q1 = [];
this.q2 = [];
};
MyStack.prototype.push = function(x) {
this.q1.push(x);
};
MyStack.prototype.pop = function() {
let n = this.q1.length;
for (let i = 0; i < n - 1; i++) {
this.q2.push(this.q1.shift());
}
let ans = this.q1.shift();
let temp = this.q1;
this.q1 = this.q2;
this.q2 = temp;
return ans;
};
MyStack.prototype.top = function() {
let n = this.q1.length;
for (let i = 0; i < n - 1; i++) {
this.q2.push(this.q1.shift());
}
let front = this.q1[0];
this.q2.push(this.q1.shift());
let temp = this.q1;
this.q1 = this.q2;
this.q2 = temp;
return front;
};
MyStack.prototype.empty = function() {
return this.q1.length === 0;
};
from collections import deque
class MyStack:
def __init__(self):
self.q1 = deque()
self.q2 = deque()
def push(self, x: int) -> None:
self.q1.append(x)
def pop(self) -> int:
while len(self.q1) > 1:
self.q2.append(self.q1.popleft())
ans = self.q1.popleft()
self.q1, self.q2 = self.q2, self.q1
return ans
def top(self) -> int:
while len(self.q1) > 1:
self.q2.append(self.q1.popleft())
front = self.q1.popleft()
self.q2.append(front)
self.q1, self.q2 = self.q2, self.q1
return front
def empty(self) -> bool:
return len(self.q1) == 0
class MyStack {
Queue q1 = new LinkedList<>();
Queue q2 = new LinkedList<>();
public MyStack() {}
public void push(int x) {
q1.offer(x);
}
public int pop() {
while (q1.size() > 1) {
q2.offer(q1.poll());
}
int ans = q1.poll();
Queue temp = q1;
q1 = q2;
q2 = temp;
return ans;
}
public int top() {
while (q1.size() > 1) {
q2.offer(q1.poll());
}
int front = q1.poll();
q2.offer(front);
Queue temp = q1;
q1 = q2;
q2 = temp;
return front;
}
public boolean empty() {
return q1.isEmpty();
}
}
#include <queue>
using namespace std;
class MyStack {
queue q1, q2;
public:
MyStack() {}
void push(int x) {
q1.push(x);
}
int pop() {
while (q1.size() > 1) {
q2.push(q1.front());
q1.pop();
}
int ans = q1.front(); q1.pop();
swap(q1, q2);
return ans;
}
int top() {
while (q1.size() > 1) {
q2.push(q1.front());
q1.pop();
}
int front = q1.front(); q1.pop();
q2.push(front);
swap(q1, q2);
return front;
}
bool empty() {
return q1.empty();
}
};
#include <stdio.h>
#include <stdbool.h>
#define MAX 1000
typedef struct {
int q1[MAX];
int q2[MAX];
int front1, rear1;
int front2, rear2;
} MyStack;
MyStack* myStackCreate() {
MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
stack->front1 = stack->rear1 = 0;
stack->front2 = stack->rear2 = 0;
return stack;
}
void push(MyStack* obj, int x) {
obj->q1[obj->rear1++] = x;
}
int pop(MyStack* obj) {
while (obj->rear1 - obj->front1 > 1) {
obj->q2[obj->rear2++] = obj->q1[obj->front1++];
}
int val = obj->q1[obj->front1++];
for (int i = 0; i < obj->rear2; i++) {
obj->q1[i] = obj->q2[i];
}
obj->rear1 = obj->rear2;
obj->front1 = obj->front2 = obj->rear2 = 0;
return val;
}
int top(MyStack* obj) {
while (obj->rear1 - obj->front1 > 1) {
obj->q2[obj->rear2++] = obj->q1[obj->front1++];
}
int val = obj->q1[obj->front1++];
obj->q2[obj->rear2++] = val;
for (int i = 0; i < obj->rear2; i++) {
obj->q1[i] = obj->q2[i];
}
obj->rear1 = obj->rear2;
obj->front1 = obj->front2 = obj->rear2 = 0;
return val;
}
bool empty(MyStack* obj) {
return obj->rear1 == obj->front1;
}
void myStackFree(MyStack* obj) {
free(obj);
}
using System.Collections.Generic;
public class MyStack {
private Queue q1 = new Queue();
private Queue q2 = new Queue();
public MyStack() {}
public void Push(int x) {
q1.Enqueue(x);
}
public int Pop() {
while (q1.Count > 1) {
q2.Enqueue(q1.Dequeue());
}
int val = q1.Dequeue();
var temp = q1;
q1 = q2;
q2 = temp;
return val;
}
public int Top() {
while (q1.Count > 1) {
q2.Enqueue(q1.Dequeue());
}
int front = q1.Dequeue();
q2.Enqueue(front);
var temp = q1;
q1 = q2;
q2 = temp;
return front;
}
public bool Empty() {
return q1.Count == 0;
}
}
