課件版數(shù)據(jù)結(jié)構(gòu)ch03stackqueue

1、第三章 棧和隊(duì)列本章內(nèi)容3.1 棧3.1.1 棧的定義及基本運(yùn)算3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)3.1.3 棧的應(yīng)用3.2 隊(duì)列3.2.1 隊(duì)列的定義及基本運(yùn)算3.2.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)3.2.3 隊(duì)列的應(yīng)用3.1.1 棧的定義及基本運(yùn)算棧(Stack)的定義棧是僅限定在表尾進(jìn)行插入和刪除操作的線性表。術(shù)語(yǔ)棧頂(top)棧的表尾棧底(bottom) 棧的表頭空棧沒(méi)有元素的棧入棧(push) 向棧頂壓入元素出棧(pop) 從棧頂彈出元素anan-1 .a2a1棧底棧頂入棧出棧棧的特點(diǎn)棧的修改是按后進(jìn)先出的原則進(jìn)行的。因此，棧稱(chēng)為后進(jìn)先出表（LIFO）。3.1.1 棧的定義及基本運(yùn)算棧的運(yùn)算演

2、示(1)A、B、C、D四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出棧，得到一個(gè)輸出序列DCBA。DCBAABCDDCBA 3.1.1 棧的定義及基本運(yùn)算棧的運(yùn)算演示(1)A、B、C、D四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出棧，得到一個(gè)輸出序列DCBA。(2)能否由入棧序列A、B、C、D、E得到出棧序列CBDAE？ABCDE操作序列：出棧序列： 元素A入棧A A 元素B入棧B B 元素C入棧C C3.1.1 棧的定義及基本運(yùn)算棧的運(yùn)算演示(1)A、B、C、D四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出棧，得到一個(gè)輸出序列DCBA。(2)能否由入棧序列A、B、C、D、E得到出棧序列CBDAE？ DE操作序列：出棧序列： 元素A

3、入棧A 元素B入棧B 元素C入棧 元素C出棧CC 元素B出棧B3.1.1 棧的定義及基本運(yùn)算棧的運(yùn)算演示(1)A、B、C、D四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出棧，得到一個(gè)輸出序列DCBA。(2)能否由入棧序列A、B、C、D、E得到出棧序列CBDAE？ DE操作序列：出棧序列： 元素A入棧A 元素B入棧 元素C入棧 元素C出棧C 元素B出棧B 元素D入棧D D 元素D出棧D 元素A出棧A3.1.1 棧的定義及基本運(yùn)算棧的運(yùn)算演示(1)A、B、C、D四個(gè)元素依次進(jìn)入一個(gè)棧，再依次出棧，得到一個(gè)輸出序列DCBA。(2)能否由入棧序列A、B、C、D、E得到出棧序列CBDAE？ E操作序列：出棧序列： 元

4、素A入棧 元素B入棧 元素C入棧 元素C出棧C 元素B出棧B 元素D入棧 元素D出棧D 元素A出棧A 元素E入棧EE 元素E出棧E棧的基本運(yùn)算InitStack(&S): 初始化棧SStackEmpty(): 判斷棧是否為空Push(e): 將元素e放入棧頂Pop(e): 移走棧頂?shù)脑兀瑫r(shí)由e帶回該元素的值Gettop(): 獲取棧頂?shù)脑?，但不從棧中移?.1.1 棧的定義及基本運(yùn)算3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)順序棧棧的順序存儲(chǔ)結(jié)構(gòu)a1a2an-1an線性表anan-1 .a2a1棧棧底棧頂6F28an6F26an-1 . .6F02a26F00a1棧的順序存儲(chǔ)映象basetop3.1

5、.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)順序棧棧的順序存儲(chǔ)結(jié)構(gòu)6F28an6F26an-1 . .6F02a26F00a1棧的順序存儲(chǔ)映象basetop順序棧基本操作的實(shí)現(xiàn)StackEmpty():top = = basePush(e): *top+ = ePop(e): e = *-topGettop(): e = *(top-1)思考：為何不用top指向棧頂元素？3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)順序棧的C語(yǔ)言實(shí)現(xiàn)結(jié)構(gòu)定義/ -棧的順序存儲(chǔ)表示-# define STACK_INIT_SIZE 100;# define STACKINCREMENT 10;typedef struct ElemType *ba

