《數(shù)據(jù)結(jié)構(gòu)實用教程（C語言版）》課件第3章 棧和隊列

第3章棧和隊列本章主要介紹下列內(nèi)容棧的概念、存儲結(jié)構(gòu)及其基本操作

隊列的概念、存儲結(jié)構(gòu)及其基本操作棧與隊列的應(yīng)用舉例本章目錄

3.1棧1

3.2隊列2

3.3棧和隊列的應(yīng)用舉例3

3.4本章小結(jié)4結(jié)束3.1棧3.1.1棧的概念3.1.2棧的基本操作3.1.3順序棧3.1.4鏈棧返回到總目錄3.1.1

棧的概念例如，在建筑工地上，使用的磚塊從底往上一層一層地碼放，在使用時，將從最上面一層一層地拿取，這種后進(jìn)先出的線性結(jié)構(gòu)稱為棧（stack），棧又稱為后進(jìn)先出（lastinfirstout）的線性表，簡稱LIFO表。棧是一種特殊的線性表。其特殊性在于限定插入和刪除數(shù)據(jù)元素的操作只能在線性表的一端進(jìn)行。插入元素又稱為進(jìn)棧，刪除元素又稱為出棧。允許進(jìn)行插入和刪除操作的一端稱為棧頂（top），另一端稱為棧底（bottom）。處于棧頂位置的數(shù)據(jù)元素稱為棧頂元素，處于棧底位置的數(shù)據(jù)元素稱為棧底元素。不含任何數(shù)據(jù)元素的棧稱為空棧。

返回到本節(jié)目錄假設(shè)有一個棧S=（a1，a2，…，an），棧中元素按a1，a2，…，an的次序進(jìn)棧后，進(jìn)棧的第一個元素a1為棧底元素，出棧的第一個元素an為棧頂元素，也就是出棧的操作是按后進(jìn)先出的原則進(jìn)行的，其結(jié)構(gòu)如圖3-1所示。圖3-1棧結(jié)構(gòu)示意圖3.1.1

棧的概念返回到本節(jié)目錄3.1.2棧的基本操作

棧除了在棧頂進(jìn)行進(jìn)棧與出棧外，還有初始化、判空等操作，常用的基本操作有：（1）初始化棧InitStack(S)。其作用是構(gòu)造一個空棧S。（2）判斷?？誆mptyStack(S)。其作用是判斷是否是空棧，若棧S為空，則返回1；否則返回0。（3）進(jìn)棧Push(S,x)。其作用是當(dāng)棧不為滿時，將數(shù)據(jù)元素x插入棧S中，使其為棧S的棧頂元素。（4）出棧Pop(S,x)。其作用是當(dāng)棧S不為空時，將棧頂元素賦給x，并從棧S中刪除當(dāng)前棧頂元素。（5）取棧頂元素GetTop(S,x)。其作用是當(dāng)棧S不為空時，將棧頂元素賦給x并返回，操作結(jié)果只是讀取棧頂元素，棧S不發(fā)生變化。返回到本節(jié)目錄3.1.3順序棧

由于棧是操作受限制的線性表，因此與線性表類似，棧也有兩種存儲結(jié)構(gòu)，即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。1.順序棧的定義棧的順序存儲結(jié)構(gòu)稱為順序棧。類似于順序表的類型定義，順序棧是用一個預(yù)設(shè)的足夠長度的一維數(shù)組和一個記錄棧頂元素位置的變量來實現(xiàn)。順序棧中棧頂指針與棧中數(shù)據(jù)元素的關(guān)系如圖3-2所示。

圖3-2順序棧中棧頂指針與棧中數(shù)據(jù)元素的關(guān)系圖

返回到本節(jié)目錄2.順序棧的類型定義#defineMAXLEN100/*順序棧存儲空間的總分配量*/typedefcharElemType;/*定義ElemType為char類型*/typedefstruct/*順序棧存儲類型*/{ElemTypedata[MAXLEN];/*存放順序棧的數(shù)組*/inttop;/*記錄棧頂元素位置的變量*/}SeqStack;順序棧被定義為一個結(jié)構(gòu)體類型，其中ElemType為棧元素的數(shù)據(jù)類型，可以根據(jù)需要而指定某種具體的類型。data為一個一維數(shù)組，用于存儲棧中的數(shù)據(jù)元素，top為int類型，用于記錄棧頂元素所在的位置。注：順序棧的程序是由C語言描述，C語言的數(shù)組下標(biāo)從0開始。3.1.3順序棧返回到本節(jié)目錄3.順序棧的基本操作實現(xiàn)（1）初始化棧操作首先創(chuàng)建一個空棧，并將棧頂下標(biāo)top初始化為-1，算法描述見算法3.1。算法3.1voidInitStack(SeqStack*S){S->top=-1;/*初始化的順序棧為空*/}3.1.3順序棧返回到本節(jié)目錄3.順序棧的基本操作實現(xiàn)（2）判斷?？詹僮髋袛嗍欠袷强諚＃碨->top==-1），若棧S為空，則返回1；否則返回0，算法描述見算法3.2。算法3.2intEmptyStack(SeqStack*S){if(S->top==-1)/*棧為空*/return1;elsereturn0;}3.1.3順序棧返回到本節(jié)目錄3.順序棧的基本操作實現(xiàn)（3）進(jìn)棧操作進(jìn)棧操作的過程如圖3-3所示。先判斷棧S如圖3-3（a）是否為滿，若不滿再將記錄棧頂?shù)南聵?biāo)變量top加1如圖3-3（b），最后將進(jìn)棧元素放進(jìn)棧頂位置上如圖3-3（c）所示，算法描述見算法3.3。圖3-3進(jìn)棧操作過程圖

