2011年软考程序员考试复习笔试知识点整理(3)

　　3、栈与队列

　　你可以问一下自己是不是已经知道了以下几点：

　　(1)栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据(请注意包括：存和取两部分)的特点。

　　(2)递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。

　　(3)栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。

　　(4)循环队列中判队空、队满条件，循环队列中入队与出队(循环队列在插入时也要判断其是否已满，删除时要判断其是否已空)算法。

　　【循环队列的队空队满条件

　　为了方便起见，约定：初始化建空队时，令

　　front=rear=0,

　　当队空时：front=rear，

　　当队满时：front=rear 亦成立，

　　因此只凭等式front=rear无法判断队空还是队满。

　　有两种方法处理上述问题：

　　(1)另设一个标志位以区别队列是空还是满。

　　(2)少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。

　　队空时： front=rear，

　　队满时： (rear+1)%maxsize=front】

　　如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。

　　循环队列的主要操作：

　　(1)创建循环队列

　　(2)初始化循环队列

　　(3)判断循环队列是否为空

　　(4)判断循环队列是否为满

　　(5)入队、出队

　　//空出头尾之间的一个元素不用

　　#include

　　#include

　　#define MAXSIZE 100

　　typedef struct

　　{

　　intelem[MAXSIZE];

　　intfront, rear;

　　}Quque; //定义队头

　　int initQue(Quque **q) //初始化

　　{

　　(*q)->front=0;

　　(*q)->rear=0;

　　}

　　int isFull(Quque *q)

　　{

　　if(q->front==(q->rear+1)%MAXSIZE)//判满(空出一个元素不用) 刘勉刚

　　return 1;

　　else

　　return 0;

　　}

　　int insertQue(Quque **q,int elem)

　　{

　　if(isFull(*q))return -1;

　　(*q)->elem[(*q)->rear]=elem;

　　(*q)->rear=((*q)->rear+1)%MAXSIZE;//插入

　　return0;

　　}

　　int isEmpty(Quque *q)

　　{

　　if(q->front==q->rear)//判空

　　return 1;

　　else

　　return 0;

　　}

　　int deleteQue(Quque ** q,int *pelem)

　　{

　　if(isEmpty(*q))

　　return 0;

　　*pelem=(*q)->elem[(*q)->front];

　　(*q)->front=((*q)->front +1)%MAXSIZE;

　　return0;

　　}

　　软考程序员考试历年真题重点题总结及答案

　　2011年上半年软考报名时间及方式汇总

　　软考程序员考试历年真题汇总(2007年-2010年)