线性结构

线性结构（linear structure）：

一种具有有序数据项的集合，其中每个数据项都有唯一的前驱（predecessor）和后继（successor）。

当前数据项的前一个与后一个数据项分别称为：当前数据项的直接前驱（intermediate predecessor）和直接后继（intermediate successor）。

任一元素的所有前驱构成其前缀（prefix），所有后继构成其后缀（suffix）。

数据有前后关系，类似列车、珠串的样子。
最为基本的线性结构统称为序列（sequence），根据其中数据项的逻辑次序与其物理存储地址的对应关系不同，又可进一步地将序列区分为向量（vector）和列表（list）。
- 向量：所有数据项的物理存放位置与其逻辑次序完全吻合，此时的逻辑次序也称作秩（rank）；
- 列表：逻辑上相邻的数据项在物理上未必相邻，而是采用间接定址的方式通过封装后的位置（position）相互引用。

基本线性结构

数组

大部分程序设计语言，都将数组（array）作为一种内置的数据类型，支持对一组相关元素的存储组织与访问操作。

具体地，若集合 $S$ 由 $n$ 个元素组成，元素类型相同，且各元素之间具有一个线性次序，则可将它们存放于起始地址A、物理位置连续的一段存储空间，并统称作数组，通常以A作为该数组的标识。数组A[]中的每一元素都唯一对应于某一下标编号。

那么，通过编号就可以直接访问到任一元素。

访问：包含读取、修改等基本操作；
直接：这些操作可以再常数时间内完成。

从起始地点，根据编号经过1次乘法和1次加法运算就可获取待访问元素的物理地址。

具体地，若数组A[]存放空间的起始地址为 $A$ ，且每个元素占用 $s$ 个单位的空间，则元素A[i]对应的物理地址 $= A + i \times s$ 。

因其中元素的物理地址与其下标之间满足这种线性关系，故也称之为线性数组。

向量（数组的一般性推广）

按照面向对象思想中的数据抽象原则，对数组结构做一般性推广，使得其以上特性更具普遍性——向量就是线性数组的一种抽象与泛化：

向量也是具有线性次序的一组元素构成的集合 $V = \{v_0, v_1, \cdots, v_{n-1}\}$ ，其中的元素分别由秩相互区分（物理存放位置与其逻辑次序完全吻合）；
若元素 $e$ 的前驱元素共计 $r$ 个，则其秩为 $r$ ；反之，通过秩 $r$ ，就可唯一确定元素 $e=v_r$ ；
这种特有的元素访问方式，称作循秩访问（call-by-rank）。

以找人类比，这种访问方式好比根据具体的城市名、街道名和门牌号（地址），直接找到某人。

经抽象之后，不再限定同一向量中的各元素都属于同一基本类型，换言之：

各元素本身可以是来自于更具一般性的某一类的对象；
各元素不一定同时具有某一数值属性，并不保证它们之间能够相互比较大小。

若向量中的所有元素不仅按线性次序存放，而且其数值大小也按此次序单调分布，则称作有序向量（sorted vector）。

（个人理解）Python的List数据结构就是这里所讲的向量。

这里介绍线性结构的概念时，主要引用了文献[1]（C++）。

后续如果提到List，若指Python提供的List类型，则会在其后增加后缀“（Python）”。

列表（链表的一般性推广）

列表中的元素也构成一个线性逻辑次序，但与向量不同的是，列表元素的物理地址可以任意。

为保证对列表元素访问的可行性，逻辑上互为前驱和后继的元素之间，应维护某种索引关系。

这种索引关系，可抽象地理解为：

被索引元素的位置（position）——循位置访问（call-by-position）；
亦或通往被索引元素的链接（link）——循链接访问（call-by-link）。

以找人类比，这种访问方式好比根据亲朋好友、亲朋好友的亲朋好友（无限套娃）找人。

⭐需要注意的是：

