打开《Python 编程与应用实践》_成为Python大佬_9.2.1栈的基本概念

【摘要】 本书摘自《Python 编程与应用实践》一书中第9章，第2节，由冯伟森，王建，杨宁主编。

9.2 栈

9.2.1栈的基本概念

栈 (stacks) 是一种只能通过访问其一端来实现数据存储与检索的线性数据结构，具 有后进先出 (Last In First Out,LIFO) 的特征。由于栈具有后进先出的特点，所以任何 不在栈顶的元素都无法访问。为了得到栈底的元素，必须先去掉上面的元素。对栈的两种 主要操作是将一个元素压入栈和将一个元素弹出栈。入栈使用push() 方法，出栈使用 pop() 方法，

栈的基本操作如下：

(1)stack(): 建立一个空的栈对象。

(2)push(): 把一个元素添加到栈的最顶层。

(3)pop(): 删除栈最顶层的元素，并返回这个元素。

(4)peek(): 返回最顶层的元素，并不删除它。

(5)isEmpty(): 判断栈是否为空。

(6) size(): 返回栈中元素的个数。

9.2.2 顺序栈

顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的 数据元素，同时附设指针 top指示栈顶元素在顺序栈中的位置。这里以top=-1 表示空栈。

顺序栈是基于数组实现的。9.2.3 链式栈

链式栈可以通过单链表的方式来实现，使用链式栈的优点在于它能够克服用数组实现 的顺序栈空间利用率不高的缺点，但是需要为每个栈元素分配额外的指针空间存放指针。

9.3 队列

9.3.1 队列的基本概念

队列 (Queue) 是一种具有先进先出特征的线性数据结构，元素的增加只能在一端进 行，元素的删除只能在另一端进行。能够增加元素的队列一端称为队尾，可以删除元素的 队列一端则称为队首。

队列的操作如下：

(1)Queue(): 创建一个空的队列。

(2)enqueue(item): 往队列中添加一个 item 元素。

(3)dequeue(): 从队列头部删除一个元素。

(4)is_empty(): 判断一个队列是否为空。

(5)size(): 返回队列的大小。

队列的实现同栈一样，队列也可以用顺序表或者链表的方式实现。顺序队列的存储结 构如图9-8所示。

9.3.3 双端队列

双端队列是一种类似于队列的元素的有序集合。它拥有两端，即队首和队尾，并且元 素保持在当前的位置。双端队列的一个特点是添加和删除元素的位置不受限制，新元素可

以在队首或者队尾添加。同样地，双端队列中的元素可以从两端弹出。在某种意义上，这 种混合的线性结构同时具有栈和队列的性质。

双端队列的基本操作如下：

(1)Deque(): 创建一个空的双端队列。

(2)add_front(item): 从队头加入一个item 元素。

(3)add_rear(item): 从队尾加入一个 item 元素。

(4)remove_front(): 从队头删除一个元素。

(5)remove_rear(): 从队尾删除一个元素。

(6)is_empty(): 判断双端队列是否为空。

(7)size(): 返回队列的大小。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们 18664393530@aliyun.com 处理，核实后本网站将在24小时内删除侵权内容。