《数据结构与算法-Python语言描述》读书笔记（5）第5章栈和队列（关键词：数据结构/算法/Python/栈/队列）_栈和队列主要用于在计算过程中临时性地保存元素,称为()

第5章 栈和队列

5.1 概述

栈和队列主要用于在计算过程中保存临时数据。

5.1.1 栈、队列和数据使用顺序

栈和队列也是最简单的缓存结构，它们只支持数据项的存储和访问，不支持数据项之间任何关系。
- 栈：后进先出（Last In First Out，LIFO）
- 队列：先进先出（First In First Out，FIFO）
应该用线性表作为栈和队列的实现结构。

5.1.2 应用环境

5.2 栈：概念和实现

栈（stack，也称堆栈）是一种容器，可存入数据元素、访问元素、删除元素等。存入栈中的元素之间相互没有任何具体关系，只有到来的时间的先后顺序。在这里没有元素的位置、元素的前后顺序等概念。

栈的基本性质保证，在任何时刻可以访问、删除的元素都是在此之前最后存入的那个元素。因此，栈确定了一种默认元素访问顺序 ，访问时无需其他信息。

5.2.1 栈抽象数据类型

栈的抽象数据类型描述：

栈的线性表实现

用线性表的技术实现栈时，操作只在表的一端进行，不涉及另一端，更不涉及表的中间部分。

5.2.2 栈的顺序表实现

由于操作时，栈不满足需要（如空栈弹出）可以看做参数值错误，采用下面定义：

class StackUnderflow(ValueError): # 栈下溢（空栈访问）
    pass
1
2

下面是一个栈类的定义，其中用一个list类型的数据属性_elems作为栈元素存储区，把_elems的首端作为栈底，尾端作为栈顶：
（读者：抄代码。。）

class SStack():             # 基于顺序表技术实现的栈类
    def __init__(self):     # 用list对象_elems存储栈中元素
        self._elems = []    # 所有栈操作都映射到list操作

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

    def top(self):
        if self._elems == []:
            raise StackUnderflow("in SStack.top()")
        return self._elems[-1]

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

    def pop(self):
        if self._elems == []:
            raise StackUnderflow("in SStack.pop()")
        return self._elems.pop()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5.2.3 栈的链接表实现

（读者：建议仔细看书，理解“为什么需要链接栈”）
（读者：抄代码。。）

class LStack():     # 基于链接表技术实现的栈类，用LNode作为结点
    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("in LStack.top()")
        return self._top.elem

    def push(self, elem):
        slef._top = LNode(elem, self._top)

    def pop(self):
        if self._top is None:
            raise StackUnderflow("in LStack.pop()")
        p = self._top
        self._top = p.next
        return p.elem
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5.3 栈的应用

（读者：去看原书吧）

5.3.1 简单应用：括号匹配问题

（读者：请看书上的分析）
（读者：继续抄代码。。）

def check_parens(text):
    """括号配对检查函数，text是被检查的正文率"""
    parens = "()[]{}"
    open_parens = "([{"
    opposite = {")":"(", "]":"[", "}":"{"} # 表示配对关系的字典

    def parentheses(text):
        """括号生成器，每次调用返回text里的下一括号及其位置"""
        i, text_len = 0, len(text)
        while True:
            while i < text_len and text[i] not in parens:
                i += 1
            if i >= text_len:
                return
            yield text[i], i
            i += 1

        st = SStack() # 保存括号的栈

    for pr, i in parentheses(text): # 对text里各括号和位置迭代
        if pr in open_parens: # 对text里各括号和位置迭代
            st.push(pr)
        elif st.pop() != opposite[pr]: # 不匹配就是失败，退出
            print("Unmatching is found at", i, "for", pr)
            return False
        # else: 这是一次括号配对成功，什么也不做，继续
    print("ALL parentheses are correctly matched.")
    return True     
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

5.3.2 表达式的表示、计算和变换

