【20250211】栈与队列：225.用队列实现栈
# class MyStack:
# def __init__(self):
# #deque是双端队列，左侧是先进的，popleft就是先入先出，pop就是后入先出
# self.que = deque()
# def push(self, x):
# self.que.append(x)
# def pop(self):
# if self.empty():
# return None
# #把前len(self.que)-1的数据都加到后面去，露出最后一个数据再弹出
# for i in range(len(self.que)-1):
# self.que.append(self.que.popleft())
# return self.que.popleft()
# #top就是获取最前面的数据但是不能弹除
# def top(self):
# # 写法一：
# # if self.empty():
# # return None
# # return self.que[-1]
# # 写法二：
# if self.empty():
# return None
# for i in range(len(self.que)-1):
# self.que.append(self.que.popleft())
# temp = self.que.popleft()
# self.que.append(temp)
# return temp
# def empty(self):
# return not self.que
#方法一：使用单个队列
# class MyStack:
# def __init__(self):
# self.deq=deque()
# def push(self,x):
# self.deq.append(x)
# def pop(self):
# if self.empty():
# return False
# else:
# for i in range(len(self.deq)-1):
# self.deq.append(self.deq.popleft())
# return self.deq.popleft()
# def top(self):
# if self.empty():
# return False
# else:
# for i in range(len(self.deq)-1):
# self.deq.append(self.deq.popleft())
# temp=self.deq.popleft()
# self.deq.append(temp)
# return temp
# def empty(self):
# return not self.deq
#方法二：使用双队列 这种方法与第一种方法大同小异，都是把前len(deq)-1给存下来，一个是用自己存，另一个是用第二个队列存
from collections import deque
class MyStack:
def __init__(self):
# Python普通的Queue或SimpleQueue没有类似于peek的功能
# 也无法用索引访问，在实现top的时候较为困难。
# 用list可以，但是在使用pop(0)的时候时间复杂度为O(n)
# 因此这里使用双向队列，我们保证只执行popleft()和append()，因为deque可以用索引访问，可以实现和peek相似的功能
# in - 存所有数据
# out - 仅在pop的时候会用到
self.queue_in = deque()
self.queue_out = deque()
def push(self, x):
# 直接append即可
self.queue_in.append(x)
def pop(self):
# 1. 首先确认不空
# 2. 因为队列的特殊性，FIFO，所以我们只有在pop()的时候才会使用queue_out
# 3. 先把queue_in中的所有元素（除了最后一个），依次出列放进queue_out
# 4. 交换in和out，此时out里只有一个元素
# 5. 把out中的pop出来，即是原队列的最后一个
# tip：这不能像栈实现队列一样，因为另一个queue也是FIFO，如果执行pop()它不能像
# stack一样从另一个pop()，所以干脆in只用来存数据，pop()的时候两个进行交换
if self.empty():
return None
for i in range(len(self.queue_in) - 1):
self.queue_out.append(self.queue_in.popleft())
self.queue_in, self.queue_out = self.queue_out, self.queue_in # 交换in和out，这也是为啥in只用来存
return self.queue_out.popleft()
def top(self):
# 写法一：
# 1. 首先确认不空
# 2. 我们仅有in会存放数据，所以返回第一个即可（这里实际上用到了栈）
# 写法二：
# 1. 首先确认不空
# 2. 因为队列的特殊性，FIFO，所以我们只有在pop()的时候才会使用queue_out
# 3. 先把queue_in中的所有元素（除了最后一个），依次出列放进queue_out
# 4. 交换in和out，此时out里只有一个元素
# 5. 把out中的pop出来，即是原队列的最后一个，并使用temp变量暂存
# 6. 把temp追加到queue_in的末尾
# 写法一：
# if self.empty():
# return None
# return self.queue_in[-1] # 这里实际上用到了栈，因为直接获取了queue_in的末尾元素
# 写法二：
if self.empty():
return None
for i in range(len(self.queue_in) - 1):
self.queue_out.append(self.queue_in.popleft())
self.queue_in, self.queue_out = self.queue_out, self.queue_in
temp = self.queue_out.popleft()
self.queue_in.append(temp)
return temp
def empty(self):
#因为只有in存了数据，只要判断in是不是有数即可
return len(self.queue_in) == 0