栈和队列

01-数据结构与算法 飞快学 388浏览

栈和队列都是线性表,栈的特点是后进先出,队列的特点是先进后出。

栈及其基本运算

栈是限定在一端进行插入与删除运算的线性表。

在栈中,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素,栈底元素总是最先被插入的元素。栈是按照“先进后出”或“后进先出”的原则组织数据的。

栈的基本运算:1)插入元素称为入栈运算;2)删除元素称为退栈运算;3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。

栈的存储方式和线性表类似,也有两种,即顺序栈和链式栈。

用一维数组S(1∶m)作为栈的顺序存储空间,其中m为最大容量。在栈的顺序存储空间S(1∶m)中,S(bottom)为栈底元素,S(top)为栈顶元素。top=0表示栈空,top=m表示栈满。

stack

队列及其基本运算

队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。尾指针(Rear)指向队尾元素,头指针(front)指向排头元素的前一个位置(队头)。

队列是“先进先出”或“后进后出”的线性表。

队列运算包括:1)入队运算:从队尾插入一个元素;2)退队运算:从队头删除一个元素。

\

循环队列及其运算

一般队列可以采用链式结构,但循环队列必须采用顺序存储空间

循环队列,就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。在循环队列中,用队尾指针rear指向队列中的队尾元素,用排头指针front指向排头元素的前一个位置,因此,从头指针front指向的后一个位置直到队尾指针rear指向的位置之间,所有的元素均为队列中的元素。循环队列中元素的个数=rear-front。

为了区分队空还是队满的情况,上图(d2)通过牺牲一个单元来区分队空和队满,入队时少用一个队列单元,这是一种较为普遍的做法,约定以“队头指针在队尾指针的下一位置作为队满的标志”。