Implementing Queue using
Stack
TOPICS
Introduction
Algorithm Pseudocode
Example
Code
Time and space complexity
Advantages and disadvantages
Interview Questions
Introduction
Problem Statement:
The task is to implement a Queue (FIFO: First In, First Out) using two Stacks (LIFO: Last In, First Out).
The queue should support four operations: push(x) to insert an element, pop() to remove the front
element, peek() to view the front element, and empty() to check if the queue is empty. The main
challenge is simulating queue behavior using stack operations.
Explanation
● Queue → FIFO order (remove first inserted element).
● Stack → LIFO order (remove last inserted element).
● To simulate a queue:
○ Use two stacks:
■ stackIn for enqueue operations.
■ stackOut for dequeue operations.
○ Transfer elements from stackIn to stackOut when needed.
Input/Output Example
Example 1
Input:
push(1), push(2), peek(), pop(), empty()
Output:
peek() → 1
pop() → 1
empty() → false
Example 2
Input:
push(10), push(20), push(30), pop(), peek()
Output:
pop() → 10
peek() → 20
stackIn for enqueue operations.
stackOut for dequeue operations.
Transfer elements from stackIn to stackOut when needed.
Pseudocode:
Initialize stackIn = empty
Initialize stackOut = empty
function push(x):
[Link](x)
function pop():
if stackOut is empty:
while stackIn not empty:
[Link]([Link]())
return [Link]()
function peek():
if stackOut is empty:
while stackIn not empty:
[Link]([Link]())
return [Link]()
function empty():
return [Link]() AND
[Link]()
Algorithm Explanation
1. Push Operation → Always push into stackIn.
2. Pop Operation → If stackOut is empty, transfer all elements from stackIn to stackOut.
○ Then pop from stackOut.
3. Peek Operation → Same as pop, but return top instead of removing it.
4. Empty Operation → True if both stacks are empty
Java Code:
import [Link].*; public int peek() {
if ([Link]()) {
class MyQueue { while (![Link]()) {
Stack<Integer> stackIn = new Stack<>(); [Link]([Link]());
Stack<Integer> stackOut = new Stack<>(); }
}
public void push(int x) { return [Link]();
[Link](x); }
}
public boolean empty() {
public int pop() { return [Link]() &&
if ([Link]()) { [Link]();
while (![Link]()) { }
[Link]([Link]()); public static void main(String[] args) {
} MyQueue q = new MyQueue();
}
return [Link](); [Link](1);
} [Link](2);
[Link]([Link]());
[Link]([Link]());
Java Code:
[Link]([Link]()); // false
[Link](10);
[Link](20);
[Link](30);
[Link]([Link]());
[Link]([Link]());
}
}
Time Complexity
● Push: O(1) since we always push directly into stackIn.
● Pop/Peek: Amortized O(1) because each element is moved from stackIn → stackOut at most once.
● Worst-case pop: O(n) occurs only when transferring all elements between stacks.
Space Complexity
● O(n) because, in the worst case, all elements may be stored across the two stacks.
● Even though we use two stacks, the total storage is still proportional to the number of elements (n).
Advantages
1. Efficient amortized O(1) operations.
2. Simple use of existing stack data structure.
3. Demonstrates queue via stack transformation (good for interviews).
Disadvantages
1. Worst-case O(n) for pop/peek (during transfer).
2. Requires extra space (two stacks).
3. Slightly more complex implementation compared to direct queue.
QUESTION 1
Why do we need two stacks instead of one?
Answer:
1. One stack alone gives LIFO.
2. Two stacks reverse order → FIFO behavior.
QUESTION 2
What is the amortized time complexity of pop?
Answer:
1. Amortized O(1).
2. Because each element is transferred at most once.
QUESTION 3
How to optimize space if memory is limited?
Answer:
1. Use a linked list to implement the queue directly.
2. Or reuse the same stack carefully, but with complex logic.
THANK YOU
+91 78150 95095 codemithra@[Link] [Link]