2012年计算机二级考试公共基础知识考前讲义（4）

会计考友

1.4 栈和队列
　　1、栈及其基本运算
9 e9 J4 g" L: v5 ?  C) |# v1 y　　栈是限定在一端进行插入与删除运算的线性表。
　　在栈中，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素，栈底元素总是最先被插入的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的。
* ^0 p" S. t6 K, u+ w　　栈具有记忆作用。
, d" v' s: N1 D8 K1 b2 f　　栈的基本运算：1）插入元素称为入栈运算；2）删除元素称为退栈运算；3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。
5 r! i' @, V0 v, [  Z1 Q* x4 ~( N　　栈的存储方式和线性表类似，也有两种，即顺序栈和链式栈。
　　2、队列及其基本运算
. d7 Z" F* I3 m) s' R/ g  w" L　　队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。尾指针（Rear）指向队尾元素，头指针（front）指向排头元素的前一个位置（队头）。
　　队列是“先进先出”或“后进后出”的线性表。
3 a2 D  h" e7 |: F$ V- Y9 U8 B　　队列运算包括：1）入队运算：从队尾插入一个元素；2）退队运算：从队头删除一个元素。
4 a0 d0 }$ L& x6 ?# ]4 }+ x& s　　循环队列及其运算：所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从头指针front指向的后一个位置直到队尾指针rear指向的位置之间，所有的元素均为队列中的元素。 　　*：循环队列中元素的个数=rear-front。