6、se; /棧底指針，棧構(gòu)造前和銷(xiāo)毀后為空ElemType *top; /棧頂指針，指向棧頂元素的下一位置int stacksize; /當(dāng)前分配的棧的存儲(chǔ)空間數(shù)SqStack; 3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)順序棧的C語(yǔ)言實(shí)現(xiàn)基本操作的實(shí)現(xiàn)(1) 初始化Status InitStack(SqStack &S)/構(gòu)造一個(gè)空棧S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType) ;if(!S.base) exit (OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE ;

7、return OK;/InitStack3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)順序棧的C語(yǔ)言實(shí)現(xiàn)基本操作的實(shí)現(xiàn)(2) 元素入棧Status Push(SqStack &S, ElemType e)/構(gòu)造一個(gè)空棧if (S.top S.base = S.stacksize) return ERROR;*S.top = e;S.top+;return OK;/Push請(qǐng)自學(xué)其他操作的實(shí)現(xiàn)算法。3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)順序棧的另一種實(shí)現(xiàn)結(jié)構(gòu)定義/ -棧的順序存儲(chǔ)表示-#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef struct

8、 ElemType *base; /棧底指針，棧構(gòu)造前和銷(xiāo)毀后為空 int top; /棧頂指針，指向棧頂元素的下一位置int stacksize; /當(dāng)前分配的棧的存儲(chǔ)空間數(shù)SqStack; 3.1.2 棧的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)鏈棧棧的鏈?zhǔn)酱鎯?chǔ)anan-1 .a2a1棧棧底棧頂S棧的鏈?zhǔn)酱鎯?chǔ)an an-1 a1a2 思考 鏈棧是否需要另外設(shè)置頭指針？ 建立鏈棧適合用哪種插入法？ 鏈棧的基本操作的實(shí)現(xiàn)。STL中的棧#include #include #include using namespace std;int main() stack s; s.push(1); s.pop(); s.push(

9、10); s.push(11); cout s.top() endl; cout s.size() endl; cout s.empty() endl; return 0; The C+ Stack is a container adapter that gives the programmer the functionality of a stack - specifically, a FILO (first-in, last-out) data structure Stack constructors:construct a new stackempty:true if the stack

10、 has no elementspop:removes the top element of a stackpush:adds an element to the top of the stacksize:returns the number of items in the stacktop:returns the top element of the stack.#include #include using namespace std;struct ElemType int x; int y;void main( ) int i, n=7; ElemType t; stack S; for

11、(i=0;in;i+) t.x = i; t.y = i*i; S.push(t); cout S.size() endl; while (!S.empty() t = S.top(); coutt.yt; S.pop(); 3.1.3 棧的應(yīng)用根據(jù)棧的FILO特性，用作某些處理問(wèn)題的工具。數(shù)制轉(zhuǎn)換例： 4310 = 1010112被除數(shù)除數(shù)商余數(shù)432211212101102505221221012010 輸出3.1.3 棧的應(yīng)用括號(hào)匹配設(shè)一個(gè)表達(dá)式中可以包含三種括號(hào)：“(”和“)”、“”和“”、“”和“”，并且這三種括號(hào)可以按照任意的次序嵌套使用，考查表達(dá)式中的括號(hào)是否匹配。例如： .(.

12、).).例：a=b+(c-d)*(e-f);while (m(a8+t) m=m+1; t=t-1;實(shí)現(xiàn)方法利用棧進(jìn)行表達(dá)式中的括號(hào)匹配自左至右掃描表達(dá)式，若遇左括號(hào)，則將左括號(hào)入棧，若遇右括號(hào)，則將其與棧頂?shù)淖罄ㄌ?hào)進(jìn)行匹配，若配對(duì)，則棧頂?shù)淖罄ㄌ?hào)出棧，否則出現(xiàn)括號(hào)不匹配錯(cuò)誤。思考：匹配的充要條件？3.1.3 棧的應(yīng)用舉例迷宮問(wèn)題尋找一條從入口到出口的通路。8123456781234567入口出口前進(jìn)方向： 上(北)、下(南)、左(西)、右(東)東南北西 走步規(guī)則：首先從向下開(kāi)始，按照逆時(shí)針?lè)较蛩阉飨乱徊娇赡芮斑M(jìn)的位置棧3.1.3 棧的應(yīng)用迷宮問(wèn)題8123456781234567(1,1)i(

13、2,1)i(3,1)i(4,1)i(5,1)i(6,1)(7,1)i棧3.1.3 棧的應(yīng)用迷宮問(wèn)題8123456781234567(1,1)i(2,1)i(3,1)i(4,1)i(5,1)i(6,1)(7,1)i (5,2)i(5,3)i(6,3)i(6,4)i(8,8)iiiiii3.1.3 棧的應(yīng)用迷宮問(wèn)題迷宮的表示const int N=8;struct PosType int x, y;char mazeNN; /位置上的標(biāo)識(shí)，是否可通過(guò)迷宮初始化用二層嵌套循環(huán)對(duì)迷宮賦值迷宮求解(見(jiàn)教材算法)輸出棧中的路徑Status MazePath(maze, start, end) /若迷宮中存

