返回目录

§3 栈和队列

§3.1 栈

§3.1.1 栈的基本概念

栈是一种 运算受限的线性表，它的插入和删除运算仅限定在表的某一端进行，不能在表中间和另一端进行。允许 进行插入和删除的一端称为 栈顶，另一端称为 栈底。

§3.1.2 栈的顺序存储结构

栈的顺序存储结构称为 顺序栈，组成：

  • 一维数组 data；
  • 记录栈顶元素位置的变量 top，习惯上将栈底放在数组下标小的那端，栈顶元素 由栈顶指针 top 所指向。

初始化栈空置 top = -1，不是 0。

§3.1.3 栈的链式存储结构（不重要）

栈的链式存储结构称为 链栈。这里采用 单链表 作为链栈，该单链表是不带头结点的。

只有表头指针没有表尾指针的循环单链表不能作为链栈。循环单链表太蠢（说的是循环单链表不是单链表）。