Queue By Two Stacks

Queue By Two Stacks:

The Queue data structure follows the First-In-First-Out (FIFO) principle, where the element that has been in the queue for the longest time is the first one to be removed. In this implementation, we use two stacks to simulate the behavior of a queue.

Approach:

We use one stack, called the input_stack, to handle the enqueue operation.
We use another stack, called the output_stack, to handle the dequeue operation.
When we enqueue an element, we simply push it onto the input_stack.
When we dequeue an element, we check if the output_stack is empty. If it is empty, we transfer all elements from the input_stack to the output_stack in reversed order. Then we pop the top element from the output_stack and return it.

This approach ensures that the elements in the output_stack are in the correct order to simulate the behavior of a queue.

Example:

Here's an example of implementing a Queue using two Stacks in Python:


class Queue:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []

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

    def dequeue(self):
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())
        return self.output_stack.pop()

    def is_empty(self):
        return len(self.input_stack) == 0 and len(self.output_stack) == 0

    def size(self):
        return len(self.input_stack) + len(self.output_stack)

In this code, we define the Queue class. It has two stacks as instance variables: input_stack and output_stack. The enqueue method appends elements to the input_stack, simulating the enqueue operation. The dequeue method checks if the output_stack is empty. If it is, it transfers elements from the input_stack to the output_stack in reversed order. Then, it pops and returns the top element from the output_stack, simulating the dequeue operation.

The is_empty method checks if both stacks are empty, indicating an empty queue. The size method returns the total number of elements in the queue.

Now, let's solve a question using this concept.

Question: Implement Queue using Stacks

Implement a Queue data structure using stacks. The implementation should support the following operations: push, pop, peek, and empty.

Here's the solution:


class Queue:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []

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

    def dequeue(self):
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())
        return self.output_stack.pop()

    def is_empty(self):
        return len(self.input_stack) == 0 and len(self.output_stack) == 0

    def size(self):
        return len(self.input_stack) + len(self.output_stack)

In this solution, we implement the MyQueue class, which has the same methods as the standard Queue. The push operation appends elements to the input_stack. The pop operation calls the peek method to ensure that the output_stack is updated, then pops and returns the top element from the output_stack. The peek operation checks if the output_stack is empty, transfers elements from the input_stack if necessary, and returns the top element. The empty operation checks if both stacks are empty.

Time and Space Complexity Analysis:

The time complexity for the enqueue operation is O(1) since we directly append elements to the input_stack.

The time complexity for the dequeue operation is O(n), where n is the number of elements in the queue. In the worst case, when the output_stack is empty, we need to transfer all elements from the input_stack to the output_stack. However, subsequent dequeue operations will be O(1) until the output_stack becomes empty again.

The time complexity for the peek operation is O(1) since we access the top element directly.

The time complexity for the empty operation is O(1) since we only check if both stacks are empty.

The space complexity is O(n), where n is the number of elements in the queue. This is because we store all elements in either the input_stack or the output_stack.

Overall, this implementation provides the required queue operations with a reasonable time complexity, making it suitable for most scenarios.

Let's solve a question using the concept of implementing a Queue using two Stacks and analyze its time and space complexity.

Question: Implement Queue using Stacks

Implement a Queue data structure using stacks. The implementation should support the following operations: push, pop, peek, and empty.

Solution:


class MyQueue:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []

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

    def pop(self):
        self.peek()
        return self.output_stack.pop()

    def peek(self):
        if not self.output_stack:
            while self.input_stack:
                self.output_stack.append(self.input_stack.pop())
        return self.output_stack[-1]

    def empty(self):
        return not self.input_stack and not self.output_stack

In this solution, we implement the MyQueue class, which utilizes two stacks: input_stack and output_stack. The push operation appends elements to the input_stack. The pop operation calls the peek method to ensure that the output_stack is updated, then pops and returns the top element from the output_stack. The peek operation checks if the output_stack is empty, transfers elements from the input_stack if necessary, and returns the top element. The empty operation checks if both stacks are empty.

Time Complexity Analysis:

The time complexity for the push operation is O(1) since we directly append elements to the input_stack.

The time complexity for the pop operation is O(1) in the average case. However, in the worst case, when the output_stack is empty, we need to transfer all elements from the input_stack to the output_stack, resulting in a time complexity of O(n), where n is the number of elements in the queue. Subsequent pop operations will be O(1) until the output_stack becomes empty again.

The time complexity for the peek operation is O(1) in the average case. Similar to the pop operation, the worst-case time complexity is O(n) when the output_stack is empty and requires transferring elements from the input_stack. Subsequent peek operations will be O(1) until the output_stack becomes empty again.

The time complexity for the empty operation is O(1) since we only check if both stacks are empty.

Space Complexity Analysis:

The space complexity is O(n), where n is the number of elements in the queue. This is because we store all elements in either the input_stack or the output_stack.

Overall:

This implementation provides a way to simulate a queue using two stacks. While the worst-case time complexity for pop and peek operations is O(n), the average-case time complexity is O(1). The space complexity is reasonable at O(n). This approach is suitable for scenarios where the number of enqueue and dequeue operations is balanced and the number of elements in the queue is not excessively large.

Let's solve another question using the concept of implementing a Queue using two Stacks and analyze its time and space complexity.

Question: Implement Stack using Queues

Implement a Stack data structure using queues. The implementation should support the following operations: push, pop, top, and empty.

Solution:


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

    def push(self, x):
        self.queue.append(x)
        size = len(self.queue)
        # Move all previous elements to the end
        for _ in range(size - 1):
            self.queue.append(self.queue.pop(0))

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

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

    def empty(self):
        return len(self.queue) == 0

In this solution, we implement the MyStack class, which uses a single queue to simulate a stack. The push operation appends the new element to the end of the queue and then moves all previous elements to the end, effectively making the new element the top of the stack. The pop operation removes and returns the front element of the queue, which corresponds to the top of the stack. The top operation returns the front element without removing it. The empty operation checks if the queue is empty.

Time Complexity Analysis:

The time complexity for the push operation is O(n), where n is the number of elements in the stack. This is because, after adding the new element, we need to move all previous elements to the end of the queue. In the worst case, we iterate through all elements in the queue.

The time complexity for the pop, top, and empty operations is O(1) since we directly access the front element of the queue or check if the queue is empty.

Space Complexity Analysis:

The space complexity is O(n), where n is the number of elements in the stack. This is because we store all elements in the queue.

Overall:

This implementation provides a way to simulate a stack using a single queue. The push operation has a time complexity of O(n) due to the need to move elements, while the other operations have a time complexity of O(1). The space complexity is reasonable at O(n). This approach is suitable for scenarios where the number of push operations is balanced with the number of pop operations, and the number of elements in the stack is not excessively large.

Queue By Two Stacks

DIFFICULTY

COMPANY

Data Structures