栈的数据结构,Python实现栈

2022-08-27 15:57:49 分类：python 阅读()

　　栈的数据结构,Python实现栈

　　堆栈和队列是编程中常见的数据类型。从数据结构的角度来看，栈和队列也是线性表，操作有限。本文将详细介绍Python中的栈，有兴趣的可以看看。

　　00-1010 0.学习目标1。栈的基本概念1.1栈的基本概念1.2栈的抽象数据类型1.3栈的应用场景2.1顺序栈的实现2.1.1栈的初始化2.2链栈的实现2.3栈的不同实现的比较3.1顺序栈的应用3.2链栈的应用3.3通过栈的基本操作实现复杂算法

　　

目录

　　堆栈和队列是编程中常见的数据类型。从数据结构的角度来看，栈和队列也是线性表，操作有限。它们的基本操作是线性表操作的子集，但从数据类型的角度来看，它们与线性表有很大的不同。本节将首先介绍堆栈的定义及其不同的实现，并给出堆栈的一些实际应用。

　　通过本节，您应掌握以下内容：

　　堆栈的基本概念和不同实现方法，堆栈基本操作的实现和时间复杂度，利用堆栈基本操作实现复杂算法。

　　

0. 学习目标

　　

1. 栈的基本概念

　　Stack是一个线性表，只能插入和删除一个序列的一端。对于一个栈来说，可以操作的一端叫顶，另一端叫底。如果堆栈不包含任何元素，则称为空堆栈。

　　堆栈提供了一种基于集合中的时间进行排序的方法。最近添加的元素靠近顶部，而旧的元素靠近底部。首先删除新添加的元素。这种排序原则也被称为后进先出(LIFO)或快速后进先出(FILO)。

　　栈的例子在现实中随处可见。如下图，球桶里的球形成一堆，每次只能从上面取出，放回去的时候放在上面。假设栈是S=(a0，a1，…，en)，这是最上面的元素。堆栈中的元素按的顺序推入，顶部的元素是第一个弹出的元素。

　　通过观察添加和删除元素的顺序，可以快速理解栈中包含的思想。下图显示了堆叠和卸载堆栈的过程。在堆栈中插入和移除元素的顺序正好相反。

　　

1.1 栈的基本概念

　　栈除了主操作(推入和推出)外，还有初始化、空判断、取栈顶元素等辅助操作。具体来说，堆栈的抽象数据类型定义如下：

　　基本操作：

　　1.__itit__():初始化堆栈

　　创建一个空堆栈。

　　2.Size () 3360查找并返回堆栈中包含的元素个数n。

　　如果堆栈为空，则返回整数0。

　　3.ISEMPTY () 3360确定堆栈是否为空。

　　确定元素是否存储在堆栈中。

　　4.将(数据)3360推入堆栈

　　将元素数据插入堆栈的顶部

　　5.从堆栈中弹出():

　　删除并返回栈顶元素。

　　4.peek():取栈顶元素

　　返回顶部元素值，但不删除该元素。

　　

1.2 栈抽象数据类型

　　Stack有广泛的应用场景，比如：

　　符号匹配，具体描述参见3.3小节；函数调用，每一个未完成的函数都会在函数栈中有一个数据区，里面保存着函数的重要信息，包括函数的局部变量和参数；后缀表达式求值：计算后缀表达式只需要一个存储数值的栈。当遍历表达式遇到数值时，会放入堆栈。遇到运算符时，会将两个数值放到堆栈外进行计算，计算结果放入堆栈。堆栈中保留的唯一值是表达式结果。后退按钮在网页浏览中，当我们在网页之间跳转时，这些网址被存储在一个堆栈中；编辑器中的撤销序列类似于网页浏览中的后退按钮，堆栈保存每一步的编辑操作。

　　>

　　除了以上应用外，我们在之后的学习中还将看到栈用作许多算法的辅助数据结构。

　　

　　

2. 栈的实现