3.1.3順序棧返回到本節(jié)目錄3.順序棧的基本操作實現(xiàn)（3）進(jìn)棧操作算法3.3intPush(SeqStack*S,ElemTypex){if(S->top==MAXLEN-1)/*棧為滿*/{printf("棧滿!");return0;}/*棧滿不能進(jìn)棧*/else/*棧不為滿*/{S->top++;S->data[S->top]=x;return1;}}3.1.3順序棧返回到本節(jié)目錄3.順序棧的基本操作實現(xiàn)（4）出棧操作出棧操作的過程如圖3-4所示。先判斷棧S如圖3-4（a）是否為空，若不空將棧頂元素取出賦給指針變量*x，如圖3-4（b）所示，然后將記錄棧頂?shù)南聵?biāo)變量top減1如圖3-4（c）所示，算法描述見算法3.4。圖3-4出棧操作過程圖3.1.3順序棧返回到本節(jié)目錄3.順序棧的基本操作實現(xiàn)（4）出棧操作intPop(SeqStack*S,ElemType*x){if(EmptyStack(S))/*調(diào)用判空函數(shù)EmptyStack(S)，判斷棧是否為空*/{printf("棧空!");return0;/*?？詹荒艹鰲?/}else/*棧不為空*/{*x=S->data[S->top];S->top--;return1;}}3.1.3順序棧返回到本節(jié)目錄3.順序棧的基本操作實現(xiàn)（5）取棧頂元素將棧頂元素賦給指針變量*x，操作結(jié)果只是讀取棧頂元素，棧S不發(fā)生變化，算法描述見算法3.5。算法3.5intGetTop(SeqStack*S,ElemType*x){if(EmptyStack(S))/*調(diào)用判空函數(shù)EmptyStack(S)，判斷棧是否為空*/{printf("棧空!");return0;}else/*棧不為空*/{*x=S->data[S->top];return1;}}3.1.3順序棧返回到本節(jié)目錄3.順序棧的基本操作實現(xiàn)上述算法3.1-3.5為順序棧的基本操作函數(shù)，讀者可以對照執(zhí)行主函數(shù)調(diào)用后的結(jié)果分析，進(jìn)一步了解順序棧的各種操作的過程實現(xiàn)。（6）設(shè)計主函數(shù)如下：main(){SeqStackS;ElemTypex;InitStack(&S);printf("依次進(jìn)棧元素為：\n");printf("r元素進(jìn)棧\n");Push(&S,'r');printf("a元素進(jìn)棧\n");Push(&S,'a');printf("h元素進(jìn)棧\n");Push(&S,'h');3.1.3順序棧返回到本節(jié)目錄3.順序棧的基本操作實現(xiàn)（6）設(shè)計主函數(shù)如下：printf("c元素進(jìn)棧\n");Push(&S,'c');GetTop(&S,&x);printf("棧頂元素為：%c\n",x);printf("出棧序列為：");while(!EmptyStack(&S)){Pop(&S,&x);printf("%c",x);}printf("\n");}3.1.3順序棧上述程序的執(zhí)行結(jié)果如下：依次進(jìn)棧元素為：r元素進(jìn)棧a元素進(jìn)棧h元素進(jìn)棧c元素進(jìn)棧棧頂元素為：c出棧序列為：char

返回到本節(jié)目錄1.鏈棧的定義用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的棧稱為鏈棧，鏈棧與不帶頭結(jié)點(diǎn)單鏈表組織形式相似，因為棧的主要操作是在棧頂進(jìn)行插入與刪除操作，顯然將鏈表的第一個結(jié)點(diǎn)作為棧頂是最方便的，因此，沒有必要如單鏈表那樣為了操作方便附加一個頭結(jié)點(diǎn)，通常鏈棧表示如圖3-5所示。圖3-5鏈棧結(jié)構(gòu)示意圖3.1.4鏈棧返回到本節(jié)目錄2.鏈棧的類型定義與單鏈表的類型定義相同，在此用LinkStack命名。鏈棧的類型定義如下：typedefcharElemType;/*定義ElemType為char類型*/typedefstructnode/*鏈棧存儲類型*/{ElemTypedata;/*定義結(jié)點(diǎn)的數(shù)據(jù)域*/structnode*next;/*定義結(jié)點(diǎn)的指針域*/}LinkStack;3.1.4鏈棧返回到本節(jié)目錄3.鏈棧的基本操作實現(xiàn)（1）初始化棧操作首先創(chuàng)建一個空棧，將鏈棧類型的變量S=NULL標(biāo)識為空棧，算法描述見算法3.6。算法3.6LinkStack*InitStack(){LinkStack*S;S=NULL;/*初始化棧為空*/returnS;}3.1.4鏈棧返回到本節(jié)目錄3.鏈棧的基本操作實現(xiàn)（2）判斷?？詹僮髋袛嗍欠袷强諚＃碨==NULL），若棧S為空，則返回1；否則返回0，算法描述見算法3.7。算法3.7intEmptyStack(LinkStack*S){if(S==NULL)/*棧為空*/return1;elsereturn0;}3.1.4鏈棧返回到本節(jié)目錄3.鏈棧的基本操作實現(xiàn)（3）進(jìn)棧操作先創(chuàng)建一個以x為值的新結(jié)點(diǎn)p，其data域值為x則進(jìn)棧操作步驟如下：將新結(jié)點(diǎn)p的指針域指向原棧頂S（執(zhí)行語句p->next=S）。將棧頂S指向新結(jié)點(diǎn)p（執(zhí)行語句S=p）。進(jìn)棧操作的過程如圖3-6所示，算法描述見算法3.8。注：進(jìn)棧操作的①與②語句執(zhí)行順序不能顛倒，否則原S指針其后的鏈表將丟失。圖3-6進(jìn)棧操作過程圖3.1.4鏈棧返回到本節(jié)目錄3.鏈棧的基本操作實現(xiàn)（3）進(jìn)棧操作算法3.8LinkStack*Push(LinkStack*S,ElemTypex){LinkStack*p;p=(LinkStack*)malloc(sizeof(LinkStack));/*生成新結(jié)點(diǎn)*/p->data=x;/*將x放入新結(jié)點(diǎn)的數(shù)據(jù)域*/p->next=S;/*將新結(jié)點(diǎn)插入鏈表表頭之前*/S=p;/*新結(jié)點(diǎn)作為棧頂*/returnS;/*返回棧頂S*/}3.1.4鏈棧返回到本節(jié)目錄3.鏈棧的基本操作實現(xiàn)（4）出棧操作先將結(jié)點(diǎn)棧頂S數(shù)據(jù)域中的值賦給指針變量*x，則刪除操作步驟如下：結(jié)點(diǎn)p指針域指向原棧頂S（執(zhí)行語句p=S）。棧頂S指向其的下一個結(jié)點(diǎn)（執(zhí)行語句S=S->next）釋放p結(jié)點(diǎn)空間（執(zhí)行語句free(p)）。出棧的過程如圖3-7所示，算法描述見算法3.9。圖3-7出棧操作過程圖3.1.4鏈棧返回到本節(jié)目錄3.鏈棧的基本操作實現(xiàn)（4）出棧操作LinkStack*Pop(LinkStack*S,ElemType*x){LinkStack*p;if(EmptyStack(S))/*調(diào)用判空函數(shù)EmptyStack(S)，判斷棧是否為空*/{printf("?？?");returnNULL;}/*棧空不能出棧*/

else/*棧不為空*/{*x=S->data;/*棧頂元素取出賦給x*/p=S;/*p結(jié)點(diǎn)指向原棧頂S*/S=S->next;/*原棧頂S指向其下一個結(jié)點(diǎn)*/free(p);/*釋放原棧頂空間*/returnS;}/*返回棧頂S*/}3.1.4鏈棧返回到本節(jié)目錄3.鏈棧的基本操作實現(xiàn)（5）取棧頂元素將棧頂元素賦給指針變量*x，操作結(jié)果只是讀取棧頂元素，棧S不發(fā)生變化，算法描述見算法3.10。intGetTop(LinkStack*S,ElemType*x){if(EmptyStack(S))/*調(diào)用判空函數(shù)EmptyStack(S)，判斷棧是否為空*/{printf("棧空!");return0;}else/*棧不為空*/{*x=S->data;/*棧頂元素賦給變量x*/return1;}}3.1.4鏈棧返回到本節(jié)目錄3.鏈棧的基本操作實現(xiàn)上述算法3.6-3.10為鏈棧的基本操作函數(shù)，讀者可以對照執(zhí)行主函數(shù)調(diào)用后的結(jié)果分析，進(jìn)一步了解鏈棧的各種操作的過程實現(xiàn)。（6）設(shè)計主函數(shù)如下：main(){LinkStack*S;ElemTypex;S=InitStack();printf("依次進(jìn)棧元素為：\n");printf("r元素進(jìn)棧\n");S=Push(S,'r');printf("a元素進(jìn)棧\n");S=Push(S,'a');printf("h元素進(jìn)棧\n");S=Push(S,'h');3.1.4鏈棧返回到本節(jié)目錄3.鏈棧的基本操作實現(xiàn)（6）設(shè)計主函數(shù)如下：printf("c元素進(jìn)棧\n");S=Push(S,'c');GetTop(S,&x);printf("棧頂元素為：%c\n",x);printf("出棧序列為：");while(!EmptyStack(S)){S=Pop(S,&x);printf("%c",x);}printf("\n");}上述程序的執(zhí)行結(jié)果與順序棧對應(yīng)程序的執(zhí)行結(jié)果相同。3.1.4鏈棧返回到本節(jié)目錄3.2隊列3.2.1隊列的概念3.2.2隊列的基本操作3.2.3順序隊列3.2.4循環(huán)隊列3.2.5鏈隊列返回到總目錄例如，在日常生活中的排隊上車，排隊的規(guī)則是不允許“插隊”。后來的人需站在隊尾，每次總是隊頭先上車。這種先進(jìn)先出的規(guī)則應(yīng)用在數(shù)據(jù)結(jié)構(gòu)中稱為隊列（queue），隊列又稱為先進(jìn)先出（firstinfirstout）的線性表，簡稱FIFO表。隊列也是一種特殊的線性表。與棧不同，其插入操作限定在線性表的一端進(jìn)行，刪除操作限定在線性表的另一端進(jìn)行，隊列插入操作又稱為入隊，刪除操作又稱為出隊，允許進(jìn)行插入的一端稱為隊尾（rear），允許進(jìn)行刪除的一端稱為隊頭（front）。處于隊頭位置的數(shù)據(jù)元素稱為隊頭元素。處于隊尾位置的數(shù)據(jù)元素稱為隊尾元素。不含任何數(shù)據(jù)元素的隊列稱為空隊。3.2.1隊列的概念返回到本節(jié)目錄假設(shè)有一個隊列Q=(a1，a2，…，an），隊列中元素按a1，a2，…，an的次序入隊后，入隊的第一個元素a1為隊頭元素，最后一個元素an為隊尾元素，隊列的操作是按先進(jìn)先出的原則進(jìn)行的，其結(jié)構(gòu)如圖3-8所示。圖3-8隊列結(jié)構(gòu)示意圖

3.2.1隊列的概念返回到本節(jié)目錄3.2.2隊列的基本操作隊列的除了在隊頭進(jìn)行出隊和隊尾進(jìn)行入隊外，還有初始化、判空等操作，常用的基本操作有：（1）初始化隊列InitQueue(Q)。其作用是構(gòu)造一個空隊列Q。（2）判斷隊列空EmptyQueue(Q)。其作用是判斷是否是空隊列，若隊列Q為空，則返回1；否則返回0。（3）入隊EnQueue(Q,x)。其作用是當(dāng)隊列不為滿時，將數(shù)據(jù)元素x插入隊列Q的隊尾，使其為隊列Q的隊尾元素。（4）出隊DeQueue(Q,x)。其作用是當(dāng)隊列Q不為空時，將隊頭元素賦給x，并從隊列Q中刪除當(dāng)前隊頭元素，而其后繼元素成為隊頭元素。（5）取隊頭元素GetFront(Q,x)。其作用是當(dāng)隊列Q不為空時，將隊頭元素賦給x并返回，操作結(jié)果只是讀取隊頭元素，隊列Q不發(fā)生變化。返回到本節(jié)目錄由于隊列是操作受限制的線性表，因此與線性表類似，隊列也有兩種存儲結(jié)構(gòu)，即順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。1.順序隊列的定義隊列的順序存儲結(jié)構(gòu)稱為順序隊列。類似于順序表的類型定義，順序隊列用一個一維數(shù)組和兩個分別指向隊頭元素與隊尾元素的變量來實現(xiàn)。3.2.3順序隊列

返回到本節(jié)目錄2.順序隊列的類型定義#defineMAXSIZE100/*順序隊列存儲空間的總分配量*/typedefcharElemType;/*定義ElemType為char類型*/typedefstruct/*順序隊列存儲類型*/{ElemTypedata[MAXSIZE];/*存放順序隊列的數(shù)組*/intfront;/*記錄隊頭元素位置的變量*/intrear;/*記錄隊尾元素位置的變量*/}SeqQueue;3.2.3順序隊列返回到本節(jié)目錄順序隊列中的幾種狀態(tài)如圖3-9所示。圖3-9順序隊列中的幾種狀態(tài)假設(shè)圖3-9中的最大存儲空間為MAXSIZE=6，可以看出，當(dāng)隊列初始化時front=rear=-1，隊列為空如圖3-9（a）所示；當(dāng)rear=MAXSIZE-1=5時，再加入新元素，數(shù)組越界而導(dǎo)致程序發(fā)生異常的錯誤，如圖3-9（e）所示。但此隊列為空或有剩余存儲單元，我們將這種現(xiàn)象稱為“假溢出”。如何解決“假溢出”現(xiàn)象？請見3.2.4節(jié)循環(huán)隊列。3.2.3順序隊列返回到本節(jié)目錄1.循環(huán)隊列的定義將順序存儲隊列的元素的一維數(shù)組首尾相接，形成一個環(huán)狀。如圖3-10所示。我們將這種形式表示的隊列稱為循環(huán)隊列。循環(huán)隊列仍然是順序隊列結(jié)構(gòu)，只是邏輯上和前面的順序隊列有所不同。圖3-10（a）中隊頭與隊尾指針指向同一位置時為空隊，非空隊時如圖3-10（b）中隊頭指針front指向隊列中隊頭元素的前一個位置，隊尾指針rear指向隊列的隊尾元素位置。圖3-10循環(huán)隊列示意圖3.2.4循環(huán)隊列

返回到本節(jié)目錄3.2.4循環(huán)隊列假設(shè)隊列開辟的數(shù)組單元數(shù)為MAXSIZE，它的數(shù)組下標(biāo)在0～MAXSIZE-1之間，若使隊頭或隊尾增1，可以利用取模運(yùn)算實現(xiàn)。即front=(front+1)%MAXSIZE;rear=(rear+1)%MAXSIZE;【例3.1】圖3-10（b）所示的循環(huán)隊列示意圖最大空間為MAXSIZE=8，數(shù)組下標(biāo)為0～7之間，求a5元素入隊的位置。解：入隊隊尾指針增1當(dāng)前隊尾指針：rear=7;入隊后隊尾指針：rear=(rear+1)%MAXSIZE=0;返回到本節(jié)目錄3.2.4循環(huán)隊列因此，a5元素入隊后對應(yīng)的下標(biāo)為0。a5元素入隊后結(jié)果如圖3-11所示。圖3-11圖3-10（b）中a5元素入隊后循環(huán)隊列示意圖返回到本節(jié)目錄3.2.4循環(huán)隊列2.循環(huán)隊列中隊空和隊滿的條件【例3.2】圖3-10（b）所示的循環(huán)隊列示意圖，a5、a6、a7、a8元素依次入隊后，其隊列如圖3-12所示。圖3-12所示圖中a1、a2、a3、a4、a5、a6、a7、a8元素依次出隊后，其隊列如圖3-13所示。圖3-12圖3-10（b）中a5、a6、a7、a8元素依次入隊后循環(huán)隊列示意圖返回到本節(jié)目錄3.2.4循環(huán)隊列2.循環(huán)隊列中隊空和隊滿的條件圖3-13圖3-12中a1、a2、a3、a4、a5、a6、a7、a8元素依次出隊后循環(huán)隊列示意圖循環(huán)隊列解決了順序隊列的“假溢出”現(xiàn)象，但新的問題出現(xiàn)了，隊滿的條件不再是rear==MAXSIZE-1，而是front==rear和隊空的條件相同了。解決方法：損失一個單元不用，即當(dāng)循環(huán)隊列中元素的個數(shù)是MAXSIZE-1時就認(rèn)為隊列已滿，這樣循環(huán)隊列的隊滿條件就變成：(rear+1)%MAXSIZE==front。隊空條件不變?nèi)允牵篺ront==rear。返回到本節(jié)目錄3.2.4循環(huán)隊列2.循環(huán)隊列中隊空和隊滿的條件【例3.3】圖3-10（b）所示的循環(huán)隊列示意圖，a5、a6、a7元素依次入隊后隊滿，其隊列如圖3-14所示。圖3-14圖3-10（b）中a5、a6、a7元素依次入隊后隊滿的循環(huán)隊列示意圖返回到本節(jié)目錄3.2.4循環(huán)隊列3.循環(huán)隊列的基本操作實現(xiàn)（2）判斷隊列空操作判斷是否是空隊列（即Q->front==Q->rear），若隊列Q為空，則返回1；否則返回0，算法描述見算法3.12。算法3.12intEmptyQueue(SeqQueue*Q){if(Q->front==Q->rear)/*隊列為空*/return1;elsereturn0;}返回到本節(jié)目錄3.2.4循環(huán)隊列3.循環(huán)隊列的基本操作實現(xiàn)

（3）入隊操作入隊操作的過程如圖3-15所示。先判斷隊列Q如圖3-15（a）否已滿，若不滿再將隊中的記錄隊尾的下標(biāo)變量rear加1如圖3-15（b）所示，最后將入隊元素x放進(jìn)隊尾位置上如圖3-15（c）所示，算法描述見算法3.13。返回到本節(jié)目錄圖3-15入隊操作的過程圖3.2.4循環(huán)隊列3.循環(huán)隊列的基本操作實現(xiàn)算法3.13intEnQueue(SeqQueue*Q,ElemTypex){if((Q->rear+1)%MAXSIZE==Q->front)/*隊列為滿*/{printf("隊滿!");return0;/*隊滿不能入隊*/}else/*隊不為滿*/{Q->rear=(Q->rear+1)%MAXSIZE;/*隊尾指針增1*/Q->data[Q->rear]=x;return1;}}

返回到本節(jié)目錄3.2.4循環(huán)隊列3.循環(huán)隊列的基本操作實現(xiàn)（4）出隊操作出隊操作的過程如圖3-16所示。先判斷隊列Q如圖3-16（a）否為空，若不空再將隊中的記錄隊頭的下標(biāo)變量front加1后將隊頭元素取出賦給*x，如圖3-16（b）所示，出隊后如圖3-16（c）所示，算法描述見算法3.14。返回到本節(jié)目錄圖3-16出隊操作的過程圖3.2.4循環(huán)隊列3.循環(huán)隊列的基本操作實現(xiàn)算法3.14intDeQueue(SeqQueue*Q,ElemType*x){if(EmptyQueue(Q))/*調(diào)用判空函數(shù)EmptyQueue(Q)，判斷隊列是否為空*/{printf("隊空!");return0;/*隊空不能出隊*/}else/*隊不為空*/{Q->front=(Q->front+1)%MAXSIZE;/*隊頭指針增1*/*x=Q->data[Q->front];return1;}}返回到本節(jié)目錄3.2.4循環(huán)隊列3.循環(huán)隊列的基本操作實現(xiàn)（5）取隊頭元素將隊頭元素賦給指針變量*x，操作結(jié)果只是讀取隊頭元素，隊列Q不發(fā)生變化，算法描述見算法3.15。算法3.15intGetFront(SeqQueue*Q,ElemType*x){if(EmptyQueue(Q))/*調(diào)用判空函數(shù)EmptyQueue(Q)，判斷隊列是否為空*/{printf("隊空!");return0;}else/*隊不為空*/{*x=Q->data[(Q->front+1)%MAXSIZE];return1;}}返回到本節(jié)目錄3.2.4循環(huán)隊列3.循環(huán)隊列的基本操作實現(xiàn)上述算法3.11-3.15為循環(huán)隊列的基本操作函數(shù)，讀者可以對照執(zhí)行主函數(shù)調(diào)用后的結(jié)果分析，進(jìn)一步了解循環(huán)隊列的各種操作的過程實現(xiàn)。（6）設(shè)計主函數(shù)如下：main(){SeqQueueQ;ElemTypex;InitQueue(&Q);printf("依次入隊元素為：\n");printf("q元素入隊\n");EnQueue(&Q,'q');printf("u元素入隊\n");EnQueue(&Q,'u');printf("e元素入隊\n");EnQueue(&Q,'e');printf("u元素入隊\n");EnQueue(&Q,'u');返回到本節(jié)目錄3.2.4循環(huán)隊列3.循環(huán)隊列的基本操作實現(xiàn)（6）設(shè)計主函數(shù)如下：printf("e元素入隊\n");EnQueue(&Q,'e');GetFront(&Q,&x);printf("隊頭元素為：%c\n",x);printf("出隊序列為：");while(!EmptyQueue(&Q)){DeQueue(&Q,&x);printf("%c",x);}printf("\n");}返回到本節(jié)目錄依次入隊元素為：q元素進(jìn)棧u元素進(jìn)棧e元素進(jìn)棧u元素進(jìn)棧e元素進(jìn)棧隊頭元素為：q出隊序列為：queue上述程序的執(zhí)行結(jié)果如下：3.2.5鏈隊列1.鏈隊列的定義用鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)的隊列稱為鏈隊列，一個鏈隊列需要一個隊頭指針和一個隊尾指針才能唯一確定。隊列中元素的結(jié)構(gòu)和前面單鏈表中的結(jié)點(diǎn)的結(jié)構(gòu)一樣。為了操作方便，在隊頭元素前附加一個頭結(jié)點(diǎn)，隊頭指針就指向頭結(jié)點(diǎn)，通常鏈隊列表示如圖3-17所示。返回到本節(jié)目錄圖3-17鏈隊列示意圖3.2.5鏈隊列2.鏈隊列的類型定義與單鏈表的類型定義相同，鏈隊列的類型定義如下：typedefcharElemType;/*定義ElemType為char類型*/typedefstructqnode/*鏈隊列存儲類型*/{ElemTypedata;/*定義結(jié)點(diǎn)的數(shù)據(jù)域*/structqnode*next;/*定義結(jié)點(diǎn)的指針域*/}LinkList;typedefstruct{LinkList*front,*rear;/*定義隊列的頭指針和尾指針*/}LinkQueue;LinkQueue類型說明中的兩個分量均為指針變量且封裝在一起，分別為鏈隊列的隊頭指針和隊尾指針。返回到本節(jié)目錄3.2.5鏈隊列3.鏈隊列的基本操作實現(xiàn)（1）初始化隊列操作鏈隊列的初始化即構(gòu)造一個僅包含頭結(jié)點(diǎn)的空鏈隊列Q，算法描述見算法3.16。算法3.16LinkQueue*InitQueue(){LinkQueue*Q;/*由隊列頭指針指向初始化頭結(jié)點(diǎn)*/Q->front=(LinkList*)malloc(sizeof(LinkList));Q->front->next=NULL;Q->front=Q->rear;/*初始化時隊尾指針也指向隊頭指針*/returnQ;}返回到本節(jié)目錄3.2.5鏈隊列3.鏈隊列的基本操作實現(xiàn)（2）判斷鏈隊列空操作判斷是否是空隊列（即Q->front==Q->rear），若鏈隊列Q為空，則返回1；否則返回0，算法描述見算法3.17。算法3.17intEmptyQueue(LinkQueue*Q){if(Q->front==Q->rear)/*鏈隊列為空*/return1;elsereturn0;}返回到本節(jié)目錄3.2.5鏈隊列3.鏈隊列的基本操作實現(xiàn)（3）入隊操作先創(chuàng)建一個新結(jié)點(diǎn)p，其data域值為x，指針域為空，則入隊操作步驟如下：將新結(jié)點(diǎn)插入隊尾，隊尾指針域Q->rear->next指向新結(jié)點(diǎn)p（執(zhí)行語句Q->rear->next=p）。將隊尾Q->rear指向新結(jié)點(diǎn)p（執(zhí)行語句Q->rear=p）。入隊操作的過程如圖3-18所示，算法描述見算法3.18。返回到本節(jié)目錄圖3-18入隊操作過程圖注：由于鏈隊列本身沒有容量限制，因此，在進(jìn)行入隊操作時不用考慮隊滿情況。3.2.5鏈隊列3.鏈隊列的基本操作實現(xiàn)（3）入隊操作算法3.18voidEnQueue(LinkQueue*Q,ElemTypex){LinkList*p;p=(LinkList*)malloc(sizeof(LinkList));/*生成新結(jié)點(diǎn)*/p->data=x;/*將x放入新結(jié)點(diǎn)的數(shù)據(jù)域*/p->next=NULL;Q->rear->next=p;/*將新結(jié)點(diǎn)插入鏈隊列之后*/Q->rear=p;/*隊尾指針指向隊尾元素*/}返回到本節(jié)目錄3.2.5鏈隊列3.鏈隊列的基本操作實現(xiàn)（4）出隊操作隊頭指針是指向隊頭元素的前一個結(jié)點(diǎn)，先將結(jié)點(diǎn)p指向隊頭元素，并將隊頭元素值取出賦給*x，則刪除操作步驟如下：將隊頭指針的指針域指向原隊頭元素的下一元素（新隊頭）的地址如圖3-19（a）所示，（執(zhí)行語句Q->front->next=p->next）。當(dāng)原隊列中僅有一個元素時如圖3-19（b）所示，出隊后隊尾指針指向?qū)︻^指針（執(zhí)行語句Q->rear=Q->front）釋放p結(jié)點(diǎn)空間（執(zhí)行語句free(p)）。返回到本節(jié)目錄3.2.5鏈隊列3.鏈隊列的基本操作實現(xiàn)（4）出隊操作出隊的過程如圖3-19所示，算法描述見算法3.19。返回到本節(jié)目錄圖3-19鏈隊列出隊操作過程圖3.2.5鏈隊列3.鏈隊列的基本操作實現(xiàn)（4）出隊操作算法3.19voidDeQueue(LinkQueue*Q,ElemType*x){

LinkList*p;if(EmptyQueue(Q))/*調(diào)用判空函數(shù)EmptyQueue(Q)，判斷隊列是否為空*/printf("隊空不能出隊!");else/*隊不為空*/{p=Q->front->next;/*p指向隊頭元素*/*x=p->data;/*隊頭元素取出賦給x*/Q->front->next=p->next;/*隊頭指針的指針域存放新隊頭元素的地址*/if(p->next==NULL)/*隊列中只含有一個元素出隊*/Q->rear=Q->front;/*出隊后隊尾指針指向隊頭指針，此時隊空*/free(p);/*釋放原隊頭結(jié)點(diǎn)空間*/}}返回到本節(jié)目錄3.2.5鏈隊列3.鏈隊列的基本操作實現(xiàn)（5）取隊頭元素將隊頭元素賦給指針變量*x，操作結(jié)果只是讀取隊頭元素，鏈隊列Q不發(fā)生變化，算法描述見算法3.20。算法3.20intGetFront(LinkQueue*Q,ElemType*x){if(EmptyQueue(Q))/*調(diào)用判空函數(shù)EmptyQueue(Q)，判斷隊列是否為空*/{printf("隊空!");return0;}else/*隊不為空*/{*x=Q->front->next->data;/*隊頭元素賦給變量x*/return1;}}返回到本節(jié)目錄3.2.5鏈隊列3.鏈隊列的基本操作實現(xiàn)上述算法3.16-3.20為鏈隊列的基本操作函數(shù)，讀者可以對照執(zhí)行主函數(shù)調(diào)用后的結(jié)果分析，進(jìn)一步了解鏈隊列的各種操作的過程實現(xiàn)。（6）設(shè)計主函數(shù)如下：main(){LinkQueue*Q;ElemTypex;Q=InitQueue();printf("依次入隊元素為：\n");printf("q元素入隊\n");EnQueue(Q,'q');printf("u元素入隊\n");EnQueue(Q,'u');printf("e元素入隊\n");EnQueue(Q,'e');返回到本節(jié)目錄3.2.5鏈隊列3.鏈隊列的基本操作實現(xiàn)（6）設(shè)計主函數(shù)如下：printf("u元素入隊\n");EnQueue(Q,'u');printf("e元素入隊\n");EnQueue(Q,'e');GetFront(Q,&x);printf("隊頭元素為：%c\n",x);printf("出隊序列為：");while(!EmptyQueue(Q)){DeQueue(Q,&x);printf("%c",x);}printf("\n");}上述程序的執(zhí)行結(jié)果與循環(huán)隊列對應(yīng)程序的執(zhí)行結(jié)果相同。返回到本節(jié)目錄3.3棧和隊列的應(yīng)用舉例

1.棧的應(yīng)用由于棧的“后進(jìn)先出”的特點(diǎn)，在數(shù)據(jù)處理中有著廣泛的應(yīng)用，進(jìn)制轉(zhuǎn)換就是利用棧做一個輔助的數(shù)據(jù)結(jié)構(gòu)進(jìn)行求解的典型示例?！纠?.4】使用展轉(zhuǎn)相除法將一個非負(fù)十進(jìn)制整數(shù)值轉(zhuǎn)換成二進(jìn)制數(shù)值。即用該十進(jìn)制數(shù)值除以2，并保留其余數(shù)，重復(fù)此操作，直到該十進(jìn)制數(shù)值為0為止。最后將所有的余數(shù)反向輸出就是所對應(yīng)的二進(jìn)制數(shù)值。返回到總目錄3.3棧和隊列的應(yīng)用舉例

1.棧的應(yīng)用如：(121)10=(1111001)2，其展轉(zhuǎn)相除的過程如圖3-20所示。返回到總目錄圖3-20十進(jìn)制數(shù)121轉(zhuǎn)換二進(jìn)制的過程圖3.3棧和隊列的應(yīng)用舉例

1.棧的應(yīng)用十進(jìn)制轉(zhuǎn)換為二進(jìn)制完整算法描述見算法3.21。算法3.21/**************各種常量及結(jié)構(gòu)體類型定義**************/#defineMAXLEN100/*順序棧存儲空間的總分配量*/typedefcharElemType;/*定義ElemType為char類型*/typedefstruct/*順序棧存儲類型*/{ElemTypedata[MAXLEN];/*存放順序棧的數(shù)組*/inttop;/*記錄棧頂元素位置的變量*/}SeqStack;返回到總目錄3.3棧和隊列的應(yīng)用舉例

1.棧的應(yīng)用/***************棧的初始化函數(shù)******************/voidInitStack(SeqStack*S){S->top=-1;/*初始的順序棧為空*/}/****************棧的判空函數(shù)*****************/intEmptyStack(SeqStack*S){if(S->top==-1)/*棧為空*/return1;elsereturn0;}返回到總目錄3.3棧和隊列的應(yīng)用舉例

1.棧的應(yīng)用/**************進(jìn)棧函數(shù)**********************/intPush(SeqStack*S,ElemTypex){if(S->top==MAXLEN-1)/*棧為滿*/{printf("棧滿溢出!");return0;/*棧滿不能進(jìn)棧*/}else/*棧不為滿*/{S->top++;S->data[S->top]=x;return1;}}返回到總目錄3.3棧和隊列的應(yīng)用舉例

1.棧的應(yīng)用/******************出棧函數(shù)******************/intPop(SeqStack*S,ElemType*x){if(EmptyStack(S))/*調(diào)用判空函數(shù)EmptyStack(S)，判斷棧是否為空*/{printf("?？?");return0;/*?？詹荒艹鰲?/}else/*棧不為空*/{*x=S->data[S->top];S->top--;return1;}}返回到總目錄3.3棧和隊列的應(yīng)用舉例

1.棧的應(yīng)用/**************進(jìn)制轉(zhuǎn)換函數(shù)******************/voidD_B(SeqStack*S,ElemTypex){while(x){Push(S,x%2);/*余數(shù)入棧*/x/=2;/*被除數(shù)data整除以2，得到新的被除數(shù)*/}printf("轉(zhuǎn)換后的二進(jìn)制為：\n");while(!EmptyStack(S)){Pop(S,&x);/*依次從棧中彈出每一個余數(shù)并輸出*/printf("%d",x);}}返回到總目錄3.3棧和隊列的應(yīng)用舉例

1.棧的應(yīng)用/******************主函數(shù)******************/main(){SeqStackS;ElemTypex;InitStack(&S);printf("請輸入十進(jìn)制正整數(shù)為:\n");scanf("%d",&x);/*輸入十進(jìn)制正整數(shù)*/D_B(&S,x);/*調(diào)用進(jìn)制轉(zhuǎn)換函數(shù)*/}返回到總目錄3.3棧和隊列的應(yīng)用舉例

2.隊列的應(yīng)用由于隊列的“先進(jìn)先出”的特點(diǎn)，在實際程序設(shè)計也有非常廣泛的用途。在此舉一個用隊列打印楊輝三角的例子來說明其使用方法。【例3.5】打印楊輝三角如圖3-21所示。返回到總目錄圖3-21楊輝三角3.3棧和隊列的應(yīng)用舉例

2.隊列的應(yīng)用由圖3-21可看出楊輝三角形的特點(diǎn)：即每一行的第一個元素和最后一個元素均為1，其它位置上的數(shù)字是其上一行中與之相鄰的兩個整數(shù)之和。所以在打印過程中，第i行上的元素要由第i-1行中的元素來生成。因此，可以利用循環(huán)隊列實現(xiàn)打印楊輝三角形的過程。在循環(huán)隊列中依次存放第i-1行上的元素，然后逐個出隊并打印，同時生成第i行元素并入隊。在整個過程中，楊輝三角中元素的入隊順序如圖3-22所示。返回到總目錄圖3-22楊輝三角入隊過程圖3.3棧和隊列的應(yīng)用舉例

2.隊列的應(yīng)用打印楊輝三角前N行元素完整算法描述見算法3.22。注：打印楊輝三角的最大行數(shù)一定要小于循環(huán)隊列的MAXSIZE-1值。算法3.22/**************各種常量及結(jié)構(gòu)體類型定義**************/#defineMAXSIZE100/*隊列存儲空間的總分配量*/typedefintElemType;/*定義ElemType為char類型*/typedefstruct/*隊列存儲類型*/{ElemTypedata[MAXSIZE];/*存放隊列的數(shù)組*/intfront;/*記錄隊頭元素位置的變量*/intrear;/*記錄隊尾元素位置的變量*/}SeqQueue;返回到總目錄3.3棧和隊列的應(yīng)用舉例

2.隊列的應(yīng)用/******************初始化循環(huán)隊列函數(shù)******************/voidInitQueue(SeqQueue*Q){Q->front=Q->rear=0;/*指針初始化*/}/*********************判空隊列函數(shù)********************/intEmptyQueue(SeqQueue*Q){if(Q->front==Q->rear)/*隊列為空*/return1;elsereturn0;}返回到總目錄3.3棧和隊列的應(yīng)用舉例

2.隊列的應(yīng)用/***********************入隊函數(shù)**********************/intEnQueue(SeqQueue*Q,ElemTypex){if((Q->rear+1)%MAXSIZE==Q->front)/*隊列為滿*/{printf("隊滿!");return0;/*隊滿不能入隊