題目:

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.

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.

用queue設計一個stack,它有push(加入值),pop(去除並回傳最後一個值),top(回傳最後一個值),empty(回傳其是否為空)的功能

又是要我們設計一系列函數的題目
這題的限制是只能用queue的功能下去實作,如push to back(從尾端將值放入),peek/pop from front(取得或移除最前端的值),size(獲取queue長度)和is empty(確認是否為空)

class MyStack:

    def __init__(self):
        self.queue=[]
        self.t=None

    def push(self, x: int) -> None:
        self.queue.append(x)
        self.t=x
        
    def pop(self) -> int:
        if len(self.queue)==1:
            self.t=None
            return self.queue.pop()
            
        for i in range(len(self.queue)-2):
            self.queue.append(self.queue.pop(0))
        self.t=self.queue.pop(0)
        self.queue.append(self.t)
        return self.queue.pop(0)
            
    def top(self) -> int:
        return self.t

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

我們逐各個函數來解釋:
(1)init:
宣告一個紀錄值的queue跟一個紀錄queue尾端值的t
(2)push:
queue直接append值
t則變為填入的值
(3)pop:
若當時queue長度為1,t變為None,直接將queue內的值pop回傳
若不為1,則將queue內第一位取出填入尾端len(queue)-2次
此時的頭為未來的新top
將其取出後紀錄到t後填入尾端
此時的頭為要去除並回傳的值
將其取出回傳即可
(4)top:
回傳t即可
(5)empty:
檢測len(queue)是否等於0
最後執行時間24ms(faster than 99.16%)

那我們下題見