3.1.1 栈的基本概念

教材导航 · 第3章

原书定位

印刷页P62起,对应PDF第74页。下文为目视整理的知识提要;完整内容见原书对照。

允许操作的一端称栈顶,另一端称栈底;空栈不含元素。核心操作为初始化、判空、入栈、出栈、读栈顶和销毁。入栈次序固定时,出栈次序仍可能多种,但任意前缀都必须满足已出栈数不大于已入栈数。

nn 个不同元素依次入栈的合法出栈排列数为卡特兰数:

Cn=1n+1(2nn)C_n=\frac1{n+1}\binom{2n}{n}

图3.1 栈的示意图

图3.1 栈的示意图,原书P63。

对应练习

3.1 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P62,PDF第74页

原书对照,原书P63,PDF第75页