232用栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/
用栈实现队列代码随想录
https://programmercarl.com/0232.用栈实现队列.html#其他语言版本
225用队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/description/
用队列实现栈代码随想录
https://programmercarl.com/0225.用队列实现栈.html#其他语言版本
基础知识
python实现队列和栈分别使用:
栈使用列表
##
a = []
a.append(1)##push
a.pop()##pop
len(a)!=0##empty
队列使用collections.deque(其实是双向队列)
##
b = collections.deque()
b.append(2)##进队列
b.popleft()##出队列
232用栈实现队列
题目
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):
实现 MyQueue 类:
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false
题解:
- 重点在pop;
- 合理利用两个栈;pop时,将新元素缓存在另一个栈内;
- 一个用于进
- 一个用于出
题解代码:
class MyQueue:
def __init__(self):
self.stack_in = collections.deque()
self.stack_out = collections.deque()
def push(self, x: int) -> None:
self.stack_in.append(x)
def pop(self) -> int:
if self.empty():
return None
if self.stack_out:
return self.stack_out.pop()
for i in range(len(self.stack_in)):
node = self.stack_in.pop()
self.stack_out.append(node)
node_i = self.stack_out.pop()
return node_i
def peek(self) -> int:
node_1 = self.pop()
self.stack_out.append(node_1)
return node_1
def empty(self) -> bool:
if len(self.stack_in)==0 and len(self.stack_out)==0:
return True
else:
return False
225用队列实现栈
题目
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。
实现 MyStack 类:
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。
题解
- 重点在pop上;top其实=先pop再push;
- push和empty都正常;
- 一个队列就可以实现pop;每次都把队列顺序重新排一遍,最后一个就会先弹出;
题解代码
class MyStack:
def __init__(self):
self.queue = collections.deque()
def push(self, x: int) -> None:
self.queue.append(x)
def pop(self) -> int:
###方法一:两个队列
if self.empty():
return None
for i in range(len(self.queue_1)-1):
node_i = self.queue_1.popleft()
self.queue_2.append(node_i)
node = self.queue_1.popleft()
self.queue_1,self.queue_2 = self.queue_2,self.queue_1
return node
###方法二:一个队列
if self.empty():
return None
for i in range(len(self.queue)-1):
self.queue.append(self.queue.popleft())
return self.queue.popleft()
def top(self) -> int:
tmp = self.pop()
self.push(tmp)
return tmp
def empty(self) -> bool:
if self.queue:
return False
else:
return True
标签:10,return,队列,self,随想录,pop,queue,stack
From: https://www.cnblogs.com/P201821440041/p/18245321