栈和队列是两种最广泛的数据结构,他们都是保存数据元素的容器,可以将元素存放个在其中,或者从其中取出元素。
容器是一大类具有数据保存作用的数据结构,它们保证存入的数据可以咋将来取到,而取出并删除的数据并不再存在于容器当中。
栈和队列主要用于在计算过程中临时的保存数据,所以栈和队列常被使用来作为缓冲存储或者缓存。和线性表和链表相比,栈和队列存入操作只需要保证元素的存入和将来取出元素的顺序,不需要记录或者保证新的存入的元素和容器之间的任何关系。

栈(stack)或者堆栈,是以一种容器,栈的基本操作是一个封闭的集合通常包括:

  • 创建空栈
  • 判断栈是否为空,is_empty()
  • 向栈中插入(推入、亚入,push)一个元素,push()
  • 从栈中删除(弹出,pop)一个元素,pop()
  • 取出当前(栈顶)的元素(并不删除),top()

栈可以实现为(可以看作)是只在一端插入和删除的表,进行插入或删除操作的一端称为栈顶,另一端称为栈底。
用线性表的技术实现栈时,由于只需要在一端操作,自然应该利用实现最方便而且能保证两个主要操作的效率最高的那一端,栈的实现通常有如下两种技术:

  • 采用连续表的方式实现,在后端插入和删除都是 O(1) 操作
  • 采用链接表的方式实现,在前端插入和删除都是 O(1) 操作

栈实现

在实现栈结构之前先定义一个异常

1
2
3
class StackUnderflow(ValueError):
"""栈下溢(空栈访问)"""
pass

连续表实现栈

采用连续表技术实现栈会面临连续表的各种问题:

  • 简单实用连续表,可能会出现栈满的情况
  • 采用动态连续表(分离式实现的连续表),栈满的时候就可以置换一个更大的存储区,这时将面临置换策略的问题,以及分期付款式的 O(1) 复杂性。

Python的内置对象 list 以及相关的操作实际上提供了一种栈功能,可以作为栈使用,实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class SStack:
def __init__(self):
self.elems = []

def is_empty(self):
return self.elems == []

def top(self):
if self.elems == []:
raise StackUnderflow
return self.elems[-1]

def push(self, elem):
self.elems.append(elem)

def pop(self):
if self.elems == []:
raise StackUnderflow
return self.elems.pop()

链接表实现栈

使用链接表实现栈之前先定义一个链接表节点的类

1
2
3
4
class LNode:
def __init__(self, elem, nxt=None)
self.elem = elem
self._next = nxt

借用 LNode 类实现一个链接栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class LStack:
def __init__(self):
self.top = None

def is_empty(self):
return self.top is None

def top(self):
if self.top is None:
raise StackUnderflow
return self.top.elem

def push(self, elem):
self.top = LNode(elem, self.top)

def pop(self):
if self.top is None:
raise StackUnderflow
current_node = self.top
self.top = current_node.next
return current_node.elem

栈的应用

括号配对问题

配对原则:

  • 遇到闭括号应该匹配此前遇到的最近尚未匹配的对应的开括号
  • 由于多种、多次、可能嵌套,为了检查配对,遇到的开括号必须保存
  • 由于括号可能嵌套,需要逐对匹配,闭括号应该金额前面最近的尚未有匹配的开括号匹配,后面括号应该和更前面的次近的括号匹配
  • 可以删除匹配的括号,为后面的匹配做好准备

后遇到并保存的开括号应该先删除,这就是后进先出,而且要按照出现的顺序,显然应该使用一个栈来保存开括号,详细操作如下:

  • 顺序检查所考虑的正文(一个字符串)里面的每一个字符
  • 忽略跳过无关字符
  • 遇到开括号时将其压入一个栈
  • 遇到闭括号的时候弹出栈顶元素与之匹配,匹配继续,遇到不匹配是检查以失败结束

定义一个函数完成检查任务,其中先定义一些检查用的数据和变量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def check_pares(text):
pares = "()[]{}"
open_pares = "([{"
opposite = {
")": "(",
"]": "[",
"}": "{",
}

def paretheses(text):
i, text_len = 0, len(text)
while True:
while i < text_len and text[i] not in pares:
i += 1
if i >= text_len:
return
yield text[i], i
i += 1

st = SStack()
for pr, i in paretheses(text):
if pr in open_pares:
st.push(pr)
elif st.pop() != oposite[pr]:
print("Unmatcing is found at ", i , " for ", pr)
return False
else:
print("index: ", i, " ", pr)
print("All paretheses are correctly matched.")
return True

栈与递归

递归的实现需要一个栈(运行栈),实现递归函数时

  • 每个具体的递归调用都有一些局部信息需要保存,语言的实现在运行栈上为函数的这次调用建立一个帧,其中保存有关信息
  • 函数执行总以栈顶帧作为当前帧,所有局部变量都在这里提现
  • 进入下一次的递归调用的时候,将建立新的帧
  • 从递归调用返回的时候,上层获得函数调用的结果,并弹出已经结束的调用对应的帧,然后回到上一层执行时的状态。

队列

队列(queue)也是一种容器,可以存入数据,访问数据,删除数据。队列基本操作也是一个封闭的集合,通常包括:

  • 创建空队列
  • 判断队列是否为空(可能还需要判断是否满)
  • 将一个元素放入队列(入队,enqueue)
  • 将一个元素从队列中删除(出队,dequeue)
  • 取出当前(最老的)元素(并不删除元素)

队列的结构

队列的链表实现

用线性表的技术实现队列,就利用元素位置的顺序关系表示入队时间的先后关系,先进先出需要在表的两端操作,实现起来比较麻烦一些。使用带尾结点的链表,后端插入为 O(1) 操作。

带有尾结点的链表

入队在表尾进行,出队在表头进行,都是 O(1) 的时间操作,实现很简单。