LeetCode Daily Challenge Series #1

Problem Statement

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

Solution

Before implementing any code, let's think about how to proceed. There are 2 ways to solve this problem:

• #### Using 2 queues: We can use 2 queues to implement a stack. We can process this in 2 ways -
  1. Making push method expensive
  2. Making the pop method expensive

The decision is based on the application. In our case, either one is fine.

Expensive Push method:

Push the element into Queue2 while rest of the elements are stored in Queue1. After this, pop elements from Queue1 and push into Queue2. Swap the names of Queue1 and Queue2.
If we repeat this process each time a new element is added, we will have the elements in the order we would expect to pop from a stack. Thus, we have achieved our stack.

Expensive Pop method:

Each time we have to pop - Dequeue all elements from Queue1 except the last element and enqueue into Queue2. Dequeue the last element from Queue1 and store it (this is the result that we will return). Swap the names of Queue1 and Queue2. Return the stored element. Thus, we will have the LIFO order while popping.

• #### Using 1 queue: It is possible to achieve the above behaviour using just 1 queue.
  1. Take the length of the queue, say n
  2. Enqueue the element
  3. Run a loop till n. Dequeue the element from the queue and enqueue it. This will make the new element the first element in the queue. If we keep following this every time we push a new element in the queue, we will have the elements in the proper order as we expect from a queue.
  4. Since, we have corrected the ordering of the elements in the queue, pop operation should be as simple as dequeue and return the element.

Code

Here is python implementation of class handling the stack using a single queue.

from collections import deque

class MyStack:

    def __init__(self):
        self.q1 = deque()


    def push(self, x: int) -> None:
        size = len(self.q1)
        self.q1.append(x)
        for i in range(size):
            el = self.q1.popleft()
            self.q1.append(el)

    def pop(self) -> int:
        return self.q1.popleft()


    def top(self) -> int:
        return self.q1[0]

    def empty(self) -> bool:
        return len(self.q1) == 0

Note: Here we are using deque collection from python, but we are using it as a normal queue only. We have not used any of the double-ended properties of deque