　　和线性表一样，栈同样有两种存储表示方式。

　　

　　

2.1 顺序栈的实现

　　顺序栈是栈的顺序存储结构，其利用一组地址连续的存储单元从栈底到栈顶依次存放。同时使用指针top来指示栈顶元素在顺序栈中的索引，同样顺序栈可以是固定长度和动态长度，当栈满时，定长顺序栈会抛出栈满异常，动态顺序栈则会动态申请空闲空间。

　　

　　

2.1.1 栈的初始化

　　顺序栈的初始化需要三部分信息：stack 列表用于存储数据元素，max_size 用于存储 stack 列表的最大长度，以及 top 用于记录栈顶元素的索引：

　　

class Stack:
　　 def __init__(self, max_size=10):
　　 self.max_size = max_size
　　 self.stack = self.max_size * [None]
　　 self.top = -1
　　

　　2.1.2 求栈长

　　由于 top 表示栈顶元素的索引，我们可以据此方便的计算顺序栈中的数据元素数量，即栈长：

　　

 def size(self):
　　 return self.top + 1
　　

　　2.1.3 判栈空

　　根据栈的长度可以很容易的判断栈是否为空栈：

　　

 def isempty(self):
　　 if self.size() == 0:
　　 return True
　　 else:
　　 return False
　　

　　2.1.4 判栈满

　　由于需要提前申请栈空间，因此我们需要能够判断栈是否还有空闲空间：

　　

 def isfully(self):
　　 if self.size() == self.max_size:
　　 return True
　　 else:
　　 return False
　　

　　2.1.5 入栈

　　入栈时，需要首先判断栈中是否还有空闲空间，然后根据栈为定长顺序栈或动态顺序栈，入栈操作稍有不同：

　　[定长顺序栈的入栈操作] 如果栈满，则引发异常：

　　

 def push(self, data):
　　 if self.isfully():
　　 raise IndexError(Stack Overflow!)
　　 else:
　　 self.top += 1
　　 self.stack[self.top_1] = data
　　

　　[动态顺序栈的入栈操作] 如果栈满，则首先申请新空间：

　　

 def resize(self):
　　 new_size = 2 * self.max_size
　　 new_stack = [None] * new_size
　　 for i in range(self.num_items):
　　 new_stack[i] = self.items[i]
　　 self.stack = new_stack
　　 self.max_size = new_size
　　 def push(self, data):
　　 if self.isfully():
　　 self.resize()
　　 else:
　　 self.top += 1
　　 self.stack[self.top_1] = data
　　

　　入栈的时间复杂度为O(1)。这里需要注意的是，虽然当动态顺序栈满时，原栈中的元素需要首先复制到新栈中，然后添加新元素，但根据《顺序表及其操作实现》中顺序表追加操作的介绍，由于n次入栈操作的总时间T(n) 与O(n) 成正比，因此入栈的摊销时间复杂度仍可以认为是O(1)。

　　2.1.6 出栈

　　若栈不空，则删除并返回栈顶元素：

　　

 def pop(self):
　　 if self.isempty():
　　 raise IndexError(Stack Underflow!)
　　 else:
　　 result = self.stack[self.top]
　　 self.top -= 1
　　 return result
　　

　　2.1.7 求栈顶元素

　　若栈不空，则只需返回栈顶元素：

　　

 def peek(self):
　　 if self.isempty():
　　 raise IndexError(Stack Underflow!)
　　 else:
　　 return self.stack[self.top]
　　

　　

　　

2.2 链栈的实现

　　栈的另一种存储表示方式是使用链式存储结构，因此也常称为链栈，其中 push 操作是通过在链表头部插入元素来实现的，pop 操作是通过从头部删除节点来实现的。

　　2.2.1 栈结点

　　栈的结点实现与链表并无差别：

　　

class Node:
　　 def __init__(self, data):
　　 self.data = data
　　 self.next = None
　　 def __str__(self):
　　 return str(self.data)
　　

　　2.2.2 栈的初始化

