Python Algorithm Q23

Q23 Implement Stack using Queues

---

Q

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.

Sample Input

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.

1. My Solution

'''
In this Question, to build stack only using Queue, the permitted operation is "popleft", and "push". This operations exist in the type Deque. Deque also supports operation like "pop", but used only two operations above to make stack only using "Queue".
'''

class MyStack:
    def __init__(self):
        #define with the type deque
        self.q = collections.deque()

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

    #flip the list, popout 1st element, then flip again
    def pop(self) -> int:
        self.q.reverse()
        pop = self.q.popleft()
        self.q.reverse()
        return pop

    #flip the list, popout 1st element and save, then flip again, append it again.
    def top(self) -> int:
        self.q.reverse()
        top = self.q.popleft()
        self.q.reverse()
        self.q.append(top)
        return top         

    def empty(self) -> bool:
        if self.q:
            return False
        else:
            return True

#for test
obj = MyStack()
obj.push(10)
obj.push(5)
p2 = obj.pop()
print(obj.q)
p3 = obj.top()
print(obj.q)
p4 = obj.empty()
print(p4, obj.q)

self.q = collections.deque is the most confusing part in the codes above… From now on, remind self.(var name) = things to assign.

Refer to the commentary above the code. Really simple problem.

2. Given Solution

class MyStack:
    def __init__(self):
        #define with the type deque
        self.q = collections.deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        #after appedning the element, re-sort the list that new input comes first
        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

Passing through other codes, let’s discuss def push. This is the function that sort the list. For example, self.q is [1, 2, 3, 4] and append 5 to the list. It becomes [1, 2, 3, 4, 5]. However, to make “Stack”, we must follow LIFO rule. Simply using the operation “leftpop” can not shape the operation “pop”. So locate the input from the last to the first place. Then [5, 1, 2, 3, 4] is the result.

Overall Review

Implementing stack with Queue is quiet interesting experience. But more need to solve the questions using stack…