Queue On Pseudo Stack

Queue on Pseudo Stack

A queue is a data structure that follows the FIFO (First-In-First-Out) principle. It has two main operations: enqueue, which adds an element to the back of the queue, and dequeue, which removes and returns the element at the front of the queue.

The "Queue on Pseudo Stack" concept involves implementing a queue using two stacks. A stack is a data structure that follows the LIFO (Last-In-First-Out) principle, with push and pop operations.

The idea is to use one stack (let's call it the "push_stack") for enqueueing elements, and another stack (let's call it the "pop_stack") for dequeueing elements. When we need to enqueue an element, we simply push it onto the push_stack. When we need to dequeue an element, we first check if the pop_stack is empty. If it is, we transfer all the elements from the push_stack to the pop_stack in reversed order. This way, the element at the top of the pop_stack becomes the front of the queue, and we can pop it. If the pop_stack is not empty, we can directly pop the top element.

This approach ensures that the elements are dequeued in the correct order, maintaining the FIFO property of a queue.

Implementation

Here's an example implementation of a queue using two stacks in Python:

class Queue:
    def __init__(self):
        self.push_stack = []
        self.pop_stack = []

    def enqueue(self, value):
        self.push_stack.append(value)

    def dequeue(self):
        if not self.pop_stack:
            # Transfer elements from push_stack to pop_stack
            while self.push_stack:
                self.pop_stack.append(self.push_stack.pop())

        if not self.pop_stack:
            raise IndexError("Queue is empty")

        return self.pop_stack.pop()

    def is_empty(self):
        return not self.push_stack and not self.pop_stack

    def size(self):
        return len(self.push_stack) + len(self.pop_stack)

In this implementation, we initialize two empty lists, push_stack and pop_stack, in the constructor. The enqueue method simply appends the value to the push_stack.

The dequeue method first checks if the pop_stack is empty. If it is, it transfers all the elements from the push_stack to the pop_stack in reversed order. Then, it pops and returns the top element from the pop_stack. If both stacks are empty, an IndexError is raised.

The is_empty method checks if both stacks are empty and returns a boolean indicating the result.

The size method returns the combined size of both stacks, which corresponds to the number of elements in the queue.

Time and Space Complexity

The time complexity of enqueue and dequeue operations in this implementation is O(1) on average. Enqueueing an element simply involves appending it to the push_stack, which is an O(1) operation. Dequeueing an element requires transferring elements from the push_stack to the pop_stack, which is also an O(1) operation on average.

The space complexity of the implementation is O(N), where N is the number of elements in the queue. This is because we use two stacks to store the elements, and the maximum combined size of the stacks is equal to the number of elements in the queue.

Let's solve the "Implement Queue using Stacks" question from LeetCode using the "Queue on Pseudo Stack" concept.

Problem: Implement a queue using two stacks.

Here's the solution code in Python with proper comments explaining each step:

class MyQueue:
    def __init__(self):
        self.push_stack = []
        self.pop_stack = []

    def push(self, x: int) -> None:
        # Push the element onto the push_stack
        self.push_stack.append(x)

    def pop(self) -> int:
        # If pop_stack is empty, transfer elements from push_stack
        if not self.pop_stack:
            while self.push_stack:
                self.pop_stack.append(self.push_stack.pop())

        # Pop the top element from pop_stack
        return self.pop_stack.pop()

    def peek(self) -> int:
        # If pop_stack is empty, transfer elements from push_stack
        if not self.pop_stack:
            while self.push_stack:
                self.pop_stack.append(self.push_stack.pop())

        # Return the top element from pop_stack without removing it
        return self.pop_stack[-1]

    def empty(self) -> bool:
        # Check if both stacks are empty
        return not self.push_stack and not self.pop_stack

In this implementation, we create two empty stacks: push_stack and pop_stack.

The push method simply appends the element to the push_stack.

The pop method first checks if the pop_stack is empty. If it is, it transfers all the elements from the push_stack to the pop_stack by popping from push_stack and pushing onto pop_stack in reversed order. Then, it pops and returns the top element from the pop_stack. This ensures that elements are dequeued in the correct order.

The peek method is similar to pop, but instead of removing the top element from pop_stack, it returns it without removing it.

The empty method checks if both stacks are empty and returns a boolean indicating the result.

Time and Space Complexity

The time complexity of the push operation is O(1) since it involves appending an element to the push_stack.

The time complexity of the pop and peek operations is O(1) on average. If the pop_stack is empty, we need to transfer elements from the push_stack to the pop_stack. This operation takes O(N), where N is the number of elements in the queue. However, since we only need to transfer elements once for every N operations, the amortized time complexity is O(1).

The space complexity of the implementation is O(N), where N is the number of elements in the queue. This is because we use two stacks to store the elements, and the maximum combined size of the stacks is equal to the number of elements in the queue.