栈的概念及性质

栈的基本概念

栈的定义

栈是一种只能在一端进行插入或删除的线性表。其中插入被称作进栈,删除被称作出栈

允许进行插入或删除操作的一端被称为栈顶,另一段被称为栈底,栈底固定不变。其中,栈顶由一个称为栈顶指针的位置指示器来指示。

(PS:栈顶指针并非传统意义上的指针,比如顺序栈用的是一个整型变量来指示,但是我们依然称其为栈顶指针)

栈的特点

  • 先进后出

栈的数学结构

当n个元素以某种顺序进栈,并且在满足先进后出的前提下可任意时刻出栈,所获得的元素排列数目满足函数 Catalan( )的计算,即:

当然你也可以得到化简形式

栈的储存结构

  • 顺序栈
  • 链栈

(PS:栈是一种稍加限制的线性表,因此顺序栈与链栈就类似于顺序表和链表)

作者

CairBin

发布于

2021-09-28

更新于

2021-09-28

许可协议

评论