題目:

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

void push(int x) Pushes element x to the back of the queue.
int pop() Removes the element from the front of the queue and returns it.
int peek() Returns the element at the front of the queue.
boolean empty() Returns true if the queue is empty, false otherwise.

You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

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

又到了設計函數時間
而這題的限制是只能用stack的功能下去實作,如push to top(從尾端將值放入),peek/pop from top(取得或移除最後的值),size(獲取stack長度)和is empty(確認是否為空)

class MyQueue:

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

    def push(self, x: int) -> None:
        if len(self.stack)==0:
            self.t=x
        self.stack.append(x)

    def pop(self) -> int:
        if len(self.stack)==1:
            self.t=None
            return self.stack.pop()
        
        temp=[]
        while len(self.stack)>1:
            temp.append(self.stack.pop())
        self.t=temp[-1]
        re=self.stack.pop()
        while len(temp)>0:
            self.stack.append(temp.pop())
        return re

    def peek(self) -> int:
        return self.t

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

一樣,我們逐各個函數來解釋:
(1)init:
宣告一個紀錄值的stack跟一個紀錄stack第一個值的t
(2)push:
stack直接append值
stack長度為0時,t變為填入的值
(3)pop:
若當時stack長度為1,t變為None,直接將stack內的值pop回傳
若不為1,則建立一個臨時陣列temp
則將stack內最後一位取出放入temp直到len(stack)=1
此時stack內剩下的值便是我們要回傳並移除的數,將其移除並紀錄
且temp的尾端即為未來的新t,將t改為該值(此時temp為stack顛倒)
最後將temp內元素全數填回stack
並將紀錄值回傳即可
(4)top:
回傳t即可
(5)empty:
檢測len(stack)是否等於0
最後執行時間31ms(faster than 91.59%)

那我們下題見