（读者：我认为这一小节讲的是栈的应用的一个实例，暂时跳过。）

表达式和计算的描述

后缀表达式的计算

中缀表达式到后缀表达式的转换

中缀表达式的求值

5.3.3 栈与递归

阶乘函数的递归计算

栈与递归/函数调用

（读者：详细看书）
对于递归定义的函数，其执行中都有局部的状态，包括函数的形式参数和局部变量及其保存的数据。

栈与函数调用

递归与非递归

递归定义的阶乘函数，与之对应的非递归形式，用自己定义的栈模拟系统的运行栈。
（读者：抄代码）

def norec_fac(n): # 自己管理栈，模拟函数调用过程
    res = 1
    st = SStack()
    while n > 0:
        st.push(n)
        n -= 1
    while not st.is_empty():
        res *= st.pop()
    return res
1
2
3
4
5
6
7
8
9

递归函数与非递归函数

栈的应用：简单背包问题

求解背包问题的递归算法

（读者：抄代码。。）

def knap_rec(weight, wlist, n):
    if weight == 0:
        return True
    if weight < 0 or (weight > 0 and n < 1):
        return False
    if knap_rec(weight - wlist[n-1], wlist, n-1):
        print("Item " + str(n) + ":", wlist[n-1])
        return True
    if knap_rec(weight, wlist, n-1):
        return True
    else: return False
1
2
3
4
5
6
7
8
9
10
11

5.4 队列

队列（queue），也是一种容器，可存入、访问、删除元素。

5.4.1 队列抽象数据类型

（读者：仔细看书去！）

5.4.2 队列的链接实现

（读者：仔细看书去！）

5.4.3 队列的顺序表实现

（读者：仔细看书去！）

5.4.4 队列的list实现

一个具体实现示例：基于Python的list实现顺序表示的队列。

基本设计

队列可能由于空而无法deque等，为此定义一个异常类：

class QueueUnderflow(ValueError):
    pass
1
2

数据不变式

（读者：去看书吧）

队列类的实现

（读者：抄代码。。）

class SQueue():
    def __init__(self, init_len=8):
        self._len = init_len          # 存储区长度
        self._elems = [0]*init_len    # 元素存储
        self._head = 0                # 表头元素下标
        self._num = 0                 # 元素个数

    def is_empty(self):
        return self._num == 0

    def peek(self):
        if self._num == 0:
            raise QueueUnderflow
        return self._elems[self._head]

    def dequeue():
        if self._num == 0:
            raise QueueUnderflow
        e = self._elems[self._head]
        self._head = (self._head+1) % self.len
        self._num -= 1
        return e

    def enqueue(self, e):
        if self._num == self._len:
            self.__extend()
        self._elems[(self._head+self._num) % self._len] = e
        self._num += 1

    def __extend(self):
        old_len = self._len
        self._len *= 2
        new_elems = [0]*self._len
        for i in range(old_len):
            new_elems[i] = self._elems[(self._head+i)%old_len]
        self._elems, self._head = new_elems, 0  
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
31
32
33
34
35
36

5.4.5 队列的应用

文件打印

万维网服务器

Windows系统和消息队列

离散事件系统模拟

5.5 迷宫求解和状态空间搜索

（读者：跳过先。。）

5.5.1 迷宫求解：分析和设计

迷宫问题

迷宫问题分析

问题表示和辅助结构

5.5.2 求解迷宫的算法

迷宫的递归求解

栈和回溯法

迷宫的回溯法求解

算法实现

5.5.3 迷宫问题和搜索

状态空间搜索：栈和队列

基于队列的迷宫求解算法

基于栈和队列的搜索过程

深度和宽度有限搜索的性质

5.6 几点补充

5.6.1 几种与栈或队列相关的结构

双端队列

Python的deque类

5.6.2 几个问题的讨论

（读者：这里的讨论值得仔细阅读）

本章总结

练习

参考文献：
1.《数据结构与算法-Python语言描述》。