当前位置：首页 > 编程日记 > 正文

栈和队列在python中的实现

编程日记 2024-06-08 03:10:00

栈和队列是两种基本的数据结构，同为容器类型，队列是先进先出，栈是先进后出。

栈

请添加图片描述
栈提供 push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。不像是set 或者map 提供迭代器iterator来遍历所有元素。

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。

对于stack我们可以使用python内置的list实现，因为list是属于线性数组，在末尾插入和删除一个元素所使用的时间都是O(1),这非常符合stack的要求。当然，我们也可以使用链表来实现。

stack的实现代码（使用python内置的list），实现起来是非常的简单，就是list的一些常用操作。

class Stack(object):def __init__(self):self.stack = []def push(self, value):    # 进栈self.stack.append(value)def pop(self):  #出栈if self.stack:self.stack.pop()else:raise LookupError('stack is empty!')def is_empty(self): # 如果栈为空return bool(self.stack)def top(self): #取出目前stack中最新的元素return self.stack[-1]

队列

请添加图片描述
队列是一种先进先出的（First In First Out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许在中间部位进行操作！假设队列是q=（a1，a2，……，an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，总是在队列最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然排在队伍最后。

定义一个头结点，左边指向队列的开头，右边指向队列的末尾，这样就可以保证我们插入一个元素和取出一个元素都是O(1)的操作，使用这种链表实现stack也是非常的方便。实现代码如下：

class Head(object):def __init__(self):self.left = Noneself.right = Noneclass Node(object):def __init__(self, value):self.value = valueself.next = Noneclass Queue(object):def __init__(self):#初始化节点self.head = Head()def enqueue(self, value):#插入一个元素newnode = Node(value)p = self.headif p.right:#如果head节点的右边不为None#说明队列中已经有元素了#就执行下列的操作temp = p.rightp.right = newnodetemp.next = newnodeelse:#这说明队列为空，插入第一个元素p.right = newnodep.left = newnodedef dequeue(self):#取出一个元素p = self.headif p.left and (p.left == p.right):#说明队列中已经有元素#但是这是最后一个元素temp = p.leftp.left = p.right = Nonereturn temp.valueelif p.left and (p.left != p.right):#说明队列中有元素，而且不止一个temp = p.leftp.left = temp.nextreturn temp.valueelse:#说明队列为空#抛出查询错误raise LookupError('queue is empty!')def is_empty(self):if self.head.left:return Falseelse:return Truedef top(self):#查询目前队列中最早入队的元素if self.head.left:return self.head.left.valueelse:raise LookupError('queue is empty!')

参考链接：https://www.cnblogs.com/yiduobaozhiblog1/p/9272556.html

https://www.dkcj.cn/info/9754.html

栈和队列在python中的实现

栈

队列

相关文章：

CSS之布局（盒子模型--外边距）

SAP Netweaver 7.4 SR2 Application Java Installation

Spring+SpringMVC+MyBatis深入学习及搭建(十)——MyBatis逆向工程

（一）七种AOP实现方法

[导入]Java线程的深入探讨

CSS之布局（盒子的水平布局）

IssueVission的命令处理

下一版本Windowsreg; CE 开发工具Smart Device Extensions for Microsoft Visual Studioreg; .NET...

vue 手机键盘把底部按钮顶上去

CSS之布局（盒子的垂直布局）

microsoft 为microbit.org 设计的课程

Java, Mono, or C++?

CSS之布局（外边距的折叠）

图论--欧拉路，欧拉回路(小结)

轻松一下，看看vs.net2002变态的智能提示，不知道算不算bug

C++构造函数（一）

CSS之布局（行内元素的盒模型）

es安装的时候遇到的所有的坑

MD5 - Bump Mapping

『03网络』实验一：多功能浏览器的使用和个人Blog的创建和使用

SQL Server 最佳实践分析器使用小结

Vue 框架-02-事件：点击, 双击事件,鼠标移上事件

HTML5 canvas绘制雪花飘落

CSS之布局（默认样式）

Junit资料汇集

LESS 的 operation 是特性

测一测你的blog魔症有多严重

CSS之布局（盒子的尺寸）

自己写的一个测试函数执行效率的单元(test on Delphi 7)

datatable自动增加序号