数据结构笔记-栈和队列部分。

栈和队列

栈

栈（Stack）是一种特殊的线性表，数据的存取必须遵循“先进后出”（LIFO, Last In First Out）的原则。

栈的基本操作

Init（S） 初始化栈为空。
Destroy（S） 销毁栈，释放内存。
Push（S, x） 将元素x压入栈顶。
Pop（S） 移除栈顶元素并返回它。
Top（S） 返回栈顶元素但不移除。
IsEmpty（S） 判断栈是否为空。

顺序栈

顺序栈使用一个数组来存储栈中的元素。

基本实现思想：

栈顶元素的索引从0开始，入栈时索引递增，出栈时索引递减。

优点：

实现简单，直接使用数组即可，易于理解和实现。

缺点：

固定大小的数组可能导致栈满的情况，此时无法再压入新元素。
空间利用率可能不高，因为数组的大小在初始化时就已经确定。

链栈

链栈使用链表来存储栈中的元素。

基本实现思想：

每个节点包含数据和指向下一个节点的指针。
栈底是一个空节点，称为哨兵节点，其指针指向栈顶节点。
入栈时，在哨兵节点和栈顶节点之间添加新节点，更新哨兵节点的指针指向新节点。
出栈时，删除哨兵节点指向的节点，更新哨兵节点的指针到下一个节点。

优点：

动态数据结构，不存在栈满的问题，可以根据需要动态增长。
空间利用率高，因为只有在需要时才会分配新节点。

缺点：

实现相对复杂，需要管理链表的节点。
由于链表的节点可能分散在内存中，可能影响缓存的局部性，从而影响性能。

栈的应用

递归实现：使用栈来实现递归调用的逆序输出。递归函数在每次调用时，将当前状态压入栈中，待所有递归调用结束后，依次弹出状态以完成递归的逆序输出。
括号匹配：使用栈来检查表达式中的括号是否正确匹配。遇到开括号时压入栈中，遇到闭括号时，检查栈顶是否有对应的开括号，有则弹出，无则不匹配。
栈求表达式的值：使用栈来计算后缀表达式或中缀表达式的值。对于后缀表达式，从左到右扫描表达式，遇到数字直接压栈，遇到运算符时，从栈中弹出所需数量的数字进行计算，并将结果压栈。

队列

队列（Queue）是一种特殊的线性表，数据的存取必须遵循“先进先出”（FIFO, First In First Out）的原则。

队列的基本操作

Init（Q） 初始化队列为空。
Destroy（Q） 销毁队列，释放内存。
Enqueue（Q, x） 将元素x添加到队尾。
Dequeue（Q） 移除队头元素并返回它。
Front（Q） 返回队头元素但不移除。
IsEmpty（Q） 判断队列是否为空。

顺序队列

顺序队列使用一个数组来存储队列中的元素，并使用两个指针分别指向队头（front）和队尾（rear）。

基本实现思想：

队列初始化时，front和rear都指向数组的起始位置。
入队（Enqueue）操作将元素添加到rear指针所在位置，然后将rear指针向前移动一位。
出队（Dequeue）操作移除front指针所在位置的元素，然后将front指针向前移动一位。

优点：

实现简单，直接使用数组即可。

缺点：

固定大小的数组可能导致队列满的情况，此时无法再加入新元素。
出队操作后，需要移动数组中的元素以保持连续性，这可能导致性能问题。

循环队列

循环队列是顺序队列的变种，通过将数组的最后一个位置连接到数组的开始位置，形成一个循环。

基本实现思想：

使用一个额外的标记来区分队列是否真的满了。
当rear指针到达数组末尾时，下一次入队操作会将元素添加到数组的起始位置，同时rear指针继续前进。
出队操作类似，front指针到达数组末尾时，下一次出队操作会从数组起始位置开始。

优点：

避免了固定大小数组的队满问题，能够更有效地利用空间。

缺点：

需要额外的逻辑来处理循环，例如使用取模运算来确定下一个位置。

链式队列

链式队列使用链表的方式来存储队列中的元素。

基本实现思想：

每个节点包含数据和指向下一个节点的指针。
队列使用两个节点：head和tail，分别表示队头和队尾。
入队操作在tail节点的后面添加新节点，并将tail指针移动到新节点。
出队操作移除head节点，并更新head指针到下一个节点。

优点：

动态数据结构，不存在队满的问题。

缺点：

实现相对复杂，需要管理链表的节点。
由于链表的节点可能分散在内存中，可能影响缓存的局部性，从而影响性能。

队列应用

广度优先搜索（BFS）：在图的遍历中，队列用来存储待访问的节点，确保按照访问顺序进行。
任务调度：在操作系统中，队列用于任务调度，按照任务的到达顺序执行。
实现最近使用（LRU）缓存淘汰算法：使用两个队列来实现，一个队列存储所有缓存项，另一个队列存储最近访问的缓存项，当缓存满时，移除第一个队列的队头元素。

队列和栈的转化

两个栈实现一个队列：使用两个栈A和B来实现队列。入队操作在栈A上执行，出队操作时，如果栈B为空，则将栈A的元素依次弹出并压入栈B，然后从栈B弹出元素。这样可以保证先进先出的顺序。
两个队列实现一个栈：使用两个队列A和B来实现栈。入栈操作在队列A上执行，出栈操作时，如果队列B不为空，则直接从队列B出队，否则将队列A的所有元素依次出队并入队到队列B，然后从队列B出队最后一个元素。这样可以保证先进后出的顺序。