编程教程 - 技术改变世界

Python编程技术

Python数据结构与算法中的栈详解

0. 学习目标

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

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

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

1. 栈的基本概念

1.1 栈的基本概念

栈 (Stack) 是限定仅在序列一端执行插入和删除操作的线性表，对于栈而言，可进行操作的一端称为栈顶 (top)，而另一端称为栈底 (bottom)。如果栈中不含任何元素则称其为空栈。

栈提供了一种基于在集合中的时间来排序的方式，最近添加的元素靠近顶端，旧元素则靠近底端。最新添加的元素被最先移除，这种排序原则也称为后进先出 (last in first out,LIFO) 或先进后出 (fast in last out,FILO)。

栈在现实中的例子随处可见，如下图所示，球桶中的球构成了一个栈，每次只能从顶部取出一个，放回时也只能置于顶部。假设栈为 S = ( a 0 , a 1 , … , a n ) S=(a_0, a_1, …, a_n) S=(a0,a1,…,an)，则栈底元素为 a 0 a_0 a0， a n a_n an 为栈顶元素，栈中元素按的顺序入栈 (push)，而栈顶元素是第一个退栈 (pop) 的元素。

栈示意图

通过观察元素的添加和移除顺序，就可以快速理解栈所蕴含的思想。下图展示了栈的入栈和出栈过程，栈中元素的插入顺序和移除顺序恰好是相反的。

栈的反转特性

1.2 栈抽象数据类型

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

ADT Stack:
数据对象： D = a i ∣ a i ∈ D a t a T y p e , i = 1 , 2 , . . . , n , n ≥ 0 D={a_i|a_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)。

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注编程教程的更多内容!

下一节：Python获取网络图片和视频的示例代码

Python编程技术

1.网络获取Google图像1.1 google_images_downloadPython 是一种多用途语言，广泛用于脚本编写。我们可以编写 Python 脚本来自动化日常事务。假设我 ...

一起来学习Python的元组和列表

Python获取网络图片和视频的示例代码