栈和队列是两种应用非常广泛的数据结构，它们都来自线性表数据结构，都是“操作受限”的线性表。
栈
栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out)线性表。
栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。
栈底(Bottom)：是固定端，又称为表头。
空栈：当表中没有元素时称为空栈。
设栈S=(a1，a2，…an)，则a1称为栈底元素，an为栈顶元素，如图１-1所示。
栈中元素按a1，a2，…an的次序进栈，退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。
图１-1.png
栈的顺序存储表示
栈的顺序存储结构简称为顺序栈，和线性表相类似，用一维数组来存储栈。根据数组是否可以根据需要增大，又可分为静态顺序栈和动态顺序栈。
栈的动态顺序存储表示
采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。
- 用bottom表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。
- 用top=bottom作为栈空的标记，每次top指向栈顶数组中的下一个存储位置。
- 结点进栈：首先将数据元素保存到栈顶(top所指的当前位置)，然后执行top加1，使top指向栈顶的下一个存储位置;
栈的静态顺序存储表示
采用静态一维数组来存储栈。
- 栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量top(称为栈顶指针)来指示当前栈顶位置。
- 用top=0表示栈空的初始状态，每次top指向栈顶在数组中的存储位置。
- 结点进栈：首先执行top加1，使top指向新的栈顶位置，然后将数据元素保存到栈顶(top所指的当前位置)。
当栈满时做进栈运算必定产生空间溢出，简称“上溢”。上溢是一种出错状态，应设法避免。
当栈空时做退栈运算也将产生溢出，简称“下溢”。下溢则可能是正常现象，因为栈在使用时，其初态或终态都是空栈，所以下溢常用来作为控制转移的条件。
栈的链式存储表示
栈的链式存储结构称为链栈，是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此，链栈没有必要像单链表那样附加头结点，栈顶指针top就是链表的头指针。图１-２是栈的链式存储表示形式。
图１-２.png
队列
队列(Queue)：也是运算受限的线性表。是一种先进先出(First In First Out ，简称FIFO)的线性表。只允许在表的一端进行插入，而在另一端进行删除。
队首(front) ：允许进行删除的一端称为队首。
队尾(rear) ：允许进行插入的一端称为队尾。
例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。
Paste_Image.png
队列的顺序表示
利用一组连续的存储单元(一维数组) 依次存放从队首到队尾的各个元素，称为顺序队列。
对于队列，和顺序栈相类似，也有动态和静态之分
队列的链式存储
队列的链式存储结构简称为链队列，它是限制仅在表头进行删除操作和表尾进行插入操作的单链表。
需要两类不同的结点：数据元素结点，队列的队首指针和队尾指针的结点，如图１-３所示。
图１-３.png
网友评论