1.用两个栈来实现一个队列
class Solution():
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
self.stack1.append(node)
def pop(self):
if self.stack2:
return self.stack2.pop()
else:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
1.初始化两个空的列表作为栈
2.所有的push都放到stack1中
3.所有的pop都从stack2中取（list的pop默认弹出最后一个元素）
4.对pop操作做判断，如果stack2为空就先把stack1中的元素倒入到stack2中，注意是“倒”，这样就可以保证stack2的最后一个元素一定是目前元素中最先进入到stack1的；如果stack2不为空（从stack1倒进stack2的），就直接从stack2中pop出来；
2.1用两个队列来实现栈-理清思路
class Solution():
def __init__(self):
self.queue1 = []
self.queue2 = []
def push(self, node):
# 1.第一种情况，当两个队列全为空，就默认放到queue1中
if not self.queue1 and not self.queue2:
self.queue1.append(node)
# 2.如果queue1空，就放到queue2中
elif not self.queue1:
self.queue2.append(node)
# 3.如果queue2空，就放到queue1中
else:
self.queue1.append(node)
def pop(self):
# 1.当全空则报栈空错误
if len(self.queue1) == 0 and len(self.queue2) == 0:
print('stack is empty')
return None
# 2.当queue1为空的时候
if not self.queue1:
# 2.1当queue2长度为1
if len(self.queue2) == 1:
return self.queue2.pop(0)
# 2.2当queue2长度大于1
else:
while len(self.queue2) > 1:
self.queue1.append(self.queue2.pop(0))
return self.queue2.pop(0)
# 3.当queue2为空的时候
if not self.queue2:
# 3.1当queue1长度为1
if len(self.queue1) == 1:
return self.queue1.pop(0)
# 3.2当queue1长度大于1
else:
while len(self.queue1) > 1:
self.queue2.append(self.queue1.pop(0))
return self.queue1.pop(0)
s = Solution()
s.push(1)
print(s.queue1)
print(s.queue2)
s.push(2)
print(s.queue1)
print(s.queue2)
s.push(3)
print(s.queue1)
print(s.queue2)
print(s.pop())
print(s.queue1)
print(s.queue2)
print(s.pop())
print(s.queue1)
print(s.queue2)
result:
[1]
[]
[1, 2]
[]
[1, 2, 3]
[]
3
[]
[1, 2]
2
[1]
[]
list的pop(0)可以弹出第一个元素，模拟成一个队列
把一串元素放到一个队列，可以将队列的第一个元素到最后第二个元素按照原来顺序放到另一个队列，将剩下那个元素pop出来就可以后进先出了。
按照上面这个思路，两个队列必有一个为空
push操作分析：
1.当两个队列都为空的时候，默认放到第一个队列
2.当队列1为空，队列2不为空，push到第二个队列
3.当队列2为空，队列1不为空，push大第一个队列
pop操作分析：
1.首先判断两个队列是否都为空，是的话返回None
2.当队列1为空需要分两种情况：a.队列2长度为1，直接pop改元素；b.队列2长度大于1，将第一个到最后第二个元素放到队列1中
3.当队列2为空的情况同上
2.2用两个队列来实现栈-pop略作简化
class Solution():
def __init__(self):
self.queue1 = []
self.queue2 = []
def push(self, node):
if not self.queue1 and not self.queue2:
self.queue1.append(node)
elif not self.queue1:
self.queue2.append(node)
else:
self.queue1.append(node)
def pop(self):
if len(self.queue1) == 0 and len(self.queue2) == 0:
print('stack is empty')
return None
if not self.queue1:
while len(self.queue2) > 1:
self.queue1.append(self.queue2.pop(0))
return self.queue2.pop(0)
if not self.queue2:
while len(self.queue1) > 1:
self.queue2.append(self.queue1.pop(0))
return self.queue1.pop(0)
pop中队列长度为1的情况可以被while循环覆盖到，不用列出来
