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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Implement Stack using Queues

Number: 225

Difficulty: Easy

Paid? No

Companies: Google, Microsoft, Amazon, Meta, Adobe, Apple, Oracle, Bloomberg

Problem Description

Implement a last-in-first-out (LIFO) stack using only two queues. The MyStack class should support the following functions:

  • push(x): Pushes element x to the top of the stack.
  • pop(): Removes the element on the top of the stack and returns it.
  • top(): Returns the element on the top of the stack.
  • empty(): Returns true if the stack is empty, false otherwise.

Note: Only standard queue operations (push to back, pop from front, size, and is empty) can be used.

Key Insights

  • We simulate a stack (LIFO) behavior using two queues (FIFO).
  • For the push operation, use one queue (q2) to hold the new element and then transfer all elements from the other queue (q1) to q2 so that the new element is at the front.
  • Swap the roles of the two queues after each push so that q1 always holds the stack in the correct order.
  • The pop and top operations can then be implemented by simply removing or peeking at the front of q1.

Space and Time Complexity

Time Complexity:

  • push: O(n), where n is the number of elements in the stack (due to transferring all elements between queues).
  • pop: O(1)
  • top: O(1) Space Complexity: O(n), as we store all elements in the two queues.

Solution

We implement the stack using two queues. During each push operation, we enqueue the new element into an empty auxiliary queue (q2) and then move all elements from the primary queue (q1) to q2. This way, the new element comes to the front of the queue, mimicking stack behavior. Finally, we swap q1 and q2 so that q1 always represents the current stack. For pop, we simply dequeue from q1; for top, we peek at the front of q1; and for empty, we check if q1 is empty.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

from collections import deque

class MyStack:
    def __init__(self):
        # Initialize two queues using deque
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        # Push x into q2 (auxiliary queue)
        self.q2.append(x)
        # Transfer all elements from q1 to q2 to reverse the order
        while self.q1:
            self.q2.append(self.q1.popleft())
        # Swap q1 and q2 so that q1 always holds the current elements
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        # Pop element from the front of q1 which is the top of the stack
        return self.q1.popleft()

    def top(self) -> int:
        # Peek at the front of q1 to get the top element
        return self.q1[0]

    def empty(self) -> bool:
        # Return True if q1 is empty, else False
        return not self.q1
← Back to All Questions