剑指offer的python实现(七)-用两个栈实现队列
【用两个栈实现一个队列】
用两个栈来实现一个队列，完成队列的push和pop操作。队列中的元素为int类型。
思路：
【首先明白栈和队列这两种不同的数据结构特点 ，栈中元素：先进后出原则，把栈想象成一个桶，先压进去的元素在桶底（栈底），后压进去的元素在桶顶（栈顶）；队列元素：先进先出，像排队一样，先进来的元素优先离开。】
1) 初始化两个栈，stack1和stack2；
2) push操作（数据压入）时，stack1用来存放压入的数据；
3) 想要调用pop操作（即数据弹出），分两种情况：
a.如果stack2不为空，则直接弹出其栈顶元素；
b.若stack2为空，先把stack1中现有的所有的数据全部弹出，依次存放进stack2, 再从stack2中弹出栈顶数据，即完成pop操作
# -*- coding:utf-8 -*-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 :q=self.stack1.pop()self.stack2.append(q)if self.stack2==[]:return 'All data has been popped'return self.stack2.pop()
测试：
s=Solution()print('队列push 2')s.push(2)print('队列push 3')s.push(3)print('队列pop操作：',s.pop())print('队列push 4')s.push(4)print('队列push 5')s.push(5)print('队列pop操作：',s.pop())print('队列pop操作:',s.pop())print('队列pop操作:',s.pop())print('队列pop操作:',s.pop())# result:队列push 2队列push 3队列pop操作：2队列push 4队列push 5队列pop操作：3队列pop操作: 4队列pop操作: 5队列pop操作: Now all data has been popped
可以看到push数字2，3，4，5，即入队顺序是2，3，4，5，调用pop后出队顺序也是2，3，4，5，push和pop操作的顺序不影响先入先出的结果，即用两个栈完成了一个队列先入先出的功能。
点击左下角【阅读原文】查看本题描述
【往期文章回顾】
二叉树
排序算法
Python