2011年軟考程序員考試復習筆試知識點整理(3)

　　3、棧與隊列

　　你可以問一下自己是不是已經(jīng)知道了以下幾點：

　　(1)棧、隊列的定義及其相關數(shù)據(jù)結構的概念，包括：順序棧，鏈棧，共享棧，循環(huán)隊列，鏈隊等。棧與隊列存取數(shù)據(jù)(請注意包括：存和取兩部分)的特點。

　　(2)遞歸算法。棧與遞歸的關系，以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法：n!階乘問題，fib數(shù)列問題，hanoi問題，背包問題，二叉樹的遞歸和非遞歸遍歷問題，圖的深度遍歷與棧的關系等。其中，涉及到樹與圖的問題，多半會在樹與圖的相關章節(jié)中進行考查。

　　(3)棧的應用：數(shù)值表達式的求解，括號的配對等的原理，只作原理性了解，具體要求考查此為題目的算法設計題不多。

　　(4)循環(huán)隊列中判隊空、隊滿條件，循環(huán)隊列中入隊與出隊(循環(huán)隊列在插入時也要判斷其是否已滿，刪除時要判斷其是否已空)算法。

　　【循環(huán)隊列的隊空隊滿條件

　　為了方便起見，約定：初始化建空隊時，令

　　front=rear=0,

　　當隊空時：front=rear，

　　當隊滿時：front=rear 亦成立，

　　因此只憑等式front=rear無法判斷隊空還是隊滿。

　　有兩種方法處理上述問題：

　　(1)另設一個標志位以區(qū)別隊列是空還是滿。

　　(2)少用一個元素空間，約定以“隊列頭指針front在隊尾指針rear的下一個位置上”作為隊列“滿”狀態(tài)的標志。

　　隊空時： front=rear，

　　隊滿時： (rear+1)%maxsize=front】

　　如果你已經(jīng)對上面的幾點了如指掌，棧與隊列一章可以不看書了。注意，我說的是可以不看書，并不是可以不作題哦。

　　循環(huán)隊列的主要操作：

　　(1)創(chuàng)建循環(huán)隊列

　　(2)初始化循環(huán)隊列

　　(3)判斷循環(huán)隊列是否為空

　　(4)判斷循環(huán)隊列是否為滿

　　(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年)