学习第九天-栈

1. 栈的定义：栈是一种线性表数据结构，仅允许在表的一端（栈顶）进行插入（入栈）和删除（出栈）操作。没有数据元素时为「空栈」，遵循「后进先出（LIFO）」原则。
2. 栈的存储方式
   • 顺序栈：利用地址连续的存储单元存放元素，用指针top指示栈顶位置，可借助 Python 的列表实现。
   • 链式栈：通过单链表实现，元素插入到链表首个节点前，top指向链表头节点。
3. 栈的基本操作：包括初始化空栈、判断栈是否为空、判断栈是否已满（仅适用于顺序栈）、插入元素、删除元素和获取栈顶元素。
4. 栈的应用：常作为辅助存储结构保存和取用信息，如函数调用栈、浏览器前进后退功能；利用后进先出规则保证特定存取顺序，如翻转元素顺序、铁路列车车辆调度，还可用于判断有效括号等问题。

优化内容

栈的定义与概念

栈（Stack），也被称为堆栈，是一种特殊的线性表数据结构。它有两个关键特征：一是操作的限制性，只允许在表的一端进行数据的插入和删除操作，这一端被称作「栈顶（top）」，而另一端则是「栈底（bottom）」；二是遵循「后进先出（Last In First Out，简称 LIFO）」原则。当栈中没有任何数据元素时，我们称其为「空栈」 。

在栈中，插入操作也叫「入栈」或「进栈」，删除操作则叫「出栈」或「退栈」。从线性表的角度看，栈中元素存在前驱后继的线性关系，元素按顺序进栈，栈顶元素是最后进栈的那个。从后进先出原则来说，每次出栈删除的都是当前栈顶元素，最先进入的元素位于栈底，最后进入的在栈顶。

栈的存储方式

1. 顺序栈：顺序栈是栈的顺序存储结构，它利用一组地址连续的存储单元，从栈底到栈顶依次存放元素。通过一个指针top来指示栈顶元素在顺序栈中的位置。在 Python 中，借助列表（list）就可以方便地实现顺序栈。列表的特性使其能够很好地模拟顺序栈的操作，利用列表的索引和内置方法，能轻松完成元素的入栈和出栈等操作。
2. 链式栈：链式栈采用单链表的方式实现栈。在链式栈中，元素按照插入顺序，依次插入到链表的第一个节点之前，栈顶指针top始终指向链表的头节点位置。这种存储方式的优势在于，插入和删除操作无需移动大量元素，效率较高，尤其适用于频繁进行插入和删除操作的场景。

栈的基本操作

1. 初始化空栈：创建一个空栈时，需要定义栈的大小size（在顺序栈中用于判断栈是否已满），同时设置栈顶元素指针top，通常初始时top指向栈底（在顺序栈中可能是 - 1 或 0，具体取决于实现方式；在链式栈中可能是None）。
2. 判断栈是否为空：该操作用于检查栈中是否有元素。当栈为空时，返回True；栈不为空时，返回False。在栈的删除操作和获取当前栈顶元素操作前，通常需要先判断栈是否为空，以避免空指针异常或其他错误。
3. 判断栈是否已满：此操作仅适用于顺序栈。当栈中的元素数量达到预先设定的栈大小时，返回True，表示栈已满；否则返回False。在顺序栈插入元素前，需判断栈是否已满，防止栈溢出；在获取栈顶元素操作时，也可能需要判断栈是否已满，以确保操作的正确性。
4. 插入元素（进栈、入栈）：这一操作相当于在线性表的末尾添加一个新的数据元素。在顺序栈中，先将新元素放入top指针所指位置，然后top指针上移；在链式栈中，创建新节点，将其插入到链表头节点之前，并更新top指针指向新节点。
5. 删除元素（出栈、退栈）：该操作类似在线性表末尾删除最后一个数据元素。顺序栈中，先取出top指针所指元素，然后top指针下移；链式栈中，删除头节点（即栈顶元素），并更新top指针指向下一个节点。
6. 获取栈顶元素：获取栈顶元素的操作与插入和删除不同，它不会改变栈顶指针top的位置。顺序栈中，直接返回top指针所指元素；链式栈中，返回头节点（栈顶元素）的值。

栈的应用

栈在算法和程序中应用广泛，主要体现在两个方面：

1. 辅助存储结构：栈能够方便地保存和取用信息，常被用作算法和程序中的辅助存储结构。例如，在操作系统中，函数调用栈用于记录函数调用的相关信息，包括函数参数、局部变量等。当一个函数被调用时，其相关信息入栈；函数执行结束后，这些信息出栈。在浏览器中，前进和后退功能也是借助栈来实现的，浏览过的页面地址按顺序入栈，通过栈操作实现页面的回溯和前进。
2. 保证特定存取顺序：基于栈的后进先出规则，可以保证特定的存取顺序。比如，在翻转一组元素的顺序时，将元素依次入栈，再依次出栈，就能得到翻转后的顺序。在铁路列车车辆调度场景中，利用栈的特性可以实现对列车车厢的合理调度，提高调度效率。

以判断有效的括号这道简单的算法题为例，给定一个只包含()、{}、[]的字符串s，判断字符串是否有效。有效的字符串需满足：左括号必须用相同类型的右括号闭合，且左括号必须以正确的顺序闭合。这道题就可以利用栈来解决，遍历字符串，遇到左括号入栈，遇到右括号时，检查栈顶元素是否与之匹配，若匹配则栈顶元素出栈，否则字符串无效。遍历结束后，若栈为空，则字符串有效，否则无效。