leetcode with python:225. Implement Stack using Queues

题目:

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

那我们下题见