python实现栈和队列
栈和队列是两种基本的数据结构,同为容器类型。两者根本的区别在于:
stack:后进先出
queue:先进先出
PS:stack和queue是不能通过查询具体某一个位置的元素而进行操作的。但是他们的排列是按顺序的
对于stack我们可以使用python内置的list实现,因为list是属于线性数组,在末尾插入和删除一个元素所使用的时间都是O(1),这非常符合stack的要求。当然,我们也可以使用链表来实现。
stack的实现代码(使用python内置的list),实现起来是非常的简单,就是list的一些常用操作
![python实现栈和队列 python实现栈和队列](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzQwMC8wN2I1YzRjYWViZWZiN2RmMjE2MzM5ZmU3M2NmOGM5MC5wbmc=) 我们定义如下的链表来实现队列数据结构:
![python实现栈和队列 python实现栈和队列](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzczOC9lMzlhMmEwZGRmMjY2YjM2NzBiNTVhOGMwZmYxMGJhYS5wbmc=) 定义一个头结点,左边指向队列的开头,右边指向队列的末尾,这样就可以保证我们插入一个元素和取出一个元素都是O(1)的操作,使用这种链表实现stack也是非常的方便。实现代码如下:
![python实现栈和队列 python实现栈和队列](/default/index/img?u=aHR0cHM6Ly9waWFuc2hlbi5jb20vaW1hZ2VzLzkzNy9mZDEyY2U5MTNmMzE1MDIxYTZkNTY4YWFhZGI1YmU5OS5wbmc=)
|
|