225. Implement Stack using Queues

Easy

Problem:

Implement a stack that supports the following operations using queues.

Implement the MyStack class:

  • void push(int x) Pushes element x to the top of the stack.

  • int pop() Removes the element on the top of the stack and returns it.

  • int top() Returns the element on the top of the stack.

  • boolean empty() Returns true if the stack is empty, false otherwise.

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Notice: You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.

https://leetcode.com/problems/implement-stack-using-queues/description/

What to learn:

Deque in Python

Deque (Doubly Ended Queue) in Python is implemented using the module “collections“. Deque is preferred over a list in the cases where we need quicker append and pop operations from both the ends of the container, as deque provides an O(1) time complexity for append and pop operations as compared to a list that provides O(n) time complexity.

  • append():- This function is used to insert the value in its argument to the right end of the deque.

  • pop():- This function is used to delete an argument from the right end of the deque.

  • appendleft():- This function is used to insert the value in its argument to the left end of the deque.

  • popleft():- This function is used to delete an argument from the left end of the deque.

  • index(value, start, end):- This function returns the first index of the value mentioned in arguments, starting searching from start till end index.

  • insert(i, a) :- This function inserts the value mentioned in arguments(a) at index(i) specified in arguments.

  • remove():- This function removes the first occurrence of the value mentioned in arguments.

  • count():- This function counts the number of occurrences of value mentioned in arguments.

  • len(dequeue):- Return the current size of the dequeue.

  • Deque[0] :- We can access the front element of the deque using indexing with de[0].

  • Deque[-1] :- We can access the back element of the deque using indexing with de[-1].

  • extend(iterable):- This function is used to add multiple values at the right end of the deque. The argument passed is iterable.

  • extendleft(iterable):- This function is used to add multiple values at the left end of the deque. The argument passed is iterable. Order is reversed as a result of left appends.

  • reverse():- This function is used to reverse the order of deque elements.

  • rotate():- This function rotates the deque by the number specified in arguments. If the number specified is negative, rotation occurs to the left. Else rotation is to right.

import collections

de = collections.deque([1,2,3,4,5,6,7,8,9])
de.rotate(3)  # deque([7, 8, 9, 1, 2, 3, 4, 5, 6])
de.rotate(-3) # deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

Reference: https://www.geeksforgeeks.org/deque-in-python

Solution:

After inserting an element, reorder the entire queue to place the recently inserted element at the front. By doing this, when removing an element from the front of the queue, it will act like a stack, where the most recently inserted element comes out first.

class MyStack:

    def __init__(self):
        self.q = colletions.deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

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

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

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

Last updated