14、在一條從入口start到出口end的通道，則求出這樣的一條通路 InitStack(S); curpos = start; curstep = 1; do if (pass(curpos) /當(dāng)前位置可以通過(guò) Mark(maze,curpos); /留下記號(hào) e = (curstep,curpos,1); push(S,e); /加入路徑 if (curpos=end) return true; /到達(dá)出口 curpos = NextPos(curpos,1) ;/下一個(gè)位置 curstep+; else /當(dāng)前位置不能通過(guò) if (!StackEmpty(S) pop(S,e); /退回一步

15、 while(e.di=4 & ! !StackEmpty(S) /當(dāng)前位置是死胡同 Markdead(maze,e.seat)；pop(S,e); /留下記號(hào)，沿來(lái)路返回 if (e.di1) return n*f(n-1); else return 1; void main( ) int n=4; printf(“%ld”,f(n); 棧與遞歸3.2.1 隊(duì)列的定義及基本運(yùn)算隊(duì)列(Queue)的定義隊(duì)列是僅限定在表尾進(jìn)行插入和表頭進(jìn)行刪除操作的線性表。術(shù)語(yǔ)隊(duì)頭(front)隊(duì)列的表頭，即只允許刪除的一端。隊(duì)尾(rear) 隊(duì)列的表尾，即只允許插入的一端。入隊(duì)(EnQueue) 向隊(duì)尾插入元

16、素。出隊(duì)(DeQueue) 從隊(duì)頭刪除元素。隊(duì)列的特點(diǎn)隊(duì)列的修改是按先進(jìn)先出的原則進(jìn)行的。因此，隊(duì)列稱(chēng)為先進(jìn)先出表（FIFO）。a1 a2 ai an隊(duì)頭front隊(duì)尾rear出隊(duì)入隊(duì)3.2.1 隊(duì)列的定義及基本運(yùn)算隊(duì)列的基本運(yùn)算InitQueue(&Q): 初始化隊(duì)列QQueueEmpty(): 判斷隊(duì)列是否為空EnQueue(e): 將元素e放入隊(duì)尾DeQueue(e): 移走隊(duì)頭元素，由e帶回該元素的值GetFront(): 獲取隊(duì)頭元素的值，但不從隊(duì)列中移走該元素Length(): 計(jì)算并返回隊(duì)列中元素的個(gè)數(shù)3.2.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)鏈隊(duì)列隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)a1

17、a2 anai Q.frontQ.reara1 a2 ai an隊(duì)頭front隊(duì)尾rear出隊(duì)入隊(duì)3.2.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)鏈隊(duì)列的C語(yǔ)言實(shí)現(xiàn) /-單鏈隊(duì)列的存儲(chǔ)結(jié)構(gòu)-typedef struct QNode /鏈表結(jié)點(diǎn)類(lèi)型 QElemType data; struct QNode *next;QNode,*QueuePtr; typedef struct /隊(duì)列類(lèi)型 QueuePtr front; /隊(duì)頭指針 QueuePtr rear; /隊(duì)尾指針LinkQueue;data Q.frontQ.rearStatus InitQueue(LinkQueue &Q) /構(gòu)造一個(gè)空隊(duì)列QQ

18、.front= Q.rear = (QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(OVERFLOW);Q.front-next = NULL;return OK;(2) 入隊(duì)Status EnQueue(LinkQueue &Q, QElemType e)/將元素e插入到隊(duì)列Q中p = (QueuePtr)malloc(sizeof(QNode);if (!p) exit(OVERFLOW);p-data = e;p-next=NULL;Q.rear-next = p; Q.rear = p;return OK;3.2.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)

19、鏈隊(duì)列基本操作的實(shí)現(xiàn)(1) 初始化 Q.frontQ.rearStatus DeQueue(LinkQueue &Q, QElemType &e)/若隊(duì)列不空，則隊(duì)頭元素出隊(duì)列，用e返回其值，返回OK /否則返回ERROR if (Q.rear = Q.front) return ERROR; p = Q.front - next; e = p - data; Q.front-next = p - next; if (Q.rear = p) Q.rear = Q.front; free(p); return OK;3.2.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)鏈隊(duì)列基本操作的實(shí)現(xiàn)(1) 初始化 (2) 入隊(duì)

20、列 (3) 出隊(duì)列 Q.frontQ.rear思考：如果不設(shè)置頭結(jié)點(diǎn)，需要考慮那些特殊情況？3.2.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)循環(huán)隊(duì)列隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)a1 a2 ai an隊(duì)頭front隊(duì)尾rear出隊(duì)入隊(duì)6F36an6F26ai . .6F02a26F00a1Q.frontQ.reara1a2a3Q.frontanQ.rear012nn+1m-1循環(huán)隊(duì)列循環(huán)隊(duì)列的C語(yǔ)言實(shí)現(xiàn)/-循環(huán)隊(duì)列的存儲(chǔ)結(jié)構(gòu)-#define MAXSIZE 100typedef struct QElemType *base; int front; int rear; SqQueue;循環(huán)隊(duì)列基本操作的實(shí)現(xiàn)(1) 初始化S

