3、棧與隊(duì)列
你可以問一下自己是不是已經(jīng)知道了以下幾點(diǎn):
(1)棧、隊(duì)列的定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念,包括:順序棧,鏈棧,共享?xiàng),循環(huán)隊(duì)列,鏈隊(duì)等。棧與隊(duì)列存取數(shù)據(jù)(請(qǐng)注意包括:存和取兩部分)的特點(diǎn)。
(2)遞歸算法。棧與遞歸的關(guān)系,以及借助棧將遞歸轉(zhuǎn)向于非遞歸的經(jīng)典算法:n!階乘問題,fib數(shù)列問題,hanoi問題,背包問題,二叉樹的遞歸和非遞歸遍歷問題,圖的深度遍歷與棧的關(guān)系等。其中,涉及到樹與圖的問題,多半會(huì)在樹與圖的相關(guān)章節(jié)中進(jìn)行考查。
(3)棧的應(yīng)用:數(shù)值表達(dá)式的求解,括號(hào)的配對(duì)等的原理,只作原理性了解,具體要求考查此為題目的算法設(shè)計(jì)題不多。
(4)循環(huán)隊(duì)列中判隊(duì)空、隊(duì)滿條件,循環(huán)隊(duì)列中入隊(duì)與出隊(duì)(循環(huán)隊(duì)列在插入時(shí)也要判斷其是否已滿,刪除時(shí)要判斷其是否已空)算法。
【循環(huán)隊(duì)列的隊(duì)空隊(duì)滿條件
為了方便起見,約定:初始化建空隊(duì)時(shí),令
front=rear=0,
當(dāng)隊(duì)空時(shí):front=rear,
當(dāng)隊(duì)滿時(shí):front=rear 亦成立,
因此只憑等式front=rear無法判斷隊(duì)空還是隊(duì)滿。
有兩種方法處理上述問題:
(1)另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿。
(2)少用一個(gè)元素空間,約定以“隊(duì)列頭指針front在隊(duì)尾指針rear的下一個(gè)位置上”作為隊(duì)列“滿”狀態(tài)的標(biāo)志。
隊(duì)空時(shí): front=rear,
隊(duì)滿時(shí): (rear+1)%maxsize=front】
如果你已經(jīng)對(duì)上面的幾點(diǎn)了如指掌,棧與隊(duì)列一章可以不看書了。注意,我說的是可以不看書,并不是可以不作題哦。
循環(huán)隊(duì)列的主要操作:
(1)創(chuàng)建循環(huán)隊(duì)列
(2)初始化循環(huán)隊(duì)列
(3)判斷循環(huán)隊(duì)列是否為空
(4)判斷循環(huán)隊(duì)列是否為滿
(5)入隊(duì)、出隊(duì)
//空出頭尾之間的一個(gè)元素不用
#include
#include
#define MAXSIZE 100
typedef struct
{
intelem[MAXSIZE];
intfront, rear;
}Quque; //定義隊(duì)頭
int initQue(Quque **q) //初始化
{
(*q)->front=0;
(*q)->rear=0;
}
int isFull(Quque *q)
{
if(q->front==(q->rear+1)%MAXSIZE)//判滿(空出一個(gè)元素不用) 劉勉剛
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;
}
相關(guān)推薦:北京 | 天津 | 上海 | 江蘇 | 山東 |
安徽 | 浙江 | 江西 | 福建 | 深圳 |
廣東 | 河北 | 湖南 | 廣西 | 河南 |
海南 | 湖北 | 四川 | 重慶 | 云南 |
貴州 | 西藏 | 新疆 | 陜西 | 山西 |
寧夏 | 甘肅 | 青海 | 遼寧 | 吉林 |
黑龍江 | 內(nèi)蒙古 |