225. Implement Stack using Queues

Constraints

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

Idea #1 (Time: O(N), Memory: O(N))

1. push: enqueue everything
2. pop: dequeue everything, return last one, revert without last one.
3. top: dequeue everything, return last one, revert!
4. empty: same as empty

Test Cases

Example 1:

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

Code

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        if self.front is None:
            self.front = self.rear = Node(data)
        else:
            node = Node(data)
            self.rear.next = node
            self.rear = node

    def dequeue(self):
        if self.front is None:
            return None
        node = self.front
        if self.front == self.rear:
            self.front = self.rear = None
        else:
            self.front = self.front.next
        return node.data

    def is_empty(self):
        return self.front is None

class MyStack:

    def __init__(self):
        self.myqueue = Queue()

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

    def pop(self) -> int:
        buf = list()
        while not self.myqueue.is_empty():
            buf.append(self.myqueue.dequeue())
        res = buf[-1]
        buf = buf[:-1]
        for elem in buf:
            self.myqueue.enqueue(elem)
        return res

    def top(self) -> int:
        res = self.pop()
        self.myqueue.enqueue(res)
        return res

    def empty(self) -> bool:
        return self.myqueue.is_empty()