Implement Stack using Queues Python Solution

LeetCode 225, Easy. Topics: Stack, Design, Queue. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

lcpy gen -n 225   # by problem number
lcpy gen -s implement_stack_using_queues   # by problem name

Problem

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

Examples

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

Constraints

1 <= x <= 9
At most 100 calls will be made to push, pop, top, and empty.
All the calls to pop and top are valid.

Notes:

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.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

Follow-up: Can you implement the stack using only one queue?

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import deque


class MyStack:
    def __init__(self) -> None:
        self.queue: deque[int] = deque()

    # Time: O(n)
    # Space: O(n)
    def push(self, x: int) -> None:
        self.queue.append(x)
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

    # Time: O(1)
    # Space: O(1)
    def pop(self) -> int:
        return self.queue.popleft()

    # Time: O(1)
    # Space: O(1)
    def top(self) -> int:
        return self.queue[0]

    # Time: O(1)
    # Space: O(1)
    def empty(self) -> bool:
        return len(self.queue) == 0

Complexity

Time	Space
O(n)	O(n)

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Implement Stack using Queues Python Solution

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags