5 Best Ways to Implement a Stack Using One Queue in Python

💡 Problem Formulation: When it comes to implementing a stack (a LIFO – last in, first out – data structure), it is typically done using an array or linked list. However, there is an interesting challenge in trying to implement a stack using just a single queue (a FIFO – first in, first out – data structure). The goal is to efficiently manage stack operations such as push and pop using only the operations provided by a queue. This article explores several methods to achieve this unconventional setup, demonstrating how we can manipulate the queue to exhibit stack-like behavior.

Method 1: Using Reversal

This method involves reversing the order of queue elements every time a push operation is performed, thereby maintaining the last inserted element at the front of the queue. With this, the pop operation simply dequeues from the front, mimicking a stack’s pop behavior.

Here’s an example:

from collections import deque

class StackUsingQueue:
    def __init__(self):
        self.queue = deque()

    def push(self, x):
        self.queue.append(x)
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

    def pop(self):
        return self.queue.popleft() if self.queue else None

    def top(self):
        return self.queue[0] if self.queue else None

# Usage
stack = StackUsingQueue()
stack.push(1)
stack.push(2)
stack.pop()

The output for the provided code:

This snippet initiates a stack instance, pushes two elements into it, and then pops the top element which would be ‘2’, reflecting the last-in-first-out (LIFO) behavior of a stack. The reversal is handled internally within the push method.

Method 2: Recursive Popping

In this approach, we utilize the recursive nature of function calls to remove all elements from the queue until we retrieve the last added element (stack’s top). Then reconstruct the queue (stack) during the unwind phase of the recursion.

Here’s an example:

from collections import deque

class StackUsingQueue:
    def __init__(self):
        self.queue = deque()
        
    def push(self, x):
        self.queue.append(x)

    def pop(self):
        if len(self.queue) == 0:
            return None
        if len(self.queue) == 1:
            return self.queue.popleft()
        temp = self.queue.popleft()
        res = self.pop()
        self.queue.append(temp)
        return res

# Usage
stack = StackUsingQueue()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())

The output for the provided code:

This code initializes a stack instance and pushes three integers, subsequently popping the top element using recursion. The pop method in this snippet cleverly reconstructs the queue after retrieving the last element.

Method 3: Iterative Size Tracking

This method pushes elements to the queue normally but keeps track of the current size. During a pop, we dequeue elements and re-enqueue them until we reach the last element, which we then return.

Here’s an example:

from collections import deque

class StackUsingQueue:
    def __init__(self):
        self.queue = deque()
        self.size = 0

    def push(self, x):
        self.queue.append(x)
        self.size += 1

    def pop(self):
        if self.size == 0:
            return None
        while self.size > 1:
            self.queue.append(self.queue.popleft())
            self.size -= 1
        return self.queue.popleft()

# Usage
stack = StackUsingQueue()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())

The output for the provided code:

The StackUsingQueue class maintains the size of the stack to identify the last element. The pop operation rotates elements within the queue and decreases the size until it retrieves the last element to simulate a stack’s pop.

Method 4: Counted Iterative Pop

Similar to method 3, this strategy also uses rotation, but instead of tracking the size of the stack, it counts the number of rotations needed to reach the stack’s top based on the queue’s length each time a pop operation is called.

Here’s an example:

from collections import deque

class StackUsingQueue:
    def __init__(self):
        self.queue = deque()

    def push(self, x):
        self.queue.append(x)

    def pop(self):
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())
        return self.queue.popleft()

# Usage
stack = StackUsingQueue()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())

The output for the provided code:

This code represents a stack implemented using a queue that performs a series of rotations to reorder the queue so that the last-in element can be popped first without keeping track of the size throughout operations.

Bonus One-Liner Method 5: Using List as a Queue

As a fun aside, we can exploit Python lists to perform queue operations natively, essentially bending the definition of a queue.

Here’s an example:

class StackUsingQueue:
    def __init__(self):
        self.queue = []

    def push(self, x):
        self.queue.insert(0, x)

    def pop(self):
        return self.queue.pop(0) if self.queue else None

# Usage
stack = StackUsingQueue()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())

The output for the provided code:

This unconventional and cheeky method abuses the flexibility of Python lists to replicate a queue’s enqueue and dequeue operations with list insertion and popping at index 0, effectively mimicking stack operations by leveraging the high-level functionalities of Python.

Summary/Discussion

• Method 1: Reversal. Strength: Mimics stack behavior precisely. Weakness: High overhead for each push operation.
• Method 2: Recursive Popping. Strength: Elegant and interesting recursion usage. Weakness: Recursive overhead and not memory efficient for large stacks.
• Method 3: Iterative Size Tracking. Strength: More operationally efficient than reversing on push. Weakness: Extra storage for size tracking and slightly complex pop logic.
• Method 4: Counted Iterative Pop. Strength: No additional storage for size. Weakness: Computationally expensive for frequent pop operations due to rotations.
• Bonus Method 5: Using List as a Queue. Strength: Extremely simple and leverages Python’s high-level list operations. Weakness: Stretches the definition of ‘using a queue’ and might not be considered a valid implementation in strict terms.