21、tatus InitQueue(SqQueue &Q)Q.base=(QElemType *)malloc(MAXSIZE*sizeof(QElemType);if (!Q.base) exit (OVERFLOW);Q.front = Q.rear = 0;return OK;3.2.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)(base+Maxsize-1)base3.2.2 隊(duì)列的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)循環(huán)隊(duì)列基本操作的實(shí)現(xiàn)(2) 入隊(duì)Status EnQueue(SqQueue &Q,QElemType e) /將元素e插入隊(duì)列Q的隊(duì)尾if (Q.rear+1) % MAXSIZE = Q.front) retu

22、rn ERROR;Q.baseQ.rear = e;Q.rear = (Q.rear+1) % MAXSIZE;return OK;(3) 出隊(duì)Status DeQueue(SqQueue &Q,QElemType &e) /刪除隊(duì)列Q的隊(duì)頭元素并用e帶回if (Q.front = Q.rear) return ERROR;e = Q.baseQ.front;Q.front = (Q.front+1) % MAXSIZE;return OK;STL中的隊(duì)列#include #include #include using namespace std;int main() queue q; q.p

23、ush(1); q.push(2); q.push(3); q.pop(); cout q.front() endl; cout q.back() endl; cout q.size() endl; cout q.empty() endl; return 0; The C+ Queue is a container adapter that gives the programmer a FIFO (first-in, first-out) data structure. Queue constructor:construct a new queueback:returns a referenc

24、e to last element of a queueempty:true if the queue has no elementsfront:returns a reference to the first element of a queuepop:removes the top element of a queuepush:adds an element to the end of the queuesize:returns the number of items in the queue.雙端隊(duì)列雙端隊(duì)列隊(duì)頭隊(duì)尾出隊(duì)入隊(duì)出隊(duì)入隊(duì)輸出受限的雙端隊(duì)列隊(duì)頭隊(duì)尾出隊(duì)入隊(duì)入隊(duì)雙端隊(duì)列輸入受限的

25、雙端隊(duì)列隊(duì)頭隊(duì)尾出隊(duì)入隊(duì)出隊(duì)STL中的雙端隊(duì)列dequequeuedequepushpush_backpush_frontpoppop_frontpop_backfrontfrontbackbacksizesizeemptyemptySTL提供了雙端隊(duì)列（Double-ended Queues ）Double-ended queues are like vectors, except that they allow fast insertions and deletions at the beginning (as well as the end) of the container.at:returns an element at a specific locationback:returns a reference to last element o