DSACQ - Editorial

editorial
, , ,
1

Problem Link - Implement Stack Using Queue

Problem Statement:

You are tasked with implementing a stack using two queues. The stack should support four operations:

  • push x: Pushes element xx to the top of the stack.

  • pop: Removes the element on the top of the stack.

  • top: Returns the element on the top of the stack.

  • size: Returns the size of the stack.

Approach:

A stack uses the LIFO principle, while a queue uses FIFO. To simulate a stack with two queues (q1 and q2):

  • push(x): Insert the new element into q2, transfer all elements from q1 to q2, then swap q1 and q2 so q1 holds the stack.

  • pop(): Remove the front of q1 (the stack’s top). If empty, print an error message.

  • top(): Return the front of q1. If empty, print an error message.

  • size(): Return the number of elements in q1.

Time Complexity:

  • push(x): O(n), as all elements from q1 are moved to q2.

  • pop(): O(1), only the front element is removed.

  • top(): O(1), only the front element is accessed.

  • size(): O(1), size is stored directly.

Space Complexity:

  • O(n), since both queues can hold up to n elements.