栈（Stack）详解：原理、实现方法与常见应用场景

文本是《数据结构（共13篇）》专题的第 4 篇。阅读本文前，建议先阅读前面的文章：

一、概念描述

栈是一种线性的数据结构
相比数组栈操作的是数组的子集
只能从一端添加元素也只能从一端取出元素(这一端称为栈顶)
栈在计算机世界里对于程序逻辑有非常重要的作用

二、Stack

1、入栈

栈（Stack）详解：原理、实现方法与常见应用场景

2、出栈

栈（Stack）详解：原理、实现方法与常见应用场景

通过对比可以看出栈是一种后进先出的数据结构；也就是Last In First Out，缩写为LIFO。

三、栈相关的应用场景

1、无处不在的Undo操作（撤销）

2、程序调用所使用的系统栈

def main():
    fun_a()

def fun_a():
    print("fun_a()开始执行")
    fun_b()
    print("fun_a()执行完毕")

def fun_b():
    print("fun_b()开始执行")
    fun_c()
    print("fun_b()执行完毕")

def fun_c():
    print("fun_c()开始执行")
    print("fun_c()")
    print("fun_c()执行完毕")

if __name__ == "__main__":
    main()

栈（Stack）详解：原理、实现方法与常见应用场景

测试代码执行过程图示

栈（Stack）详解：原理、实现方法与常见应用场景

通过以上图示可以看出，系统栈对于程序的子过程调用非常重要，它可以记录上一次调用的点，当程序执行完成一个子过程后通过这个记录可以快速的找到上一次未完成的操作继续执行；深入研究这个逻辑的话可以帮助我们更好的理解递归的操作。

四、栈的基本实现

4.1 栈的基本方法

def push(e):     # 入栈
    pass

def pop():       # 出栈
    pass

def peek():      # 查看栈顶元素
    pass

def get_size():  # 查看栈一共有多少元素
    pass

def is_empty():  # 查看栈是否为空
    pass

其实从用户的角度去看，支持这些操作就可以满足日常的需求，具体的底层实现，用户是不会去关心的，实现底层有多种方式。

4.2 栈的底层实现（数组实现）

from abc import ABC, abstractmethod

# 定义Stack接口
class Stack(ABC):
    """栈的抽象基类"""

    @abstractmethod
    def get_size(self):
        """获取栈的长度"""
        pass

    @abstractmethod
    def is_empty(self):
        """查看栈是否为空"""
        pass

    @abstractmethod
    def push(self, e):
        """入栈"""
        pass

    @abstractmethod
    def pop(self):
        """出栈"""
        pass

    @abstractmethod
    def peek(self):
        """查看栈顶元素"""
        pass

# Stack实现类
class ArrayStack(Stack):
    """基于数组实现的栈"""

    def __init__(self, capacity=10):
        """ArrayStack构造器"""
        self.array = Array(capacity)

    def get_size(self):
        """获取栈中元素的个数"""
        return self.array.get_size()

    def is_empty(self):
        """判断栈是否为空"""
        return self.array.is_empty()

    def push(self, e):
        """向栈中添加一个元素"""
        self.array.add_last(e)

    def pop(self):
        """出栈"""
        return self.array.remove_last()

    def peek(self):
        """查看栈顶元素"""
        return self.array.get_last()

    def get_capacity(self):
        """获取栈的容量"""
        return self.array.get_capacity()

    def __str__(self):
        """重写toString方法"""
        res = "Stack: ["
        for i in range(self.array.get_size()):
            res += str(self.array.get(i))
            if i != self.array.get_size() - 1:
                res += ", "
        res += "] top"
        return res

# 测试Stack
def main():
    array_stack = ArrayStack()

    for i in range(5):
        array_stack.push(i)
        print(array_stack)

    array_stack.pop()
    print(array_stack)

if __name__ == "__main__":
    main()

栈（Stack）详解：原理、实现方法与常见应用场景

五、栈的另一个应用(括号匹配练习)

5.1 问题描述

假设一个算术表达式中可以包含三种括号：圆括号"("和")"，方括号"["和"]"和花括号"{"和"}"，且这三种括号可按任意的次序嵌套使用（如：…[…{… …[…]…]…[…]…(…)…)。编写判别给定表达式中所含括号是否正确配对出现的算法。输出结果True或者False。

5.2 代码实现

# 括号匹配
class Solution:
    def is_valid(self, s):
        stack = []

        for c in s:
            if c in '([{':
                stack.append(c)
            else:
                if not stack:
                    return False

                pop_char = stack.pop()

                if c == ')' and pop_char != '(':
                    return False
                if c == ']' and pop_char != '[':
                    return False
                if c == '}' and pop_char != '{':
                    return False

        return len(stack) == 0

def main():
    solution = Solution()
    print(solution.is_valid("()[]{}"))
    print(solution.is_valid("([)]"))

if __name__ == "__main__":
    main()

栈（Stack）详解：原理、实现方法与常见应用场景