leetcode with python:232. Implement Queue using Stacks

题目:

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%)

那我们下题见