python中栈的标准实现方法,数据结构栈的基本运算

  python中栈的标准实现方法,数据结构栈的基本运算

  本文主要详细介绍Python数据结构和算法中的栈。本文中的示例代码非常详细,具有一定的参考价值。感兴趣的朋友可以参考一下,希望能帮到你。

  00-1010 0.学习目标1。栈的基本概念1.1栈的基本概念1.2栈的抽象数据类型1.3栈的应用场景2。实现栈2.1.1初始化栈2.1.2求栈长2.1.3判断栈空2.1.4判断栈满2.1.5进入栈2.1.1 .2.3求栈长2.2.4判断栈空2.2.5进入栈2.2.6退出栈2.3栈不同实现的比较3.1顺序栈的应用3.2链栈的应用3.3基本栈操作对复杂算法的总结

  

目录

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

  通过本节学习,应掌握以下内容:

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

  

0. 学习目标

  

1. 栈的基本概念

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

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

  栈的例子在现实中随处可见。如下图,球桶里的球形成一堆,每次只能从上面取出,放回去的时候放在上面。假设堆栈是s=(A0,A1,…,A N N)s=(A _ 0,A _ 1,…,A _ N) s=(A0,A1,…,An),那么堆栈的底部元素是a 0 a_0 a0,a n a_n an是顶部元素,堆栈中的元素按顺序堆叠。

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

  

1.1 栈的基本概念

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

  ADT堆栈:

  br /> 数据对象: D = a i ∣ a i ∈ D a t a T y p e , i = 1 , 2 , . . . , n , n ≥ 0 D={a_ia_i∈DataType, i=1,2,...,n,n\geq0} D=ai​∣ai​∈DataType,i=1,2,...,n,n≥0
 数据关系: R = < a i , a i + 1 > ∣ a i , a i + 1 ∈ D , i = 1 , 2 , . . . , n − 1 R={<a_{i},a_{i+1}>a_i,a_{i+1}∈D,i=1,2,...,n-1} R=<ai​,ai+1​>∣ai​,ai+1​∈D,i=1,2,...,n−1
       a 1 a_1 a1​为栈底元素, a n a_n an​为栈顶元素
 基本操作:
  1. __itit__(): 初始化栈
   创建一个空栈
  2. size(): 求取并返回栈中所含元素的个数 n
   若栈为空,则返回整数0
  3. isempty(): 判断是否为空栈
   判断栈中是否存储元素
  4. push(data): 入栈
   将元素 data 插入栈顶
  5. pop(): 出栈
   删除并返回栈顶元素
  4. peek(): 取栈顶元素
   返回栈顶元素值,但并不删除元素

  

  

  

1.3 栈的应用场景

  栈具有广泛的应用场景,例如:

  

  • 符号的匹配,具体描述参考第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 pop(self):

   if self.isempty():

   raise IndexError(Stack Underflow!)

   else:

   result = self.stack[self.top]

   self.top -= 1

   return result

  

  

  

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 pop(self):

   if self.isempty():

   raise IndexError("Stack Underflow!")

   ele = self.top.data

   self.top = self.top.next

   self.length -= 1

   return ele

  

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

  

  

2.2.6 出栈

  若栈不空,则删除并返回栈顶元素:

  

 def peek(self):

   if self.isempty():

   raise IndexError("Stack Underflow!")

   return self.top.data

  

  由于删除元素仅需修改头指针指向其next域,因此出栈的时间复杂度同样为 O ( 1 ) O(1) 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 利用栈基本操作实现复杂算法

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

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

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

  

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)。

  [2]给定一链表(带有头结点) L : L 0 → L 1 → … → L n,将其重排为: L 0 → L n → L 1 → L n − 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)。

  

  

总结

  本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注盛行IT软件开发工作室的更多内容!

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

相关文章阅读

  • 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 数据结构与算法系列精讲之背包问题
  • 留言与评论(共有 条评论)
       
    验证码: