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

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

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

3、入棧A 元素B入棧B 元素C入棧 元素C出棧CC 元素B出棧B3.1.1 棧的定義及基本運算棧的運算演示(1)A、B、C、D四個元素依次進入一個棧，再依次出棧，得到一個輸出序列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 棧的定義及基本運算棧的運算演示(1)A、B、C、D四個元素依次進入一個棧，再依次出棧，得到一個輸出序列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棧的基本運算InitStack(&S): 初始化棧SStackEmpty(): 判斷棧是否為空Push(e): 將元素e放入棧頂Pop(e): 移走棧頂?shù)脑?，同時由e帶回該元素的值Gettop(): 獲取棧頂?shù)脑?，但不從棧中移?.1.1 棧的定義及基本運算3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)順序棧棧的順序存儲結(jié)構(gòu)a1a2an-1an線性表anan-1 .a2a1棧棧底棧頂6F28an6F26an-1 . .6F02a26F00a1棧的順序存儲映象basetop3.1

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

6、se; /棧底指針，棧構(gòu)造前和銷毀后為空ElemType *top; /棧頂指針，指向棧頂元素的下一位置int stacksize; /當(dāng)前分配的棧的存儲空間數(shù)SqStack; 3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)順序棧的C語言實現(xiàn)基本操作的實現(xiàn)(1) 初始化Status InitStack(SqStack &S)/構(gòu)造一個空棧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 棧的存儲結(jié)構(gòu)和實現(xiàn)順序棧的C語言實現(xiàn)基本操作的實現(xiàn)(2) 元素入棧Status Push(SqStack &S, ElemType e)/構(gòu)造一個空棧if (S.top S.base = S.stacksize) return ERROR;*S.top = e;S.top+;return OK;/Push請自學(xué)其他操作的實現(xiàn)算法。3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)順序棧的另一種實現(xiàn)結(jié)構(gòu)定義/ -棧的順序存儲表示-#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;typedef struct

8、 ElemType *base; /棧底指針，棧構(gòu)造前和銷毀后為空 int top; /棧頂指針，指向棧頂元素的下一位置int stacksize; /當(dāng)前分配的棧的存儲空間數(shù)SqStack; 3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)鏈棧棧的鏈?zhǔn)酱鎯nan-1 .a2a1棧棧底棧頂S棧的鏈?zhǔn)酱鎯n an-1 a1a2 思考 鏈棧是否需要另外設(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特性，用作某些處理問題的工具。數(shù)制轉(zhuǎn)換例： 4310 = 1010112被除數(shù)除數(shù)商余數(shù)432211212101102505221221012010 輸出3.1.3 棧的應(yīng)用括號匹配設(shè)一個表達式中可以包含三種括號：“(”和“)”、“”和“”、“”和“”，并且這三種括號可以按照任意的次序嵌套使用，考查表達式中的括號是否匹配。例如： .(.

12、).).例：a=b+(c-d)*(e-f);while (m(a8+t) m=m+1; t=t-1;實現(xiàn)方法利用棧進行表達式中的括號匹配自左至右掃描表達式，若遇左括號，則將左括號入棧，若遇右括號，則將其與棧頂?shù)淖罄ㄌ栠M行匹配，若配對，則棧頂?shù)淖罄ㄌ柍鰲?，否則出現(xiàn)括號不匹配錯誤。思考：匹配的充要條件？3.1.3 棧的應(yīng)用舉例迷宮問題尋找一條從入口到出口的通路。8123456781234567入口出口前進方向： 上(北)、下(南)、左(西)、右(東)東南北西 走步規(guī)則：首先從向下開始，按照逆時針方向搜索下一步可能前進的位置棧3.1.3 棧的應(yīng)用迷宮問題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)用迷宮問題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)用迷宮問題迷宮的表示const int N=8;struct PosType int x, y;char mazeNN; /位置上的標(biāo)識，是否可通過迷宮初始化用二層嵌套循環(huán)對迷宮賦值迷宮求解(見教材算法)輸出棧中的路徑Status MazePath(maze, start, end) /若迷宮中存

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

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

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

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

18、.front= Q.rear = (QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(OVERFLOW);Q.front-next = NULL;return OK;(2) 入隊Status EnQueue(LinkQueue &Q, QElemType e)/將元素e插入到隊列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 隊列的存儲結(jié)構(gòu)和實現(xiàn)

19、鏈隊列基本操作的實現(xiàn)(1) 初始化 Q.frontQ.rearStatus DeQueue(LinkQueue &Q, QElemType &e)/若隊列不空，則隊頭元素出隊列，用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 隊列的存儲結(jié)構(gòu)和實現(xiàn)鏈隊列基本操作的實現(xiàn)(1) 初始化 (2) 入隊

20、列 (3) 出隊列 Q.frontQ.rear思考：如果不設(shè)置頭結(jié)點，需要考慮那些特殊情況？3.2.2 隊列的存儲結(jié)構(gòu)和實現(xiàn)循環(huán)隊列隊列的順序存儲結(jié)構(gòu)a1 a2 ai an隊頭front隊尾rear出隊入隊6F36an6F26ai . .6F02a26F00a1Q.frontQ.reara1a2a3Q.frontanQ.rear012nn+1m-1循環(huán)隊列循環(huán)隊列的C語言實現(xiàn)/-循環(huán)隊列的存儲結(jié)構(gòu)-#define MAXSIZE 100typedef struct QElemType *base; int front; int rear; SqQueue;循環(huán)隊列基本操作的實現(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 隊列的存儲結(jié)構(gòu)和實現(xiàn)(base+Maxsize-1)base3.2.2 隊列的存儲結(jié)構(gòu)和實現(xiàn)循環(huán)隊列基本操作的實現(xiàn)(2) 入隊Status EnQueue(SqQueue &Q,QElemType e) /將元素e插入隊列Q的隊尾if (Q.rear+1) % MAXSIZE = Q.front) retu

22、rn ERROR;Q.baseQ.rear = e;Q.rear = (Q.rear+1) % MAXSIZE;return OK;(3) 出隊Status DeQueue(SqQueue &Q,QElemType &e) /刪除隊列Q的隊頭元素并用e帶回if (Q.front = Q.rear) return ERROR;e = Q.baseQ.front;Q.front = (Q.front+1) % MAXSIZE;return OK;STL中的隊列#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.雙端隊列雙端隊列隊頭隊尾出隊入隊出隊入隊輸出受限的雙端隊列隊頭隊尾出隊入隊入隊雙端隊列輸入受限的

25、雙端隊列隊頭隊尾出隊入隊出隊STL中的雙端隊列dequequeuedequepushpush_backpush_frontpoppop_frontpop_backfrontfrontbackbacksizesizeemptyemptySTL提供了雙端隊列（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