We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Implement Stack using Queues

Difficulty: Easy

Problem Description

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).

Key Insights

  • A stack is a LIFO (Last In First Out) data structure, whereas a queue is a FIFO (First In First Out) data structure.
  • To implement a stack using two queues, we can utilize the properties of queues to reverse the order of elements.
  • One queue will be used for pushing elements, while the other will help in maintaining the stack order during pop and top operations.

Space and Time Complexity

Time Complexity:

  • Push: O(n) (in the worst case, we may need to transfer all elements to maintain order)
  • Pop: O(1) (removing the front element of the queue)
  • Top: O(1) (accessing the front element of the queue)
  • Empty: O(1)

Space Complexity: O(n) (for storing elements in the two queues)

Solution

To implement a stack using two queues, we can use the following approach:

  1. Use two queues: queue1 for storing elements and queue2 for assisting in maintaining the stack order.
  2. When pushing an element:
    • Add the element to queue1.
    • Transfer all elements from queue1 to queue2, so that the newly added element is at the front of queue2.
    • Swap the names of queue1 and queue2 to keep queue1 as the main storage.
  3. For popping an element:
    • Simply dequeue from queue1.
  4. For accessing the top element:
    • Return the front element of queue1.
  5. To check if the stack is empty:
    • Check if queue1 is empty.

Code Solutions

from collections import deque

class MyStack:
    def __init__(self):
        self.queue1 = deque()  # Main queue to hold stack elements
        self.queue2 = deque()  # Auxiliary queue

    def push(self, x: int) -> None:
        self.queue1.append(x)  # Add element to queue1
        # Move all elements in queue1 to queue2
        while self.queue1:
            self.queue2.append(self.queue1.popleft())
        # Swap the names of the two queues
        self.queue1, self.queue2 = self.queue2, self.queue1

    def pop(self) -> int:
        return self.queue1.popleft()  # Remove and return the top element

    def top(self) -> int:
        return self.queue1[0]  # Return the top element without removing it

    def empty(self) -> bool:
        return not self.queue1  # Check if queue1 is empty
← Back to All Questions