向量与列表的不同，表面上体现于对外的操作方式，但根源则在于其内部存储方式的不同。
向量中的秩同时对应于逻辑和物理次序，而列表中的位置仅对应于逻辑次序。

在设计或选用数据结构时，应从实际应用的需求出发，确定功能规范及性能指标。

比如，引入列表结构的目的，就在于弥补向量结构在解决某些应用问题时在功能及性能方面的不足。

数据结构支持的操作通常包含静态（从中获取信息）和动态（修改数据结构的局部或整体信息）两类：

向量：
- 获取向量长度、访问某个元素： $O(1)$ ；
- 插入元素、删除元素： $O(n)$ 。
  
  因向量中各元素物理地址连续（静态存储策略），在删除（插入）某个元素之后（之前），都需要移动后继元素的物理地址（动态操作）。
列表：
- 访问某个元素： $O(n)$ ；
  
  因不能直接获取到地址，只能顺着相邻元素之间的指针，从某一端出发逐个扫描各元素才能确定待访问元素的物理存储位置。
- 插入元素、删除元素： $O(1)$ 。
  
  列表中各元素的物理地址无任何限制（动态存储策略）。
  
  在其生命期内，该数据结构将随着内部数据的需要，相应地分配或回收局部的数据空间。如此，元素之间的逻辑关系得以保持，且无关物理地址次序。
  
  作为补偿，这种结构将通过指针或引用等机制来确定各元素的实际物理地址。
例如，链表（linked list）就是一种典型的动态存储结构。其中的数据，分散为一系列称作节点（node）的单位，节点之间通过指针相互索引和访问。那么，增加新节点或删除原有节点，只需在局部调整少量相关节点之间的指针。

因此，定义列表的ADT接口时，不仅要考虑列表本身的ADT接口，还要考虑列表节点的ADT接口。

这意味着采用动态存储策略，可以大大降低动态操作的成本。但在提高动态操作效率的同时，舍弃了原静态存储策略中循秩访问的方式，从而造成静态操作性能的下降。

有些地方将列表分为两种：array list与linked list。而array list其实可以对应这里介绍的向量。

通过上述对向量和列表的介绍，可以发现对数据结构的访问方式，应与其存储策略相一致。

另外，需要说明的是：

列表是链表结构的一般化推广，其中的元素称作节点（node），分别由特定的位置或链接指代；
列表与向量一样，在元素之间，也可定义前驱、直接前驱，以及后继、直接后继等关系；
相对于任意元素，列表也有定义对应的前缀、后缀等子集。

与有序向量一样，若列表中所有节点的逻辑次序与其大小次序完全一致，则称作有序列表（sorted list）。

并不是所有的编程语言都提供了列表数据类型，有时候需要自己实现。

列表ADT支持的接口

List()：创建一个空列表；
add(item)：添加一个数据项到列表中，假设item原先不存在于列表中；
remove(item)：从列表中移除item，此数据项应存在，列表被修改；
search(item)：判断列表是否存在item，返回布尔类型值；
isEmpty()：判断列表是否为空；
size()：报告列表的规模；
append(item)：添加一个数据项到表末尾；
index(item)：返回数据项在表中的位置；
insert(pos, item)：将数据项插入到位置pos，假设item原先不存在于列表中，同时原列表具有足够多数据项，能让item占据位置pos；
pop()：从列表末尾移除数据项，假设原列表至少有1个数据项；
pop(pos)：移除位置为pos的数据项，假设原列表存在位置pos。

用Python实现列表

这种列表数据结构要求保持数据项的前后相对位置，但这种前后位置的保持，并不要求数据项依次存放在连续的存储空间（循链接/位置访问），那么可采用链表结构。

在数据项之间建立链接指向，就可以保持其前后相对位置！

链表实现的最基本元素是节点Node。

需要注意的是：

第一个（表头）和最后一个数据项（表尾）需要显示标记；
每个节点至少包含两个信息：数据项data、指向下一个Node的引用信息（next）；
next为None表示没有下一个节点。

next为None的节点为表尾。

不是Node的data为None。

