1、1/232/23 線性表及操作 特殊的線性表棧 棧的操作原則 棧的順序存儲和鏈式存儲結構 棧的操作3/23學習目的要求: 棧的基本概念和棧的基本運算。棧的基本概念和棧的基本運算。 棧在計算機中的應用。棧在計算機中的應用。 隊列的基本概念和隊列的基本運算。隊列的基本概念和隊列的基本運算。 隊列在計算機中的應用。隊列在計算機中的應用。4/233.2.1 隊列的定義隊列的定義隊列（隊列（queue）也是一種特殊的線性表。也是一種特殊的線性表。特殊性特殊性：它僅允許在表的一端進行插入，在表：它僅允許在表的一端進行插入，在表的另一端進行刪除。的另一端進行刪除。5/23a1a2a3a4a5a6rearre

2、ar rearrear rearrearfront frontfront frontfrontfrontrear3.2.1 隊列的定義隊列的定義隊列的操作：隊列的操作：a1,a2,a3入隊，入隊，a1,a2出隊，出隊，a4,a5,a6入隊，入隊，a3,a4,a5,a6出隊。出隊。由于每個元素必然按照進入的次序由于每個元素必然按照進入的次序離隊，所以又把隊列稱為離隊，所以又把隊列稱為“先進先出先進先出”表（表（First In First Out ，簡稱，簡稱FIFO表）表）6/233.2.1 隊列的定義隊列的定義隊尾隊尾：允許進行允許進行插入操作插入操作的一端，由隊尾指針的一端，由隊尾指針re

3、ar指示指示隊空：隊空：當隊列中沒有元素時稱為隊空當隊列中沒有元素時稱為隊空隊首：隊首：允許進行允許進行刪除操作刪除操作的一端，由隊首指針的一端，由隊首指針front指示指示出隊：出隊：隊的刪除操作隊的刪除操作, ,又稱又稱離隊離隊入隊：入隊：隊列的插入操作，又稱隊列的插入操作，又稱進隊進隊7/23隊列的基本操作可以歸納為以下幾種隊列的基本操作可以歸納為以下幾種: （1）InitQueue（）（）; 初始化一個空隊列初始化一個空隊列Q； （2）GetFront（&Q，&y）; 取隊列取隊列Q的隊頭元素，的隊頭元素，y返回返回其值，但隊列其值，但隊列Q狀態不變；狀態不變； （3）EnQuene（

4、&Q，x）; 若隊列若隊列Q還有空間，將元素還有空間，將元素x插插入到隊尾；入到隊尾； （4）DelQueue（&Q，&y）;若隊列若隊列Q不為空，刪除隊列不為空，刪除隊列Q的隊頭元素，的隊頭元素，y返回其值；返回其值； （5）Empty（&Q）; 判斷隊列判斷隊列Q是否為空，若為空返回一是否為空，若為空返回一個真值，否則返回一個假值。個真值，否則返回一個假值。8/23隊列的存儲結構：隊列的存儲結構：順序存儲順序存儲順序隊列順序隊列鏈式存儲鏈式存儲鏈隊列鏈隊列9/233.2.2 隊列的順序存儲結構及其運算隊列的順序存儲結構及其運算1. 順序隊列順序隊列隊列順序存儲結構稱為隊列順序存儲結構稱為順

5、序隊列（順序隊列（sequential queue）。）。順序隊列與順序表一樣，用一個一維順序隊列與順序表一樣，用一個一維數組來存放數據元素。在內存中，用一組連續的數組來存放數據元素。在內存中，用一組連續的存儲單元順序存放隊列中各元素。存儲單元順序存放隊列中各元素。10/233.2.2 隊列的順序存儲結構及其運算隊列的順序存儲結構及其運算1. 順序隊列順序隊列#define MAXLEN 10typedef int elementtype;typedef struct /*隊列的順序存儲結構定義隊列的順序存儲結構定義*/ int elementMAXLEN; /*存放隊列元素的數組存放隊列元素

6、的數組*/ int front , rear ;/*隊首指針隊首指針 ,隊尾指針隊尾指針*/SeQueue;11/2343210front=rear=-1(1) 初始初始空隊空隊(2) 元素元素a入隊入隊(3)元素元素b, ,c, ,d入隊入隊(4)元素元素a出隊出隊43210reara front=-1 rear=043210reardcba front=-1 rear=343210reardcb front=0rear=3front總結：總結：（1）在隊列為）在隊列為空空的初始狀態時，的初始狀態時， front=rear=-1。（2）每當向隊列）每當向隊列插入插入一個元素，尾指針一個元素，

