一、栈的定义和特性

（一）栈的定义

栈是一种线性数据结构，栈是元素的有序集合，其元素的顺序取决于添加顺序或移除顺序，它有两端，称作顶端和底端，即对应栈的栈顶和栈底，栈中元素的添加称为入栈，而元素的移除称为出栈，栈中元素的添加操作和移除操作都发生在其顶端。

栈中最后添加的元素将最先被移除，栈的排序原则被称作LIFO，即后进先出，最先添加的元素在栈底，它最后最移出。

简单来说，可比喻为几本书或砖头叠在一起，需要依次从上至下一本一本地拿出书，最下面的那本书最后被拿出。

（二）栈的反转特性

栈的反转特性最明显的例子体现在浏览器的返回键中，我们知道在浏览网页时，实际上的网页是文件，是由 HTML 构成的文件，每个网页文件都有一个唯一的URL（即统一资源定位符）。

当从当前网页跳转到另一个网页页面时，当前浏览的网页处于栈顶，而之前的网页相对当前网页位于栈底，也就是这些网页的URL都被存放在一个栈中。

二、实现分析步骤

通过Python中的类与对象，在类中定义几个方法，且使用列表来实现栈的相关操作，栈的操作有：

1、创建一个空栈，通过构造方法创建一个空列表；

class Stack:
    def __init__(self):
        self.items = []  # 创建一个空栈，它不需要参数，且会返回一个空栈

2、向栈（栈顶）中添加元素，通过列表的append()或insert()实现添加新的元素至栈中。（若将列表的尾部作为栈的顶端，则通过append()实现；而若将列表的头部作为栈的顶端，则通过insert()实现，insert()第一个参数表示索引位置，第二个参数即要添加的元素，由于是向栈顶添加元素，则第一个参数为0（列表的下标从0开始））；

def push(self, item):
        self.items.append(item)  # 将一个元素添加到栈的顶端，它需要一个参数item，且无返回值【self.items.insert(0,item)】

3、删除栈顶元素，通过列表的pop()实现删除栈顶的元素。（若将列表的尾部作为栈的顶端，pop()内无参数，即此时删除列表的末尾元素，也就是栈的顶端元素；而若将列表的头部作为栈的顶端，则pop(0)表示移除列表中下标为0的元素）；

def pop(self):
        return self.items.pop()  # 将栈顶的元素移除，它不需要参数，但会返回顶端的元素，且修改栈的内容【return self.items.pop(0)】

4、返回栈顶元素，若将列表的尾部作为栈的顶端，则通过len()先取得列表的长度，由于下标是从0开始，所以要减1；而若将列表的头部作为栈的顶端，则直接通过索引列表下标为0的元素）；

def peek(self):
        return self.items[len(self.items) - 1]  # 返回栈顶端的元素，它不需要参数，不会修改栈的内容【return self.items[0]】

5、检查栈是否为空，通过比较运算符“==”比较栈是否为空，若为空，则返回布尔值False，若不为空，则返回True；

def isEmpty(self):
        return self.items == []  # 检查栈是否为空，它不需要参数，且会返回一个布尔值

6、返回栈中元素数目，通过len()取列表的长度，即返回栈中元素的数目。

def size(self):
        return len(self.items)  # 返回栈中元素的数目，它不需要参数，且会返回一个整数

三、栈的Python实现代码

将列表的尾部作为栈的顶端：

# 通过列表实现栈的操作（以列表尾部作为栈的顶端）
class Stack:
    def __init__(self):
        self.items = []  # 创建一个空栈，它不需要参数，且会返回一个空栈
    def isEmpty(self):
        return self.items == []  # 检查栈是否为空，它不需要参数，且会返回一个布尔值
    def push(self, item):
        self.items.append(item)  # 将一个元素添加到栈的顶端，它需要一个参数item，且无返回值
    def pop(self):
        return self.items.pop()  # 将栈顶的元素移除，它不需要参数，但会返回顶端的元素，且修改栈的内容
    def peek(self):
        return self.items[len(self.items) - 1]  # 返回栈顶端的元素，它不需要参数，不会修改栈的内容
    def size(self):
        return len(self.items)  # 返回栈中元素的数目，它不需要参数，且会返回一个整数