那么，链表节点的Python实现如下：

class Node:
    def __init__(self, init_data):
        self.data = init_data
        self.next = None
    
    def getData(self): # 访问数据项
        return self.data
    
    def getNext(self): # 访问引用信息
        return self.next
    
    def setData(self, new_data): # 修改数据项
        self.data = new_data
    
    def setNext(self, new_next): # 修改引用信息
        self.next = new_next

因此，可以采用链接节点的方式来实现链表。

如果想访问列表中的所有节点，就必须从第一个节点开始沿着链接遍历下去，直到next为None的那个节点。

所以，链表必须要有对第一个节点的引用信息：

设置一个属性head，保存对第一个节点的引用信息；

表头head并不是节点！！！
空表的head为None。

理解为：告诉系统这个表的应该从哪里开始读数据。空表就表示，没有下一项。

那么，该链表的初始化方法的Python实现如下：

class LinkedList:
    def __init__(self):
        self.head = None

随着数据项的加入，链表的head始终指向第一个节点。

注意：

若mylist = LinkedList()，链表对象本身（mylist）是不包含数据项的；

因为数据项只存在于节点Node中。
其所包含的head只是对首个节点Node的引用。

因此，判断空表的isEmpty()很容易实现，只要看head是不是None。

由链表结构可知，要访问链表所有数据项需要从表头head开始沿着next链接逐个向后访问，因此，要添加新数据项最快捷的位置是表头。

省去找位置这个步骤，开头就直接添加。

那么，该链表的add方法（时间复杂度 $O(1)$ ）的Python实现如下：

def add(self, item):
    temp = Node(item)
    temp.setNext(self.head)
    self.head = temp

该链表的size方法（时间复杂度 $O(n)$ ）的Python实现如下：

def size(self):
    current = self.head
    count = 0
    while current:
        count += 1
        current = current.next
    return count

该链表的search(item)方法（时间复杂度 $O(n)$ ）的Python实现如下：

def search(self, item):
    current = self.head
    found = False
    while current and not found:
        if current.getData() == item:
            found = True
        else:
            current = current.getNext()
    return found

该链表的remove(item)方法（时间复杂度 $O(n)$ ）的Python实现如下：

def remove(self, item):
    current = self.head
    previous = None
    found = False
    while not found: # 找到待删除节点，维护一个previous节点
        if current.getData() == item:
            found = True
        else:
            previous = current
            current = current.getNext()

    if previous == None:
        self.head = current.getNext() # 待删除节点位于表头
    else:
        previous.setNext(current.getNext()) # 待删除节点位于表中

其他ADT接口（如append、pop等）的实现方法这里不再一一给出。

有序列表ADT支持的接口

OrderedList()：创建一个空的有序列表；
add(item)：添加一个数据项到有序列表中，并保持整体顺序，假设item原先不存在于列表中；
remove(item)：从有序列表中移除item，此数据项应存在，有序列表被修改；
search(item)：判断有序列表是否存在item，返回布尔类型值；
isEmpty()：判断列表是否为空；
size()：报告列表的规模；
index(item)：返回数据项在表中的位置，此数据项应存在；
pop()：从有序列表末尾移除数据项，假设原列表至少有1个数据项；
pop(pos)：移除位置为pos的数据项，假设原列表存在位置pos。

用Python实现有序列表

列表中所有节点的逻辑次序与其大小次序完全一致。

实现有序列表时，数据项的相对位置取决于它们之间的”大小“比较。

并且，这种比较并不仅仅局限于数字，可适用于所有定义了比较操作符（如>）的数据类型。

这里以”整数数据项”且“数据项越小越靠近表头，数据项越大则越靠近表尾“为例。

链表节点Node的Python实现见上文。

有序链表OrderedList的Python实现注意如下：

对于isEmpty()、size()、remove()等与节点的次序无关的方法，实现同上文；
对于search()、add()等与节点的次序有关的方法则需要修改。

代码实现如下：

class OrderedList:
    def __init__(self):
        self.head = None
        
    def search(self, item):
        current = self.head
        found = False
        while current and not found:
            if current.getData() == item:
                found = True
            else:
                if current.getData() > item:
                    return found
                current = current.getNext()
        
        return found
    
    def add(self, item):
        current = self.head
        previous = None
        temp = Node(item)
        
        while current and temp.getData() > current.getData(): # 找到第一个比temp.data大的Node
            previous = current
            current = current.getNext()

        if not previous: # 待插入节点在表头
            temp.setNext(current)
            self.head = temp
        else: # 待插入节点在表中
            temp.setNext(current)
            previous.setNext(temp)

对于链表时间复杂度的分析，主要是看相应的方法是否涉及到链表的遍历。

常用线性结构

这里将介绍更为常用的两类数据结构：栈（stack）与队列（queue）。

这两类数据结构也属于线性结构。

相对于一般的序列结构，栈与队列的数据操作范围仅限于逻辑上的特定某端。

得益于其简洁性与规范性，它们既是构建更复杂、更高级数据结构的基础，也是算法设计的基本出发点，其也常常作为标准配置的基本数据结构。
相对于向量和列表，栈与队列的外部接口更为简化和紧凑，故亦可视为向量和列表的特例。

因此，利用面向对象编程的中继承与封装特性，容易实现栈与列表这样的数据结构。

因此，在介绍栈与列表时，一般不拘泥于对数据结构内部实现机制的展示，而是更多地从其外部特性出发，结合若干典型的实际问题介绍栈与队列的具体应用。

栈

栈（stack）是存放数据对象的一种特殊容器，其中的数据元素按线性的逻辑次序排列。在栈中，数据项的加入和移除操作都仅发生在同一端（栈顶）。

类似托盘的堆叠，只有顶端的盘子可以操作（没法从中间或底端抽出盘子）。

栈的两端称为：
- 栈顶（stack top）：可操作的一端；
栈底（stack base/bottom）：禁止操作的一端，亦称为盲端。
最新加入栈的数据项会被最新移除，因此，这种次序通常被称为后进先出（last-in-first-out，LIFO）；

这种”后进先出“针对的是最新加入的数据项！

距离栈底越近的数据项，停留在栈中的时间就越长；

这是一种基于数据项保存（停留）时间的次序，保存时间越短的数据离栈顶越近，而保存时间越长的离栈底越近。
具有反转次序的特性；

例如，浏览器的后退键，最先返回的是最近访问的页面；文档编辑器的撤销键，最先撤销的是最近的操作。

栈ADT支持的操作接口

Stack()：创建一个空栈，不包含任何数据项；
push(item)：将item加入栈顶，无返回值（入栈）；
pop()：将栈顶数据删除，并返回所删除数据，栈被修改（出栈）；
peek()：”窥视“并返回栈顶数据，但不移除，栈不被修改；
isEmpty()：判断栈是否为空；
size()：报告栈的规模。

操作样例如下表：

Stack Operation	Stack Contents	Return Value
`s = Stack()`	`[]`	`Stack object`
`s.isEmpty()`	`[]`	`True`
`s.push(4)`	`[4]`
`s.push('dog')`	`[4, 'dog']`
`s.peek()`	`[4, 'dog']`	`'dog'`
`s.push(True)`	`[4, 'dog', True]`
`s.size()`	`[4, 'dog', True]`	`3`
`s.isEmpty()`	`[4, 'dog', True]`	`False`
`s.push(8.4)`	`[4, 'dog', True, 8.4]`
`s.pop()`	`[4, 'dog', True]`	`8.4`
`s.pop()`	`[4, 'dog']`	`True`
`s.size()`	`[4, 'dog']`	`2`

用Python实现栈

既然栈可以视为序列的特例，利用Python的面向对象机制，可以使用Python自带的数据结构来实现栈：

将Stack实现为Python的一个class；
采用Python自带的List数据结构实现；
那么，Stack的两端可对应List（Python）进行设置：将List（Python）的任意一端（index = 0或-1）设为栈顶。

例如，这里选择List（Python）的右端（末端，即index = -1）作为栈顶，如此，对栈的push和pop操作均可使用List（Python）的append和pop来实现。

class Stack:
    def __init__(self):
        self.items = []
    
    def isEmpty(self):
        return self.items == []
    
    def push(self, item):
        return self.items.append(item)
    
    def pop(self):
        return self.items.pop()
    
    def peek(self):
        return self.items[-1]
    
    def size(self):
        return len(self.items)

当然，也可将List（Python）的左端（首端，即index = 0）作为栈顶。不同的实现方案均保持了ADT接口的稳定性，但性能是不同的：

栈顶为List（Python）首端的版本，其push和pop的复杂度为 $O(n)$ ；
栈顶为List（Python）尾端的版本，其push和pop的复杂度为 $O(1)$ 。

栈的应用

简单括号匹配

括号的使用必须遵循平衡规则：

每个开括号都要对应一个闭括号；
每对开闭括号要正确的嵌套。

思路：从左到右扫描括号串，最近输入的左括号应该匹配最先遇到的右括号；这种次序反转的识别，正好符合栈的特性。

那么具体做法就是：

对指定的括号字符串从左往右扫描，扫描到开括号时，将其加入栈；

即，这个栈只存储开括号。
扫描到闭括号时，将加入栈中的最近括号删除；

”最近“指的是最新加入栈的开括号；

因为扫描是从左往右进行的，那么先扫描到闭括号时，其对应的开括号就应该是栈顶的那个开括号，若栈中没有开括号与之匹配，说明这个字符串的括号不匹配。
匹配状态即：没有闭括号，且栈为空。

def par_checker(symbol_str):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbol_str) and balanced:
        if symbol_str[index] == '(':
            s.push(symbol_str[index]) # 栈只存开括号
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()
        index = index + 1
    if balanced and s.isEmpty():
        return True
    else:
        return False

通用括号匹配考虑的就不仅仅是小括号()，还有[]{}。

那么程序修改为：

def par_checker(symbol_str):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbol_str) and balanced:
        if symbol_str[index] in '([{': # Modification，从原本的小开括号判断变为通用开括号判断
            s.push(symbol_str[index])
        else:
            if s.isEmpty():
                balanced = False
            else:
                top = s.pop()
                if not matches(top, symbol_str[index]): # Modification，看看pop掉的开括号是否与当前读取的闭括号匹配
                    balanced = False
        index = index + 1
    if balanced and s.isEmpty():
        return True
    else:
        return False
    
def matches(open_par, closed_par):
    open_pars = '([{'
    closed_pars = ')]}'
    return open_pars.index(open_par) == closed_pars.index(closed_par) # Modification，利用反查来看开闭括号是否匹配（⭐）

十进制转换为二进制

如， $(233)_{10}$ 对应的二进制数为 $(11101001)_{2}$ ：

$(233)_{10} = {\color{red} 2}\times 10^{2} + {\color{red} 3}\times 10^{1} + {\color{red} 3}\times 10^{0} \\ (11101001)_{2} = {\color{red} 1}\times 2^{7} + {\color{red} 1}\times 2^{6} + {\color{red} 1}\times 2^{5} + {\color{red} 0}\times 2^{4} + {\color{red} 1}\times 2^{3} + {\color{red} 0}\times 2^{2} + {\color{red} 0}\times 2^{1} + {\color{red} 1}\times 2^{0}$

十进制转换为二进制，采用的是“除以2求余数”的算法：

$\begin{aligned} 2 \quad | \underline{\quad 233 \quad}\quad\quad\quad\quad\quad\quad\quad & \text{Remainder} & \\ 2 \quad | \underline{\quad 116 \quad}\quad\quad\quad\quad\quad\quad & \quad\quad 1 & \text{High}\\ 2 \quad | \underline{\quad 58 \quad}\quad\quad\quad\quad\quad\quad & \quad\quad 0 & \uparrow \quad\\ 2 \quad | \underline{\quad 29 \quad}\quad\quad\quad\quad\quad & \quad\quad 0 & |\quad\\ 2 \quad | \underline{\quad 14 \quad}\quad\quad\quad\quad & \quad\quad 1 & |\quad\\ 2 \quad | \underline{\quad 7 \quad}\quad\quad\quad & \quad\quad 0 & |\quad\\ 2 \quad | \underline{\quad 3 \quad}\quad\quad & \quad\quad 1 \ & |\quad\\ 2 \quad | \underline{\quad 1 \quad}\quad & \quad\quad 1 & |\quad\\ 0 \quad\quad& \quad\quad1 & \text{Low}\\ \end{aligned}$

将整数不断除以2，每次得到的余数就是由低位到高位的二进制位。

因为得到的余数是从低到高的次序，而输出则是从高到低的次序，这种次序反转正好符合栈的特性。

利用push()加入余数，利用pop输出结果。

def divide_by_2(dec_number):
    rem_stack = Stack()
    
    while dec_number > 0:
        rem = dec_number % 2 # 求余数
        rem_stack.push(rem)
        dec_number = dec_number // 2 # 求整数
    
    bin_str = ''
    while not rem_stack.isEmpty():
        bin_str = bin_str + str(rem_stack.pop())
        
    return bin_str

除了二进制，计算机中另外两种常用的进制是八进制和十六进制。

二进制：0、1

八进制：0、1、2、3、4、5、6、7

十六进制：0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F

def divide_by_n(dec_number, n):
    rem_stack = Stack()
    digits = '0123456789ABCDEF' # Modification，增加一个用于查询对应数值的表
    
    while dec_number > 0:
        rem = dec_number % n # Modification，更改了基底
        rem_stack.push(rem)
        dec_number = dec_number // n # Modification，更改了基底
    
    bin_str = ''
    while not rem_stack.isEmpty():
        bin_str = bin_str + digits[rem_stack.pop()] # Modification，直接查找对应符号即可，不用再str()转变
        
    return bin_str

表达式转换

中缀表达式：操作符（operator）介于操作数（operand）中间的表达式，即A+B*C。

但有时会引起混淆，如A+B*C是先算加法还是乘法？因此，为了消除这种混淆，引入了优先级的概念，规定如下：

高优先级的操作符先计算；
相同优先级的操作符从左到右依次计算；
用引入括号来表示强制优先级，嵌套的括号中，内层括号的优先级更高。

全括号中缀表达式：在所有表达式两边都加上括号。

A+B*C+D表示为：((A+(B*C))+D)

前缀表达式：将操作符移动到操作数之前，即A+B变为了+AB。

后缀表达式：将操作符移动到操作数之后，即A+B变为了AB+。

中缀表达式	全括号中缀表达式	前缀表达式	后缀表达式
`A + B`	`(A + B)`	`+ A B`	`A B +`
`A + B * C`	`(A + (B * C))`	`+ A * B C`	`A B C * +`
`(A + B) * C`	`((A + B) * C)`	`* + A B C`	`A B + C *`
`A + B * C + D`	`((A + (B * C)) + D)`	`+ + A * B C D`	`A B C * + D +`
`(A + B) * (C + D)`	`((A + B) * (C + D))`	`* + A B + C D`	`A B + C D + *`

每个部分都逐渐换成对应的前（后）缀表达式。

通过观察上表，可以发现：

在前（后）缀表达式中，操作符的次序完全决定了运算的次序，不会有运算混淆的情况出现；

观察全括号中缀表达式和前（后）缀表达式的区别，可以发现：

对比全括号中缀和前缀表达式：将操作符移动到左括号的位置上，并去掉右括号，即为前缀表达式；
对比全括号中缀和后缀表达式：将操作符移动到右括号的位置上，并去掉左括号，即为后缀表达式；