7、尾指針rear向后移動一位，向后移動一位，rear=rear+1。（3）當）當rear= MAXLEN-1 時，表示時，表示隊滿隊滿;（4）每從隊列中）每從隊列中刪除刪除一個元素時，隊首指針也向后移動一位，一個元素時，隊首指針也向后移動一位，front=front+1。（5）入隊的所有元素都出隊后，隊列為空，此時）入隊的所有元素都出隊后，隊列為空，此時front=rear;12/23說明：說明：（1）指針的位置：指針的位置：隊尾指針指向隊尾元素（尾元素下隊尾指針指向隊尾元素（尾元素下標），隊首指針指向隊首元素的前一個位置；標），隊首指針指向隊首元素的前一個位置；（2）溢出：溢出：當當隊列滿隊列

8、滿時（時（rear=MAXLEN-1）再做）再做入隊入隊運算必定產生空間溢出，簡稱運算必定產生空間溢出，簡稱“上溢上溢”；當；當隊列空隊列空時時（front=rear）再做）再做出隊出隊運算也將產生溢出，簡稱運算也將產生溢出，簡稱“下溢下溢”3.2.2 隊列的順序存儲結構及其運算隊列的順序存儲結構及其運算13/23a1a2a3a4a5a6rearrear rearrear rearrearfront frontfront frontfrontfrontrear入隊、出隊操作：入隊、出隊操作：3.2.2 隊列的順序存儲結構及其運算隊列的順序存儲結構及其運算0 1 2 3 4 5入隊：入隊：(1)

9、判滿判滿;(2)移動隊尾指針移動隊尾指針 rear+；(3)新元素入隊尾新元素入隊尾 elementrear=x;出隊：出隊：(1)判空判空;(2)移動隊首指針移動隊首指針front+;(3)返回刪除元素返回刪除元素x=elementfront；elementfront=rear=-114/23（1） 入隊入隊int Enqueue_sq(SeQueue *q,elementtype x) if(q-rear=MAXLEN-1) return(0); /*隊列滿返回隊列滿返回0*/ q-rear+; q-elementq-rear=x; return(1);3.2.2 隊列的順序存儲結構及其運

10、算隊列的順序存儲結構及其運算15/23（2） 出隊出隊int Delqueue_sq(SeQueue *q,elementtype *x) if(q-front=q-rear) return(0); /*隊列空返回隊列空返回0*/ else q-front+; *x=q-elementq-front; return(1); 3.2.2 隊列的順序存儲結構及其運算隊列的順序存儲結構及其運算16/23隊列的存儲結構：隊列的存儲結構：順序存儲順序存儲順序隊列順序隊列鏈式存儲鏈式存儲鏈隊列鏈隊列17/233.2.3 隊列的隊列的鏈式存儲結構鏈式存儲結構及其運算及其運算隊列的鏈式存儲結構稱為隊列的鏈式存

11、儲結構稱為鏈隊列（鏈隊列（linked queue）。）。用帶頭結點的單鏈表表示如下：用帶頭結點的單鏈表表示如下：18/233.2.3 隊列的隊列的鏈式存儲結構鏈式存儲結構及其運算及其運算鏈隊列的結構定義：鏈隊列的結構定義：typedef struct node /*定義鏈隊列結點定義鏈隊列結點*/ int data; /*以整型數據為例以整型數據為例*/ struct node*next;/*存放下一個結點地址存放下一個結點地址*/NODE;19/233.2.3 隊列的隊列的鏈式存儲結構鏈式存儲結構及其運算及其運算鏈隊列的操作：鏈隊列的操作：（1）鏈隊列為）鏈隊列為空空條件：條件：front

12、=rear;均指向頭結點。均指向頭結點。（2）鏈隊列不存在滿的情況，除非內存已滿。）鏈隊列不存在滿的情況，除非內存已滿。（3）入隊入隊操作：向隊尾插入新結點。操作：向隊尾插入新結點。（4）出對出對操作：刪除隊首結點。操作：刪除隊首結點。20/233.2.3 隊列的隊列的鏈式存儲結構鏈式存儲結構及其運算及其運算鏈隊列入隊操作：鏈隊列入隊操作：xfront生成新結點并由指針生成新結點并由指針p指向新結點，指向新結點，數據域賦值為數據域賦值為x，指針域為，指針域為NULL；bc修改隊尾指針修改隊尾指針rear=t;parear向隊尾插入結點完成入隊向隊尾插入結點完成入隊,rear-next=t；21

13、/23（1）入隊）入隊NODE *pushqueue(NODE *rear,int x) /*入隊操作入隊操作*/ NODE *p; p=(NODE*)malloc(sizeof(NODE); p-data=x; /*將要插入的數據將要插入的數據x存儲到結點存儲到結點p的數據域中的數據域中*/ p-next=NULL; rear-next=p; /*將將p插入鏈隊列尾部插入鏈隊列尾部*/ rear=p;/*修改隊尾指針修改隊尾指針rear*/ return(rear);22/233.2.3 隊列的隊列的鏈式存儲結構鏈式存儲結構及其運算及其運算鏈隊列出隊操作：鏈隊列出隊操作：隊列不為空的情況下，

14、指針隊列不為空的情況下，指針p指向隊列的首元素指向隊列的首元素返回刪除結點的數據返回刪除結點的數據p-data，釋放結點，釋放結點free(p);rear刪除隊首結點，完成出隊刪除隊首結點，完成出隊,front-next=p-next；pfrontbca23/23（2） 出隊出隊NODE *popqueue(NODE *front,NODE *rear,int *x) /*出隊操作出隊操作*/ NODE *p; if(front!=rear) /*判斷鏈隊列空判斷鏈隊列空,若鏈隊列不空若鏈隊列不空*/ p=front-next;/*p指向鏈隊列第一個元素指向鏈隊列第一個元素*/ front-n

15、ext=p-next;/*將將p元素出隊元素出隊*/ if(p-next=NULL)/*表示原鏈隊列中只有一個元素表示原鏈隊列中只有一個元素*/ rear=front; /*出隊后出隊后,隊空隊空,修改修改rear指針指針*/ *x=p-data;/*保存出隊后的元素值保存出隊后的元素值*/ free(p); return(rear); /*返回返回rear*/ 24/23總結隊列的定義隊列的操作特點隊列的存儲結構順序隊列判空、判滿條件隊列的入隊、出隊操作25/232. 循環隊列循環隊列a1a2a3a4a5a6rearrear rearrear rearrearfront frontfront

16、 front0 1 2 3 4 5順序隊列操作的過程中可能會出現這樣情況，尾指針順序隊列操作的過程中可能會出現這樣情況，尾指針指向一維數組最后，但前面有元素已經出隊，這時要指向一維數組最后，但前面有元素已經出隊，這時要插入元素，仍然發生溢出，而實際上隊列并未滿。插入元素，仍然發生溢出，而實際上隊列并未滿。這這種溢出稱為種溢出稱為“假溢出假溢出”。為了解決這個問題，下面討。為了解決這個問題，下面討論循環隊列。論循環隊列。26/232. 循環隊列循環隊列循環隊列是將存儲隊列的循環隊列是將存儲隊列的存儲區看成是一個首尾相連的存儲區看成是一個首尾相連的環，即將表示隊列的數組元素環，即將表示隊列的數組元

17、素 element0與與elementMAXLEN-1連接起來，形連接起來，形成一個成一個環形表環形表。當隊列的第當隊列的第MaxSize-1個位置被占用以后，只要隊列的前端個位置被占用以后，只要隊列的前端還有可用空間，則把新的數據元素加入隊列的第還有可用空間，則把新的數據元素加入隊列的第0號位置。號位置。27/23 54 03 1 2 front=rear= -1rear f e a d b c 54 03 1 2front= -1; rear=52)a,b,c,d,e,f入隊入隊 f e d c 54 03 1 2rearrear=5front=1front3)a,b出隊出隊1)初始初始

18、空隊空隊入隊操作：入隊操作：rear=(rear+1)%MAXLEN; elementrear=x;元素出隊：元素出隊：front=(front+1)%MAXLEN;解決：通過解決：通過rear=(rear+1)%MAXLEN，讓，讓rear歸零。歸零。問題：當問題：當rear=MAXLEN-1時，再執行時，再執行rear+，數組，數組下標越界。下標越界。28/23 f e g d h c 54 03 1 2rearfront= rear=1front4)g,h入隊，入隊，隊滿隊滿 54 03 1 2rearfront= rear=1front5)c,d,e,f,g,h出隊，出隊，隊空隊空問題

19、：當隊滿和隊空時條件都是問題：當隊滿和隊空時條件都是front=rear此時：此時： front=rear是循環隊列空的標志；是循環隊列空的標志；（rear+1）%MAXLEN=front是循環隊列滿的標志。是循環隊列滿的標志。解決方法解決方法:(1)設標志位；設標志位；(2)少用一個元素空間少用一個元素空間29/232. 循環隊列循環隊列隊空條件：隊空條件：rear=front隊滿條件：隊滿條件：(rear+1)%MAXLEN=front入隊操作：入隊操作：rear=(rear+1)%MAXLEN; elementrear=x;出隊操作：出隊操作：front=(front+1)%MAXLEN

20、; x=elementfront;總結：總結：30/23（1） 入隊入隊int EnCqueue(CQueue *cq,elementtype x) if(cq-rear+1)%MAXLEN=cq-front) return(0); /*循環隊列滿返回循環隊列滿返回0*/ else cq-rear=(cq-rear+1)%MAXLEN; cq-elementcq-rear=x; return(1); 31/23（2） 出隊出隊int DelCqueue(CQueue *cq,elementtype *x) if(cq-rear=cq-front) return(0); /*循環隊列空返回循環隊

21、列空返回0*/ else cq-front=(cq-front+1)%MAXLEN; *x=cq-elementcq-front; return(1); 32/233.2.4 隊列的應用隊列的應用例例3.6 打印數據緩沖區問題。打印數據緩沖區問題。在打印機打印的時候，主機輸出數據的速度比打印機打印的速度要在打印機打印的時候，主機輸出數據的速度比打印機打印的速度要快得多。由于速度不匹配，大大影響了主機的工作效率。快得多。由于速度不匹配，大大影響了主機的工作效率。為了解決這個問題，通常是在內存中設置一個為了解決這個問題，通常是在內存中設置一個打印數據緩沖區打印數據緩沖區。緩。緩沖區是一塊連續的存儲

22、空間，把它設計成循環隊列結構，主機把要打沖區是一塊連續的存儲空間，把它設計成循環隊列結構，主機把要打印的數據依次寫入到這個緩沖區中，寫滿后就暫停輸出，主機此時可印的數據依次寫入到這個緩沖區中，寫滿后就暫停輸出，主機此時可以進行其他工作。打印機就從緩沖區按照先進先出的原則依次取出數以進行其他工作。打印機就從緩沖區按照先進先出的原則依次取出數據并打印。打印完這批數據后，再向主機發出請求，主機接到請求后，據并打印。打印完這批數據后，再向主機發出請求，主機接到請求后，再向緩沖區寫入打印數據。再向緩沖區寫入打印數據。33/23例例3.7 鍵盤輸入循環緩沖區問題。鍵盤輸入循環緩沖區問題。鍵盤輸入是另一個循

23、環隊列在計算機操作系統中應用的實例。鍵盤輸入是另一個循環隊列在計算機操作系統中應用的實例。例如，當程序正在執行某一任務時，用戶仍然可以從鍵盤輸入其他例如，當程序正在執行某一任務時，用戶仍然可以從鍵盤輸入其他內容。用戶輸入的內容暫時未能在屏幕上顯示出來，當程序的當前內容。用戶輸入的內容暫時未能在屏幕上顯示出來，當程序的當前任務結束時，用戶輸入的內容才顯示出來。任務結束時，用戶輸入的內容才顯示出來。 在這個過程中，系統是將檢測到的鍵盤輸入的字符先存儲到一在這個過程中，系統是將檢測到的鍵盤輸入的字符先存儲到一個緩沖區中，當系統當前任務結束后，就從個緩沖區中，當系統當前任務結束后，就從鍵盤緩沖區鍵盤緩沖區依次取出已依次取出已輸入的字符，并按要求進行處理。這是系統設置的一個鍵盤緩沖區，輸入的字符，并按要求進行處理。這是系統設置的一個鍵盤緩沖區，也采用了循環隊列結構。利用循環隊列的工作方式，