s = Stack()  # s是一个新创建的空栈，创建一个对象，即对象名称=类名称()
print(s.isEmpty())  # 检查栈是否为空
s.push("wddd")
s.push("w")
s.push(123)
print(s.peek())  # 返回栈最顶端的元素
print(s.size())  # 返回当前栈中的元素数目
s.push(False)
print(s.size())
print(s.isEmpty())
s.push(0.2)
print(s.pop())  # 删除栈顶元素
print(s.peek())
print(s.size())

运行结果如下：

四、栈的应用

（一）匹配圆括号

我们知道圆括号由左括号“(”和右括号“)”进行匹配的，通过创建一个空栈来保存括号，从左至右依次处理括号，若匹配到左括号则通过push()方法将其添加至栈中，而若匹配到右括号则通过pop()方法删除栈顶元素，最后若所有括号都匹配则栈为空，程序会返回一个布尔值来表示括号是否匹配。

程序完整代码及解析如下：

# 通过列表实现栈的操作（以列表尾部作为栈的顶端）
class Stack:
    def __init__(self):
        self.items = []  # 创建一个空栈，它不需要参数，且会返回一个空栈
    def isEmpty(self):
        return self.items == []  # 检查栈是否为空，它不需要参数，且会返回一个布尔值
    def push(self, item):
        self.items.append(item)  # 将一个元素添加到栈的顶端，它需要一个参数item，且无返回值
    def pop(self):
        return self.items.pop()  # 将栈顶的元素移除，它不需要参数，但会返回顶端的元素，且修改栈的内容
    def peek(self):
        return self.items[len(self.items) - 1]  # 返回栈顶端的元素，它不需要参数，不会修改栈的内容
    def size(self):
        return len(self.items)  # 返回栈中元素的数目，它不需要参数，且会返回一个整数
# 定义一个有参函数Par_Checker()，其参数parenthesis是输入的括号
def Par_Checker(parenthesis):
    s = Stack()  # s是一个新创建的空栈，创建一个对象
    balanced = True
    index = 0
    while index < len(parenthesis) and balanced:  # 若当前索引值小于输入的括号的总长度且变量balanced的值为正确时，一直执行while循环下去
        symbol = parenthesis[index]# 取输入的括号赋给变量symbol，变量index的初值为0
        if symbol == "(":  # 若匹配到左括号则通过push()方法将其添加至栈中
            s.push(symbol)
        else:
            if s.isEmpty():  # 检查栈是否为空，它不需要参数，会返回一个布尔值
                balanced = False  # 栈为空，变量balanced的值变为False
            else:
                s.pop()  # 若匹配到右括号则通过pop()方法删除栈顶元素
        index = index + 1  # 索引加一，对下一个括号进行检查
    if balanced and s.isEmpty():  # 如果栈为空，则代表所有括号都匹配成功
        return True
    else:
        return False
#测试
print(Par_Checker("(()(("))
print(Par_Checker(")(("))
print(Par_Checker("(()(()))"))

运行结果如下：

（二）匹配符号

通过改进匹配圆括号的程序从而实现对符号“()”、“[]”和“{}”的匹配，在原有的基础上加了一个函数matches()，该函数检查每一个从栈顶移除的符合是否与当前的右符合相匹配，匹配符号的程序完整代码及解析如下：