那么，无论表达式多复杂，当需要转换成前（后）缀表达式时，只需要两个步骤：

将中缀表达式转换为全括号形式；
移动操作符到对应括号位置，再删除无用的括号。

为了避免另外额外的第一步缀转全括号操作，这里考虑通用的中缀转后缀算法。

在中缀转后缀的算法中，就应该考虑：

操作符比操作数要晚输出；

在扫描到对应的第二个操作数之前，需要把操作符先保存起来。
这些暂存的操作符，由于优先级的规则，可能要反转次序输出；

A + B * C，对应的后缀形式为A B C * +，+虽然先出现，但是优先级比*低，因此+要等*处理完之后才能再处理。；

(A + B) * C，对应的后缀形式为A B + C *，可以看到+的输出比*要早，因为括号使得+的优先级提高了。

因此，这种反转特性，可以用栈来保存暂时未处理的操作符：

从左往右扫面中缀表达式；
当遇到操作数，则保存到后缀表达式列表末尾；
当遇到左括号，则保存在栈中；
当遇到右括号，则反复弹出栈中的操作符，直到碰到左括号；
当遇到操作符，跟栈顶的操作符比较优先级，若优先级低于栈顶中的操作符，则反复弹出栈顶操作符至后缀表达式列表末尾；然后再将所遇到的操作符则存入栈中；
当扫描完后，将栈中剩余的操作符依次弹出，添加到后缀表达式列表末尾；
最后输出后缀表达式。

约定中缀表达式是由空格隔开的一系列单词（token）构成：

操作符单词：*、/、+、-、(、)。
操作数则是单字母标识符A、B、C等。

def infix_to_postfix(infix_expr):
    priority = {} # 设置好优先级
    priority["("] = 1
    priority["+"] = 2
    priority["-"] = 2
    priority["*"] = 3
    priority["/"] = 3
    
    op_stack = Stack() # 创建空栈
    infix_expr_list = infix_expr.split() # 分解成各个字符
    postfix_expr_list = []
    index = 0
    while index < len(infix_expr_list): # 扫描中继表达式
        if infix_expr_list[index] not in "+-*/()": # 遇到操作数
            postfix_expr_list.append(infix_expr_list[index])
        elif infix_expr_list[index] == "(": # 遇到左括号
            op_stack.push(infix_expr_list[index])
        elif infix_expr_list[index] == ")": # 遇到右括号
            top_token = op_stack.pop()
            while top_token != "(":
                postfix_expr_list.append(top_token)
                top_token = op_stack.pop()
        else: # 遇到操作符
            while (not op_stack.isEmpty()) and priority[infix_expr_list[index]] < priority[op_stack.peek()]:
                postfix_expr_list.append(op_stack.pop())
            op_stack.push(infix_expr_list[index])
        index = index + 1
        
    while not op_stack.isEmpty():
        postfix_expr_list.append(op_stack.pop())
        
    postfix_expr = " "
    return postfix_expr.join(postfix_expr_list) # 返回后缀表达式

队列

与栈一样，队列（queue）也是存放数据对象的一种容器，其中的数据对象也按线性的逻辑次序排列。

队列结构的插入与移除操作分别被限制于队列的两端：

新数据项的添加总发生在一端，通常称为队尾（rear）；
现存数据项的移除总发生在另一端，通常称为队端（front）。

队列中的元素就像水管里的水、滑滑梯上的小朋友、排队中的人、羽毛球桶中的羽毛球。

这种次序通常被称为先进先出（first-in-firt-out，FIFO），或先到先服务（first-come first-served）；

这种“先进先出”针对的是最早加入的数据项！
队列仅有一个入口和一个出口。

计算机科学中，使用队列的常见例子：打印队列、进程调度、键盘缓冲。

队列ADT支持的操作接口

Queue()：创建一个空队列，返回值为Queue对象；
enqueue(item)：将数据项item添加到队尾（入队）；
dequeue()：从队首移除数据项，返回值为队首数据项，队列被修改（出队）；
isEmpty()：判断队列是否为空；
size()：报告队列的规模。

