栈与队列

栈与队列内容摘要：

3 ( + 1 +进栈 4 ( + 1 2 输出 2 5 1 2 + +退栈输出，退栈到（止 6 * 1 2 + *进栈 7 * ( 1 2 + （进栈 8 * ( ( 1 2 + （进栈 9 * ( ( 1 2 + 8 输出 8 10 * ( ( 1 2 + 8 进栈 将中缀表达式 (1+2)*((82)/(74))变成等价的后缀表达式。 现在用栈来实现该运算，栈的变化及输出结果如下： 11 * ( ( 1 2 + 8 2 输出 2 12 * ( 1 2 + 8 2 退栈输出，退栈到（止 13 * ( / 1 2 + 8 2 / 进栈 14 * ( / ( 1 2 + 8 2 （ 进栈 15 * ( / ( 1 2 + 8 2 7 输出 7 16 * ( / ( 1 2 + 8 2 7 进栈 17 * ( / ( 1 2 + 8 2 7 4 输出 4 18 * ( / 1 2 + 8 2 7 4 退栈输出，退栈到（止 19 * 1 2 + 8 2 7 4 / /退栈输出，退栈到（止 20 1 2 + 8 2 7 4 / * *退栈并输出 队列定义 队列是只能在表的一端进行插入、在另一端进行删除操作的线性表。 允许删除元素的一端称为队头，允许插入元素的一端称为队尾。 显然不论元素按何种顺序进入队列，也必然按这种顺序出队列，所以队列又称为先进先出（ FIFO）表。 队列有两个活动端，所以设置了对头和队尾两个位置指针。 一般队头指针记作 front，队尾指针记作 rear。 a b c front rear 入队 出队 队列示意图 循环队列 — 队列顺序存储 顺序存储的队列中，每次出队列的元素必定是队头元素，因此如果采取与普通顺序表同样的操作方式，则每次出队操作必然将整个队列向前移动，这使得效率大大降低。 因此 在顺序存储的队列中，出队和入队操作都不移动元素而是移动指针。 为方便起见，这里规定队头指针 front指向队头元素的前一个位置，队尾指针rear指向队尾元素所在位置。 这样，入队和出队操作的执行步骤都是首先执行指针移动，再进行元素读写。 对空队列而言，可假定 front和 rear的值为 1 假溢出 A B C front rear front rear (a) A‚B‚C入 队 (b) A‚B出队 , D‚E入 队 (c)队列假溢出 队列假溢出示意图 C D E front rear 随着元素不断入队列、出队列， rear和 front指针会不断向后移动（如图 (b)所示），最终会指向数组的最大下标位置（如图 (c)所示）。 由于 rear和 front指针只能单方向移动，这时元素无法入队列，但是队列。