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.

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.

Example 1:

**Input**
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], [|], [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.

Solve¶

I assuming we can only use 4 queue function, that is similar to Leetcode Stack implement provided:

push
pop
first (which return the first person/element value about to leave the queue - similar to the top of stack)
empty

2 Queue - Push/Insert modified¶

O(n)

We do need to implement Queue, to create a Stack that using Queue

# FIFO
class MyQueue:
    def __init__(self):
        self.arr = []

    def push(self, v):
        self.arr.append(v)

    def pop(self):
        return self.arr.pop(0)

    def first(self):
        return self.arr[0]

    def empty(self):
        return len(self.arr) == 0

The first implementation:

I try to only use q1 as the actual stack
q2 is a buffer to temporally holding the value, which always empty.

We perform operation on our Queue to represented Stack push implementation, so that we push in to the First of Queue, instead of Last.

    def push(self, x: int) -> None:
        self.q2.push(x)

        while not self.q1.empty():
            v = self.q1.pop()
            self.q2.push(v)
        self.q1, self.q2 = self.q2, self.q1

We push the value to q2, making x standing as the first element of q2 queue
We push all value of q1 in to q2 by pop() each element out, this maintain the order of element of q1 transfer over q2
Swapping q1 and q2

We maintaining q1 is the only representation of our stack, while q2 == []. By achieve the modify on queue insert, all other operation can be keep the same.

Final implementation:

Time Submitted	Status	Runtime	Memory	Language
08/28/2023 23:47	Accepted	37 ms	16.4 MB	python3

# FIFO
class MyQueue:
    def __init__(self):
        self.arr = []

    def push(self, v):
        self.arr.append(v)

    def pop(self):
        return self.arr.pop(0)

    def first(self):
        return self.arr[0]

    def empty(self):
        return len(self.arr) == 0

# LIFO
class MyStack:

    def __init__(self):
        self.q1 = MyQueue()
        self.q2 = MyQueue()

    def push(self, x: int) -> None:
        self.q2.push(x)

        while not self.q1.empty():
            v = self.q1.pop()
            self.q2.push(v)
        self.q1, self.q2 = self.q2, self.q1

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

    def top(self) -> int:
        return self.q1.first()

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

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

1 Queue - Push/Insert modified¶

O(n)

Just create a bookmark, where we track the last of the queue (and that I mean it will be the head of the stack). By running every element in a cycle and stop at our bookmark (also remember to pop() the bookmark out), we done done push x into the first of our queue.

Time Submitted	Status	Runtime	Memory	Language
08/29/2023 00:16	Accepted	40 ms	16.6 MB	python3

# FIFO
class MyQueue:
    def __init__(self):
        self.arr = []

    def push(self, v):
        self.arr.append(v)

    def pop(self):
        return self.arr.pop(0)

    def first(self):
        return self.arr[0]

    def empty(self):
        return len(self.arr) == 0

# LIFO
class MyStack:

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

    def push(self, x: int) -> None:
        self.q1.push(0)
        self.q1.push(x)
        v = self.q1.pop()
        while v != 0:
            self.q1.push(v)
            v = self.q1.pop()

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

    def top(self) -> int:
        return self.q1.first()

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

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

Last update : September 17, 2023
Created : August 28, 2023