《数据结构》学习笔记 第4章 栈与队列

第四章 栈与队列

1， 栈：线性序列，由向量/列表派生

相比于向量和列表，增加了约束：只能访问栈顶元素；只能对栈顶元素增减，且LILO。

五个主要操作：push(), pop(), top(), empty(), size().

实现：

• 

栈的应用：

• 逆序输出，如进制转换：
  • 
• 递归嵌套，如：
  • 括号匹配
  • 栈混洗（跟括号匹配相关）：按照某种规则，对栈内元素重新排列。
    • 
    • 栈混洗的数目：catalan(n) =  (2n)!/(n+1)!/n!。
    一个排列是栈混洗的三种判断算法。
    • 其一，O(n^3): 不包含312这种排列。
• 延迟缓冲，如中缀表达式求值
• 栈式计算

2，队列-在图算法中有广泛应用

受限的序列，FIFO。可有向量/列表派生。

支持的主要操作：enqueue(), dequeue(), front(), rear(), empty(), size().

实现：

• 

应用：循环分配器；银行服务模拟。

<注：堆栈的许多应用，暂时跳过>