# 通过列表实现栈的操作（以列表尾部作为栈的顶端）
class Stack:
    def __init__(self):
        self.items = []  # 创建一个空栈，它不需要参数，且会返回一个空栈
    def isEmpty(self):
        return self.items == []  # 检查栈是否为空，它不需要参数，且会返回一个布尔值
    def push(self, item):
        self.items.append(item)  # 将一个元素添加到栈的顶端，它需要一个参数item，且无返回值
    def pop(self):
        return self.items.pop()  # 将栈顶的元素移除，它不需要参数，但会返回顶端的元素，且修改栈的内容
    def peek(self):
        return self.items[len(self.items) - 1]  # 返回栈顶端的元素，它不需要参数，不会修改栈的内容
    def size(self):
        return len(self.items)  # 返回栈中元素的数目，它不需要参数，且会返回一个整数
# 定义一个有参函数matches()，该函数检查每一个从栈顶移除的符合是否与当前的右符合相匹配
def matches(left, right):
    left = "([{"
    right = ")]}"
    return left.index(left) == right.index(right)  # index()用于检查子字符串是否在字符串中
# 定义一个有参函数Par_Checker()，其参数parenthesis是输入的括号
def Par_Checker(parenthesis):
    s = Stack()  # s是一个新创建的空栈，创建一个对象
    balanced = True
    index = 0
    while index < len(parenthesis) and balanced:  # 若当前索引值小于输入的符号的总长度且变量balanced的值为正确时，一直执行while循环下去
        symbol = parenthesis[index]  # 取输入的符号赋给变量symbol，变量index的初值为0
        if symbol in "([{":  # 若匹配到左符号则通过push()方法将其添加至栈中
            s.push(symbol)
        else:
            if s.isEmpty():  # 检查栈是否为空，它不需要参数，会返回一个布尔值
                balanced = False  # 栈为空，变量balanced的值变为False
            else:
                top = s.pop()  # 若匹配到右符号则通过pop()方法删除栈顶元素
                if not matches(top, symbol):  # 调用matches()函数检查每一个从栈顶移除的符合是否与当前的右符合相匹配，即若未匹配执行以下语句
                    balanced = False
        index = index + 1  # 索引加一，对下一个符号进行检查
    if balanced and s.isEmpty():  # 如果栈为空，则代表所有符号都匹配成功
        return True
    else:
        return False
#测试
print(Par_Checker("(({)("))
print(Par_Checker("]("))
print(Par_Checker("{([]})"))

运行结果如下：

（三）模2除法（十进制转二进制）

我们知道将十进制转二进制可以通过模2除法的方法实现，也就是除2取余，逆序排列，如下十进制25转换为二进制：

最后可得25=0001 1001=11001：

我们从步骤上可以看出，计算出的第一个余数是得到结果的最后一位，而最后计算出的余数是结果的第一位，所以可以将得到的二进制数看成一系列数字，创建一个空栈，通过一系列方法得到二进制数字。

模2除法的程序完整代码及解析如下：

# 通过列表实现栈的操作（以列表尾部作为栈的顶端）
class Stack:
    def __init__(self):
        self.items = []  # 创建一个空栈，它不需要参数，且会返回一个空栈
    def isEmpty(self):
        return self.items == []  # 检查栈是否为空，它不需要参数，且会返回一个布尔值
    def push(self, item):
        self.items.append(item)  # 将一个元素添加到栈的顶端，它需要一个参数item，且无返回值
    def pop(self):
        return self.items.pop()  # 将栈顶的元素移除，它不需要参数，但会返回顶端的元素，且修改栈的内容
    def peek(self):
        return self.items[len(self.items) - 1]  # 返回栈顶端的元素，它不需要参数，不会修改栈的内容
    def size(self):
        return len(self.items)  # 返回栈中元素的数目，它不需要参数，且会返回一个整数