用Python实现队列

例如，这里选择List（Python）的右端（末端，即index = -1）作为队列的首端，如此，队列的enqueue操作可以用List（Python）的insert来实现；队列的dequeue操作可以用List（Python）的pop来实现。

class Queue:
    def __init__(self):
        self.items = []
    
    def isEmpty(self):
        return self.items == []
    
    def enqueue(self, item):
        return self.items.insert(0, item)
    
    def dequeue(self):
        return self.items.pop()
    
    def size(self):
        return len(self.items)

当然，也可将List的左端（首端，即index = 0）作为栈顶。

不同的实现方案保持了ADT接口的稳定性，但是性能是不同的：

队列首端为List（Python）末端的版本，其enqueue的复杂度为 $O(n)$ ，dequeue的复杂度为 $O(1)$ ；
队列首端为List（Python）首端的版本，其enqueue的复杂度为 $O(1)$ ，dequeue的复杂度为 $O(n)$ 。

队列的应用（例题）

热土豆问题（约瑟夫问题）

传烫手的热土豆，鼓声停的时候，手里有土豆的小孩就要出列，看哪个小孩最后一个出列。

输入参数：

游戏人数name_list
传土豆次数num

输出参数：

最后剩下的小孩名

思路：

队列中的元素即为参加游戏的小孩名字；
队首对应的小孩表示拥有土豆（⭐）；

有种山不动水动的感觉。
队首的小孩跑去队尾即代表传递一次。

def hot_potato(name_list, num):
    sim_queue = Queue()
    for name in name_list:
        sim_queue.enqueue(name)
        
    while sim_queue.size() > 1:
        for i in range(num):
            circ_person = sim_queue.dequeue() # 一次传递
            print(circ_person)
            sim_queue.enqueue(circ_person)
            
        quit_person = sim_queue.dequeue() # 达到传递次数后，刷掉一个人
        
    winner = sim_queue.dequeue() # 最后剩下的一个人
    return winner

双端队列（队列的扩展）

与队列类似，但在双端队列（deque）中，数据项既可以从队首加入，也可以从队尾加入；同理，数据项也可以从两端移除。

双端队列集成了栈和队列的能力。

双端队列ADT支持的操作接口

Deque()：创建一个空双端队列；
addFront(item)：将item加入队首；
addRear(item)：将item加入队尾；
removeFront()：从队首移除数据项，返回值为移除的数据项；
removeRear()：从队尾移除数据项，返回值为移除的数据项；
isEmpty()：判断双端队列是否为空；
size()：报告双端队列的规模。

用Python实现双端队列

采用List（Python）实现：

Deque的首端：List（Python）下标为-1的位置；
Deque的尾端：List（Python）下标为0的位置。

class Deque:
    def __init__(self):
        self.items = []
        
    def isEmpty(self):
        return self.items == []
    
    def addFront(self, item):
        self.items.append(item)
        
    def addRear(self, item):
        self.items.insert(0, item)
        
    def removeFront(self):
        self.items.pop()
        
    def removeRear(self):
        self.items.pop(0)
        
    def size(self):
        return len(self.items)

操作复杂度：

addFront和removeFront： $O(1)$ ；
addRear和removeRear： $O(n)$ 。

双端队列的应用（例题）

回文词判定

回文词：正读和反读都一样的词。

如radar、madam、toot；上海自来水来自海上

用双端队列就很容易解决：

将回文词加入deque；
队首和队尾同时移除字符，判定是否相同；
直到双端队列中只剩下0或1个字符。

def pal_checker(a_string):
    pal_deque = Deque()
    
    for char in a_string:
        pal_deque.addFront(char)
    
    is_pal = True
    
    while pal_deque.size() > 1:
        front_char = pal_deque.removeFront()
        rear_char = pal_deque.removeRear()
        if front_char != rear_char:
            is_pal = False
            return is_pal
    
    return is_pal