　　栈的初始化函数中，使栈顶指针指向 None，并初始化栈长：

　　

class Stack:
　　 def __init__(self):
　　 self.top = None
　　 # 栈中元素数
　　 self.length = 0
　　

　　2.2.3 求栈长

　　返回 length 的值用于求取栈的长度，如果没有 length 属性，则需要遍历整个链表才能得到栈长：

　　

 def size(self):
　　 return self.length
　　

　　2.2.4 判栈空

　　根据栈的长度可以很容易的判断栈是否为空栈：

　　

 def isempty(self):
　　 if self.length == 0:
　　 return True
　　 else:
　　 return False
　　

　　2.2.5 入栈

　　入栈时，在栈顶插入新元素即可：

　　

 def push(self, data):
　　 p = Node(data)
　　 p.next = self.top
　　 self.top = p
　　 self.length += 1
　　

　　由于插入元素是在链表头部进行的，因此入栈的时间复杂度为O(1)，在这种情况下链尾作为栈底 。

　　2.2.6 出栈

　　若栈不空，则删除并返回栈顶元素：

　　

 def pop(self):
　　 if self.isempty():
　　 raise IndexError("Stack Underflow!")
　　 ele = self.top.data
　　 self.top = self.top.next
　　 self.length -= 1
　　 return ele
　　

　　由于删除元素仅需修改头指针指向其 next 域，因此出栈的时间复杂度同样为O(1)。

　　2.2.7 求栈顶元素

　　若栈不空，返回栈顶元素即可，但栈顶元素并不会被删除：

　　

 def peek(self):
　　 if self.isempty():
　　 raise IndexError("Stack Underflow!")
　　 return self.top.data
　　

　　

　　

2.3 栈的不同实现对比

　　本节我们将对比栈的不同实现之间的异同：

　　顺序栈

　　

  • 操作的时间复杂度均为O(1)，列表的尾部作为栈顶
  • 栈满时需要进行动态的扩展，复制原栈元素到新栈中

　　链栈

　　

  • 操作的时间复杂度均为O(1)，链表的头部作为栈顶
  • 优雅的扩展，无需考虑栈满，需要额外的空间存储指针

　　

　　

3. 栈应用

　　接下来，我们首先测试上述实现的链表，以验证操作的有效性，然后利用实现的基本操作来解决实际算法问题。

　　

　　

3.1 顺序栈的应用

　　首先初始化一个顺序栈 stack，然后测试相关操作：

　　

# 初始化一个最大长度为4的栈
　　s = Stack(4)
　　print(栈空?, s.isempty())
　　for i in range(4):
　　 print(入栈元素：, i)
　　 s.push(i)
　　print(栈满?, s.isfully())
　　print(栈顶元素：, s.peek())
　　print(栈长度为：, s.size())
　　while not s.isempty():
　　 print(出栈元素：, s.pop())
　　

　　测试程序输出结果如下：

　　

栈空? True
入栈元素： 0
入栈元素： 1
入栈元素： 2
入栈元素： 3
栈满? True
栈顶元素： 3
栈长度为： 4
出栈元素： 3
出栈元素： 2
出栈元素： 1
出栈元素： 0

　　

　　

　　

3.2 链栈的应用

　　首先初始化一个链栈 stack，然后测试相关操作：

　　

# 初始化新栈
　　s = Stack()
　　print(栈空?, s.isempty())
　　for i in range(4):
　　 print(入栈元素：, i)
　　 s.push(i)
　　print(栈顶元素：, s.peek())
　　print(栈长度为：, s.size())
　　while not s.isempty():
　　 print(出栈元素：, s.pop())
　　

　　测试程序输出结果如下：

　　

栈空? True
入栈元素： 0
入栈元素： 1
入栈元素： 2
入栈元素： 3
栈顶元素： 3
栈长度为： 4
出栈元素： 3
出栈元素： 2
出栈元素： 1
出栈元素： 0

　　

　　

　　

