栈的基础知识

0. 简介

最近在自己编写一些小的算法的时候，深感自己的算法过于臃肿。碰巧Datawhale在新的一期组队学习中组织了数据结构与算法的课程学习。于是就参加了，再次感谢Datawhale~~

首先跟大家分享一下两个自己感觉比较好的学习资料，一个是 算法通关手册 ，也是Datawhale在本次组队学习中的学习资料；一个是B站上的视频 【北京大学】数据结构与算法Python版（完整版），老师讲的特别棒（也难得有Python版的数据结构课程，哈哈~）。

1. 栈的简介

栈是数据结构中常见的一种数据存储方式。栈的全称叫做 堆栈（Stack）。栈是一种线性表数据结构，是一种只允许在表的一端进行插入和删除操作的线性表。个人认为，栈的最大特点就是后进先出（Last In First Out）简称为 「LIFO 结构」。这一特点主要体现在栈的 入栈 和 出栈 操作中，即最后进入栈的数据会被第一个取出来，具体操作如下图所示：

1.1 栈的存储方式

和之前介绍的数组一样，栈的存储主要有两种方式：

1. 顺序存储：顺序栈，即堆栈的顺序存储结构。利用一组地址连续的存储单元依次存放自栈底到栈顶的元素，同时使用指针 top 指示栈顶元素在顺序栈中的位置。
2. 链式存储：链式栈，即堆栈的链式存储结构。利用单链表的方式来实现堆栈。栈中元素按照插入顺序依次插入到链表的第一个节点之前，并使用栈顶指针 top 指示栈顶元素， top 永远指向链表的头节点位置。

算法通关手册 中分别给出了两种存储方式的代码实现

• 顺序栈

其主要的思想是利用了Python中已经有的数组来构建顺序栈，并始终遵循 LIFO 原则。

代码如下：

class Stack:
    # 初始化空栈
    def __init__(self, size=100):
        self.stack = []
        self.size = size
        self.top = -1    
        
    # 判断栈是否为空
    def is_empty(self):
        return self.top == -1
    
    # 判断栈是否已满
    def is_full(self):
        return self.top + 1 == self.size
    
    # 入栈操作
    def push(self, value):
        if self.is_full():
            raise Exception('Stack is full')
        else:
            self.stack.append(value)
            self.top += 1
    
    # 出栈操作
    def pop(self):
        if self.is_empty():
            raise Exception('Stack is empty')
        else:
            self.top -= 1
            self.stack.pop()
    
    # 获取栈顶元素
    def peek(self):
        if self.is_empty():
            raise Exception('Stack is empty')
        else:
            return self.stack[self.top]

• 链式栈

链式栈的构造引用了之前介绍的节点，并始终遵循 LIFO 原则

代码如下：

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        
class Stack:
    # 初始化空栈
    def __init__(self):
        self.top = None
    
    # 判断栈是否为空
    def is_empty(self):
        return self.top == None
    
    # 入栈操作
    def push(self, value):
        cur = Node(value)
        cur.next = self.top
        self.top = cur
    
    # 出栈操作
    def pop(self):
        if self.is_empty():
            raise Exception('Stack is empty')
        else:
            cur = self.top
            self.top = self.top.next
            del cur
    
    # 获取栈顶元素
    def peek(self):
        if self.is_empty():
            raise Exception('Stack is empty')
        else:
            return self.top.value

1.2 栈的简单应用

我们通过一道 Leetcode 试题来看一下栈的应用。这道题在 算法通关手册 和 【北京大学】数据结构与算法Python版（完整版）中都有提到。本文中采用的是 算法通关手册 的代码。
题目的论述如下：

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s。
要求：判断括号是否匹配。如果匹配，返回 True，否则返回 False。

解题思路为：

• 先判断一下字符串的长度是否为偶数。因为括号是成对出现的，所以字符串的长度应为偶数，可以直接判断长度为奇数的字符串不匹配。如果字符串长度为奇数，则说明字符串 s 中的括号不匹配，直接返回 False。
• 使用栈 stack 来保存未匹配的左括号。然后依次遍历字符串 s 中的每一个字符。如果遍历到左括号时，将其入栈。如果遍历到右括号时，先看栈顶元素是否是与当前右括号相同类型的左括号。如果是相同类型的左括号，则令其出栈，继续向前遍历。如果不是相同类型的左括号，则说明字符串 s 中的括号不匹配，直接返回 False。
• 遍历完，再判断一下栈是否为空。如果栈为空，则说明字符串 s 中的括号匹配，返回 True。如果栈不为空，则说明字符串 s 中的括号不匹配，返回 False。

代码如下：

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1:
            return False
        stack = list()
        for ch in s:
            if ch == '(' or ch == '[' or ch == '{':
                stack.append(ch)
            elif ch == ')':
                if len(stack) !=0 and stack[-1] == '(':
                    stack.pop()
                else:
                    return False
            elif ch == ']':
                if len(stack) !=0 and stack[-1] == '[':
                    stack.pop()
                else:
                    return False
            elif ch == '}':
                if len(stack) !=0 and stack[-1] == '{':
                    stack.pop()
                else:
                    return False
        if len(stack) == 0:
            return True
        else:
            return False