Implement Stack using Queues

Implement a stack using two queues with O(1) amortized time complexity for all operations.

Language Selection

Choose your preferred programming language

Showing: Python

Implement Stack using Queues

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 onto the stack
int pop() Removes the element on top of the stack and returns it
int top() Returns the element on top of the stack
boolean empty() Returns true if the stack is empty, false otherwise

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 100 calls will be made to push, pop, top, and empty
All the calls to pop and top are valid

Approach 1: Two Queues with Amortized O(1) (Optimal)

Algorithm

Use two queues: one for input and one for output. Transfer elements from input to output only when output is empty.

Steps:

Use inputQueue for push operations
Use outputQueue for pop and top operations
When output queue is empty, transfer all elements from input to output
This ensures amortized O(1) time complexity

Implementation

Python:

from collections import deque

class MyStack:
    """
    Stack implementation using two queues
    Time: O(1) amortized for all operations
    Space: O(n)
    """
    
    def __init__(self):
        self.input_queue = deque()
        self.output_queue = deque()
    
    def push(self, x: int) -> None:
        """Push element x onto stack"""
        self.input_queue.append(x)
    
    def pop(self) -> int:
        """Remove element on top of stack and return it"""
        self._transfer_if_needed()
        return self.output_queue.popleft()
    
    def top(self) -> int:
        """Return element on top of stack"""
        self._transfer_if_needed()
        return self.output_queue[0]
    
    def empty(self) -> bool:
        """Return true if stack is empty"""
        return len(self.input_queue) == 0 and len(self.output_queue) == 0
    
    def _transfer_if_needed(self):
        """Transfer elements from input to output queue if needed"""
        if not self.output_queue:
            while self.input_queue:
                self.output_queue.append(self.input_queue.popleft())

Java:

import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    /**
     * Stack implementation using two queues
     * Time: O(1) amortized for all operations
     * Space: O(n)
     */
    
    private Queue<Integer> inputQueue;
    private Queue<Integer> outputQueue;
    
    public MyStack() {
        inputQueue = new LinkedList<>();
        outputQueue = new LinkedList<>();
    }
    
    public void push(int x) {
        inputQueue.offer(x);
    }
    
    public int pop() {
        transferIfNeeded();
        return outputQueue.poll();
    }
    
    public int top() {
        transferIfNeeded();
        return outputQueue.peek();
    }
    
    public boolean empty() {
        return inputQueue.isEmpty() && outputQueue.isEmpty();
    }
    
    private void transferIfNeeded() {
        if (outputQueue.isEmpty()) {
            while (!inputQueue.isEmpty()) {
                outputQueue.offer(inputQueue.poll());
            }
        }
    }
}

Go:

type MyStack struct {
    inputQueue  []int
    outputQueue []int
}

// Constructor - Initialize stack
func Constructor() MyStack {
    return MyStack{
        inputQueue:  make([]int, 0),
        outputQueue: make([]int, 0),
    }
}

// Push - Push element x onto stack
func (this *MyStack) Push(x int) {
    this.inputQueue = append(this.inputQueue, x)
}

// Pop - Remove element on top of stack and return it
func (this *MyStack) Pop() int {
    this.transferIfNeeded()
    top := this.outputQueue[0]
    this.outputQueue = this.outputQueue[1:]
    return top
}

// Top - Return element on top of stack
func (this *MyStack) Top() int {
    this.transferIfNeeded()
    return this.outputQueue[0]
}

// Empty - Return true if stack is empty
func (this *MyStack) Empty() bool {
    return len(this.inputQueue) == 0 && len(this.outputQueue) == 0
}

// transferIfNeeded - Transfer elements from input to output queue if needed
func (this *MyStack) transferIfNeeded() {
    if len(this.outputQueue) == 0 {
        for len(this.inputQueue) > 0 {
            top := this.inputQueue[0]
            this.inputQueue = this.inputQueue[1:]
            this.outputQueue = append(this.outputQueue, top)
        }
    }
}

JavaScript:

/**
 * Stack implementation using two queues
 * Time: O(1) amortized for all operations
 * Space: O(n)
 */
class MyStack {
    constructor() {
        this.inputQueue = [];
        this.outputQueue = [];
    }
    
    push(x) {
        this.inputQueue.push(x);
    }
    
    pop() {
        this.transferIfNeeded();
        return this.outputQueue.shift();
    }
    
    top() {
        this.transferIfNeeded();
        return this.outputQueue[0];
    }
    
    empty() {
        return this.inputQueue.length === 0 && this.outputQueue.length === 0;
    }
    
    transferIfNeeded() {
        if (this.outputQueue.length === 0) {
            while (this.inputQueue.length > 0) {
                this.outputQueue.push(this.inputQueue.shift());
            }
        }
    }
}

C#:

using System.Collections.Generic;

public class MyStack {
    /// <summary>
    /// Stack implementation using two queues
    /// Time: O(1) amortized for all operations
    /// Space: O(n)
    /// </summary>
    
    private Queue<int> inputQueue;
    private Queue<int> outputQueue;
    
    public MyStack() {
        inputQueue = new Queue<int>();
        outputQueue = new Queue<int>();
    }
    
    public void Push(int x) {
        inputQueue.Enqueue(x);
    }
    
    public int Pop() {
        TransferIfNeeded();
        return outputQueue.Dequeue();
    }
    
    public int Top() {
        TransferIfNeeded();
        return outputQueue.Peek();
    }
    
    public bool Empty() {
        return inputQueue.Count == 0 && outputQueue.Count == 0;
    }
    
    private void TransferIfNeeded() {
        if (outputQueue.Count == 0) {
            while (inputQueue.Count > 0) {
                outputQueue.Enqueue(inputQueue.Dequeue());
            }
        }
    }
}

Complexity Analysis

Time Complexity: O(1) amortized for all operations
Space Complexity: O(n) for the two queues

Key Insights

Two Queue Approach: Use input queue for push, output queue for pop/top
Amortized Analysis: Transfer elements only when output queue is empty
Lazy Transfer: Defer expensive operations until necessary
LIFO Behavior: Maintain last-in-first-out order using queue operations
Space Efficiency: Use two queues to simulate stack behavior

Edge Cases

Empty Stack: All operations on empty stack
Single Element: Stack with one element
Multiple Operations: Mix of push, pop, top operations
Large Input: Many consecutive push operations
Alternating Operations: Push-pop-push-pop pattern

Follow-up Questions

Implement Queue using Stacks: How would you implement a queue using stacks?
Thread Safety: How would you make it thread-safe?
Memory Management: How would you optimize memory usage?
Performance: How would you optimize for high-frequency operations?

Common Mistakes

Transfer Timing: Not transferring elements at the right time
Queue Management: Incorrect queue operations
Empty Check: Not properly checking for empty stack
Order Maintenance: Not maintaining LIFO order correctly

Interview Tips

Clarify Requirements: Ask about time complexity requirements
Discuss Approaches: Mention both amortized and simple approaches
Handle Edge Cases: Discuss empty stack and single element scenarios
Explain Algorithm: Walk through the two-queue approach
Consider Optimizations: Discuss space and time optimizations