2.3 和队列的链式存储结构

2.3 和队列的链式存储结构

2.3 栈和队列的链式存储结构

　　栈和队列的链式存储结构是线性链表的特殊形式，具有线性链表的一些基本特征，同时，又具有其本身的一些特殊性质。

2.3.1 栈的链式存储结构

　　链栈就是使用链式存储结构实现的栈，一般情况下，可以直接使用线性链表来描述链栈。以链表尾作为栈底，以链表头作为栈顶，图2-4（a）是以不带头结点的线性链表描述的栈，图2-4（b）是带头结点的线性链表描述的栈。

　　1．栈的链式存储结构
　　用链式存储结构实现的栈称为链栈。通常用不带头结点的单链表表示一个栈，设置一个栈顶指针top。入栈、出栈都在top端进行。链栈是动态存储结构，元素个数动态变化，预先不需要指定。链栈的结点结构与单链表的结构相同，类型定义如下：
　　
　　因为栈中的主要运算是在栈顶插入和删除，将链表的头部做栈顶是最方便的，而且没有必要像单链表那样为了运算方便附加一个头结点。
　　2．链栈的基本操作算法
　　链栈的各个操作算法思想与顺序栈类似，不再赘述，下面仅给出算法描述。
　　① 置空栈。算法描述如下：
　　
　　② 判栈空。算法描述如下：
　　
　　③ 入栈。算法描述如下：
　　
　　④ 出栈。算法描述如下：
　　
　　⑤ 求栈长（元素个数）。算法描述如下：
　　

2.3 和队列的链式存储结构