1.1.4　栈和队列

1.栈及其基本运算

（1）栈的基本概念

栈是一种特殊的线性表，其插入与删除操作都只在线性表的一端进行。在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的一端称为栈底。栈顶元素总是最后被插入的元素，也是最先被删除的元素；栈底元素总是最先被插入的元素，也是最后才被删除的元素（假设栈s=（a1，a2，…，an），如图1-1-6所示）。栈是按照“先进后出（FILO）”或“后进先出（LIFO）”的原则组织数据的。

栈的描述：

①栈：是限定仅在表尾进行插入或删除操作的线性表。

②栈顶：表尾。

③栈底：表头。

④空栈：不含元素的空表。

（2）栈的运算

通常用指针top表示栈顶的位置，用指针bottom指向栈底，向栈中插入一个元素称为入栈运算，从栈中删除一个元素称为退栈运算，栈顶指针top动态反映了栈中元素的变化情况。在栈的顺序存储空间S（1：m）中，S（bottom）称为栈底元素，S（top）称为栈顶元素，top=0表示栈空，top=m表示栈满，如图1-1-7所示。

2.队列及其基本运算

（1）队列的基本概念

队列是指允许在一端进行插入，在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个队尾指针rear指向最后被插入的元素；允许删除的一端称为队头（排头），通常用一个排头指针front指向排头元素的前一个位置（假设队列为a=（a1，a2，…，an），如图1-1-8所示）。在队列这种数据结构中，最先插入的元素最先被删除，反之，最后插入的元素将最后被删除。因此，队列是“先进先出（FIFO）”或“后进后出（LILO）”的线性表，它体现了“先来先服务”的原则。

（2）循环队列的运算

①入队运算。入队运算是指在循环队列的队尾加入一个新元素。这个运算有两个基本操作：首先将队尾指针加1；然后将新元素插入到队尾指针指向的位置。当循环队列非空且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算，若此时进入入队运算，这种情况称为“上溢”。

②退队运算。退队运算是指在循环队列的排头位置退出一个元素并赋值给指定的变量。这个运算有两个基本操作：首先将排头指针加1，然后将排头指针指向的元素赋给指定的变量。当循环队列为空时，不能进行退队运算，若此时进行退队运算，这种情况称为“下溢”。

③循环队列的基本思想。是指把队列设想为一个循环的表，即elem[0]接在elem[maxsize-1]之后，如图1-1-9所示。