3.3 利用栈基本操作实现复杂算法

　　匹配符号是指正确地匹配左右对应的符号(符号允许进行嵌套)，不仅每一个左符号都有一个右符号与之对应，而且两个符号的类型也是一致的，下标展示了一些符号串的匹配情况：

　　符号串是否匹配[]()()匹配[(())()不匹配{([]())}匹配(())[]}不匹配

　　为了检查符号串的匹配情况，需要遍历符号串，如果字符是 (、[ 或 { 之类的开始分隔符，则将其写入栈中；当遇到诸如 )、] 或 } 等结束分隔符时，则栈顶元素出栈，并将其与当前遍历元素进行比较，如果它们匹配，则继续解析符号串，否则表示不匹配。当遍历完成后，如果栈不为空，则同样表示不匹配：

　　

def isvalid_expression(expression):
　　 stack = Stack()
　　 symbols = {):(, ]:[, }:{}
　　 for s in expression:
　　 if s in symbols:
　　 if stack:
　　 top_element = stack.pop()
　　 else:
　　 top_element = #
　　 if symbols[s] != top_element:
　　 return False
　　 else:
　　 stack.push(s)
　　 return not stack
　　

　　由于我们只需要遍历符号串一边，因此算法的时间复杂度为O(n)，算法的空间复杂度同样为O(n)。

　　给定一链表(带有头结点) L : L0→L1→…→Ln，将其重排为：L0→Ln→L1→Ln−1 … 。

　　例如链表中包含 9 个元素，则下图现实了重排前后的链表元素情况：

　　

　　由于栈的先进后出原则，可以利用栈与原链表的配合进行重排，首次按遍历链表，将每个结点入栈；栈中元素的出栈顺序为原链表结点的逆序，然后交替遍历链表和栈，构建新链表。

　　

def reorder_list(L):
　　 p = L.head.next
　　 if p == None:
　　 return L
　　 stack = Stack()
　　 while p!= None:
　　 stack.push(p)
　　 p = p.next
　　 l = L.head.next
　　 from_head = L.head.next
　　 from_stack = True
　　 while (from_stack and l != stack.peek() or (not from_stack and l != from_head)):
　　 if from_stack:
　　 from_head = from_head.next
　　 l.next = stack.pop()
　　 from_stack = False
　　 else:
　　 l.next = from_head
　　 from_stack = True
　　 l = l.next
　　 l.next = None

　　该算法的时间复杂度和空间复杂度均为O(n)。

　　以上就是Python数据结构之栈详解的详细内容，更多关于Python 栈的资料请关注盛行IT软件开发工作室其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。

标签： python

相关文章阅读

  • mysql复合索引和组合索引,mysql组合索引数据结构
  • mysql复合索引和组合索引,mysql组合索引数据结构,Mysql之组合索引方法详解
  • mysql复合索引和组合索引,mysql复合索引数据结构
  • mysql复合索引和组合索引,mysql复合索引数据结构,MySQL的复合索引总结
  • b+树 多路搜索树,数据结构中树的分类
  • b+树 多路搜索树,数据结构中树的分类,数据结构-树（三）：多路搜索树B树、B+树
  • avl树的构造,avl树特性,数据结构之AVL树详解
  • 数据结构c语言哈夫曼树,c语言哈夫曼树的构造,使用C语言详解霍夫曼树数据结构
  • c语言数据结构算法编程库,数据结构 c语言中文网
  • c语言数据结构算法编程库,数据结构 c语言中文网,C语言编程数据结构基础详解小白篇
  • c++纸牌游戏,数据结构纸牌游戏c语言
  • c++纸牌游戏,数据结构纸牌游戏c语言,C语言实战之纸牌游戏
  • ,,c#解析jobject的数据结构
  • ,,javascript数据结构之多叉树经典操作示例【创建、添加、遍历、移除等】
  • ,,Java 数据结构与算法系列精讲之背包问题
    • 留言与评论（共有 条评论）
       
    验证码：