数据结构栈与队列的心得体会（数据结构之栈的解读）

通过对最近10年联考真题与本章有关考点的统计与分析结合数据结构课程知识体系的结构特点来看，本章应了解以下三部分内容： **（1）栈**，包括顺序存储结构和链式存储结构。 **（2）队列**,包括顺序存储结构和链式存储结构； **（3）数组**，重点掌握数组的存储结构、特殊矩阵的压缩存储和稀疏矩阵的压缩存储。

通过对最近10年联考真题与本章有关考点的统计与分析结合数据结构课程知识体系的结构特点来看，本章应了解以下三部分内容：（1）栈，包括顺序存储结构和链式存储结构。（2）队列,包括顺序存储结构和链式存储结构；（3）数组，重点掌握数组的存储结构、特殊矩阵的压缩存储和稀疏矩阵的压缩存储。

栈(stack) 是限定仅在表尾进行插入或 删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶(top), 相应地，表头端称为栈底(bottom) 。不含元素的空表称为空栈。

假设栈S=(a1,a 2 ,…，an ), 则称a1为栈底元素 ，an 为栈顶元素。栈中元素按a1，a2 , …,an 的次序进栈,退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如图3.2所示。因此，栈又称为后进先出(last in first out)的线性表（简称LI FO结构）表示。

顺序栈，即栈的顺序存储结构，是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top 指示栈顶元素在顺序栈中的位置。通常的习 惯做法是以top= O表示空栈，鉴于C语言中数组的下标约定从0开始，则当以C作 描述语言时，如此设定会带来很大不便；另一方面，由于栈在使用过程中所需最大空间的大小很难估计，因此，一般来说，在初始化设空栈时不应限定栈的最大容量。一个较合理的做法是：先为栈分配一个基本容量，然后在应 用过程中，当找的空间不够使用时再逐段扩大。为此，可设定两个常量：STACK —I NIT—SIZE ( 存储空间初始分配量）和STACKINCRE ME NT (存储空间分配增量。）

其中，stacksize指示栈的当前可使用的最大容量。栈的初始化操作为：按设定的初始分配量进行第一次存储分配，base可称为栈底指针，在顺序栈中，它始终指向栈底的位置，若base的值为NULL,则表明栈结构不存在。称top为栈顶指针，其初值指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1;删除栈顶元素时，指针top减1 ,因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上。图3.3展示了顺序栈中数据元素和栈顶指针之间的对应关系。

基本运算有：（1）初始化栈InitStack(＆S)（2）取栈顶元素GetTop(S,＆e)（3）进栈Status Push(＆S,e)（4）出栈Pop(＆S,e)

若需要用到两个相同类型的栈 ，可用一个数组data[O..MaxSize-1]来实现这两个栈，称之为共享栈。如图3.4所示。

因为一个数组有左右两个端点，而两个栈刚好也有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈的栈底为数组的末端，即下标为Maxsize-1 ,这样在两个栈中进栈元素时栈顶向中间伸展。

3） 栈的链式存储结构采用链式存储结构的栈称为链栈，这里采用不带头结点的单链表来实现，链栈的优点是不存在栈满溢出的清况，规定栈的所有操作都是在单链表的表头进行的。图3.5为栈与链栈的映射关系图，栈顶到栈底依次是an,an-1,…，a

链栈的结点结构与单链表的结构相同，在此使用StackNode表示基本运算有：（1）初始化栈InitStack(＆S)（2）入栈Push（＆s,e）（2）出栈Pop(＆S,e)（3）取栈顶元素GetTop(S,＆e)

内容来源于研芝士2021计算机考研精深解读数据结构

,