# 创建一个有参函数DivideBy2()，参数为一个十进制数
def DivideBy2(decNumber):
    s = Stack()  # s是一个新创建的空栈，创建一个对象
    while decNumber > 0:  # 若输入的十进制大于0，则执行while循环一直下去
        rem = decNumber % 2  # 参数rem为余数，即十进制数每次除2得到的余数
        s.push(rem)  # 通过push()方法将得到的余数添加到栈的顶端
        decNumber = decNumber // 2  # 输入的十进制整数除2，即十进制与2的整数商
    binString = ""  # 定义一个空字符串binString用于存放二进制数字
    while not s.isEmpty():  # 若栈不为空，则执行while循环一直下去
        binString = binString + str(s.pop())  # 通过pop()方法将栈顶的元素移除，通过str()转换为字符串类型并通过"+"拼接赋值给字符串binString
    return binString  # 得到的二进制值
print(DivideBy2(17))
print(DivideBy2(255))
print(DivideBy2(1024))
print(DivideBy2(2022))

运行结果如下：

（四）进制转换

根据十进制转二进制的程序代码可以进一步改进，首先该函数可以另外定义一个参数base，它表示相应的进制数（二进制、八进制、十六进制），另外创建一个字符串digits，由于有十进制转十六进制，所以该字符串的内容应该有ABCDEF，再加上数字0-9，即该字符串的内容为“0123456789ABCDEF”，它用于存储对应位置上的数字，当从栈中移除一个十进制余相应的进制数得到的余数时，就可以作为访问数字的下标，即对应的数字会被添加到结果中，最后再通过pop()方法将栈顶的元素移除，通过对字符串索引的方式依次索引移除的元素，并通过"+"拼接赋值给字符串newString。

十进制转其他进制（二进制、八进制、十六进制）的程序完整代码及解析如下：

# 通过列表实现栈的操作（以列表尾部作为栈的顶端）
class Stack:
    def __init__(self):
        self.items = []  # 创建一个空栈，它不需要参数，且会返回一个空栈
    def isEmpty(self):
        return self.items == []  # 检查栈是否为空，它不需要参数，且会返回一个布尔值
    def push(self, item):
        self.items.append(item)  # 将一个元素添加到栈的顶端，它需要一个参数item，且无返回值
    def pop(self):
        return self.items.pop()  # 将栈顶的元素移除，它不需要参数，但会返回顶端的元素，且修改栈的内容
    def peek(self):
        return self.items[len(self.items) - 1]  # 返回栈顶端的元素，它不需要参数，不会修改栈的内容
    def size(self):
        return len(self.items)  # 返回栈中元素的数目，它不需要参数，且会返回一个整数
# 创建一个有参函数BaseConverter()，参数为进制数和进制
def BaseConverter(decNumber, base):
    digits = "0123456789ABCDEF"  # 创建一个字符串digits，存储对应位置上的数字，当从栈中移除一个余数时，它可以被用作访问数字的下标，对应的数字会被添加到结果中
    s = Stack()
    while decNumber > 0:  # 若输入的进制数大于0，则执行while循环一直下去
        rem = decNumber % base  # 参数rem为余数，即进制数每次除相应的进制得到的余数
        s.push(rem)  # 通过push()方法将得到的余数添加到栈的顶端
        decNumber = decNumber // base  # 输入的进制数整数除相应的进制
    newString = ""  # 定义一个空字符串newString用于存放二进制数字
    while not s.isEmpty():  # 若栈不为空，则执行while循环一直下去
        newString = newString + digits[s.pop()]  # 通过pop()方法将栈顶的元素移除，通过对字符串索引的方式依次索引移除的元素，并通过"+"拼接赋值给字符串newString
    return newString  # 得到的相应进制值
#测试
print(BaseConverter(17, 2))
print(BaseConverter(255, 8))
print(BaseConverter(1024, 16))
print(BaseConverter(2022, 16))

运行结果如下：

结语

参考书籍：《Python数据结构与算法分析第2版》

[美] 布拉德利·米勒（Bradley N. Miller）戴维·拉努姆（DavidL. Ranum）|译者:吕能刁寿钧

Python数据结构学习笔记——栈

一、栈的定义和特性