# Implementing a Stack with Two Queues in Python

Rate this post

π‘ Problem Formulation: Stacks and queues are fundamental data structures in computer science with contrasting principles β stacks are LIFO (last in, first out) and queues are FIFO (first in, first out). The challenge is to implement a stack’s LIFO behavior using two queues as the underlying data structures, ensuring all stack operations such as push (add) and pop (remove) retain their usual complexities. For instance, if we push the numbers 1, 2, and 3 in succession and then pop, the output should be 3.

## Method 1: Using Push-Costly Approach

This method focuses on making the `push` operation costly. The main idea is to empty the first queue and place all elements into the second queue, then enqueue the new element to the first queue and reverse the process. This ensures that the newest element is always at the front of the first queue, simulating the stack’s behavior.

Here’s an example:

```from queue import Queue

class StackUsingQueues:
def __init__(self):
self.q1 = Queue()
self.q2 = Queue()

def push(self, element):
self.q2.put(element)
while not self.q1.empty():
self.q2.put(self.q1.get())
self.q1, self.q2 = self.q2, self.q1

def pop(self):
return self.q1.get() if not self.q1.empty() else None

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

stack = StackUsingQueues()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())```

Output:

`3`

This code snippet defines a stack data structure that uses two queues. The `push` method is designed to be costly; it makes sure that the newest element is always at the front of `q1` by emptying `q1` into `q2`, enqueuing the new element into `q1`, and then moving everything back from `q2` to `q1`. The `pop` method simply dequeues the front element from `q1`, effectively mimicking the desired LIFO behavior of a stack.

## Method 2: Using Pop-Costly Approach

In contrast to Method 1, this technique emphasizes a costly `pop` operation. Elements are enqueued in the first queue normally. For the `pop` operation, elements are dequeued from the first queue and enqueued to the second queue, leaving only the last element, which is then dequeued to simulate the stack’s `pop`.

Here’s an example:

```from queue import Queue

class StackUsingQueues:
def __init__(self):
self.q1 = Queue()
self.q2 = Queue()

def push(self, element):
self.q1.put(element)

def pop(self):
while self.q1.qsize() > 1:
self.q2.put(self.q1.get())
popped = self.q1.get() if not self.q1.empty() else None
self.q1, self.q2 = self.q2, self.q1
return popped

def top(self):
return self.pop()

stack = StackUsingQueues()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())```

Output:

`3`

The code defines a similar stack class but this time with a costly `pop` instead of `push`. It dequeues every element except for the last one, which is the one to be popped. The remaining elements are preserved in the second queue, and the queues are swapped to reset the structure. The `top` method is simply a pop without the dequeue.

## Bonus One-Liner Method 3: Efficient Stack with Amortized O(1) Operations

This approach doesn’t strictly follow the two-queue logic, but it is a clever workaround that can maintain amortized O(1) complexity for both `push` and `pop` using Python’s built-in list data structure. It’s an intriguing way to consider how a stack can be effectively emulated with a different underlying structure.

Here’s an example:

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

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

def pop(self):
return self.queue.pop()

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

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())```

Output:

`3`

This example is quite simple, with a stack that is just a Python list. The list’s `append()` and `pop()` methods perfectly replicate a stack’s push and pop functions, and because Python lists are dynamic arrays, these operations generally run with O(1) amortized time complexity, which is very efficient.

## Summary/Discussion

• Method 1: Push-Costly. It provides a clear stack-like operation with every push, but the O(n) complexity for push operations may be detrimental for large stacks.
• Method 2: Pop-Costly. This method offers a better performance for frequent push operations, but suffers during pops, making it suitable for situations where pop is rarely called.
• Bonus Method 3: Efficient Stack. While it sidesteps the two-queue requirement, it provides an efficient alternative for implementing a stack with O(1) amortized time for both push and pop operations, thus very suitable for most practical purposes.