數(shù)據(jù)結(jié)構(gòu)棧與隊列課件

1、棧、隊列、串是常用數(shù)據(jù)結(jié)構(gòu)。其中棧與隊列不僅可直接用于描述問題，而且大量用于算法的實現(xiàn)中。串多用于直接描述非數(shù)值的簡單信息。從數(shù)據(jù)元素間的邏輯關(guān)系看，棧、隊列與串是線性表，但從操作方式與種類看，它們與線性表有許多不同。因此，若把數(shù)據(jù)間邏輯關(guān)系與相應(yīng)的操作作為整體看待（即作為抽象數(shù)據(jù)類型），它們應(yīng)為新的數(shù)據(jù)結(jié)構(gòu)。事實上，棧與隊列是操作受限的線性表，串是元素受限的線性表。盡管它們與線性表有許多共同點，但也有不少特殊性。本章重點介紹這些特殊性，并給出一些典型的應(yīng)用實例。第三章 棧和隊列通常稱，棧和隊列是限定插入和刪除只能在表的“端點”進(jìn)行的線性表。 線性表 棧 隊列Insert(L, i, x) I

2、nsert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in棧和隊列是兩種常用的數(shù)據(jù)類型3.1 棧3.2 棧的應(yīng)用舉例3.3 棧與遞歸的實現(xiàn)3.4 隊列3.5 離散事件模擬(本節(jié)內(nèi)容不作要求)第三章 棧和隊列3.1.1 棧的定義3.1 棧 棧（stack）：是限定僅在表尾進(jìn)行插入和刪除操作的線性表。又稱為后進(jìn)先出（last in first out）的線性表（簡稱LIFO結(jié)構(gòu)）。 棧頂（top）：棧表尾端。棧底（bottom）：棧表頭端。 例：假設(shè)棧 ，則 稱為棧底元素， 為棧頂元素。棧中

3、元素按 的次序進(jìn)棧，退棧的第一個元素應(yīng)為棧頂元素。如圖3.1所示。 出棧 進(jìn)棧 棧頂 an . . . a2 棧底 a1 圖3.1 棧的示意圖 在現(xiàn)實世界中，有許多符合棧模型的例子。 例如，火車扳道站、進(jìn)入單車道死胡同的汽車等，都是棧的例子。 在計算機(jī)系統(tǒng)中，棧的例子更是多見。 例如，記錄中斷返回地址（斷點）的結(jié)構(gòu)就是棧。 在中斷發(fā)生時，為了處理完中斷事件后恢復(fù)被中斷事件的繼續(xù)執(zhí)行，需記下斷點。在允許多級中斷的情況下，中斷處理過程仍可能被其它中斷所中斷，因此，系統(tǒng)可能同時要保存多個斷點。由于中斷恢復(fù)是先恢復(fù)最近被打斷的過程，所以斷點的保存次序與取出次序正好相反，這正好滿足棧的特性。 棧中元素除

4、具有線性關(guān)系外，還具有先進(jìn)后出的特性。所以在應(yīng)用時，應(yīng)根據(jù)這兩點決定是否使用棧。3.1.2 棧的順序存儲結(jié)構(gòu) （1）定義 順序棧（即棧的順序存儲結(jié)構(gòu)）：是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設(shè)指針top指示棧頂元素在順序棧中的位置。（2）C語言描述typedef struct SElemType*base;/棧底指針SElemType*top;/棧頂指針int stacksize;/棧當(dāng)前可使用的最大容量。SqStack;（3）圖形表示 topbasetopbasetopbaseAABCDE圖3.2棧的順序存儲結(jié)構(gòu)示意圖 （4）ADT Stack的表示和實現(xiàn)#def

5、ineSTACK_INIT_SIZE100;/存儲空間初始分配量#defineSTACKINCREMENT10;/存儲空間分配增量typedef struct SElemType*base;/在構(gòu)造之前和銷毀之后，/base的值為NULLSElemType*top;/棧頂指針int stacksize;/棧當(dāng)前可使用的最大容量。SqStack;/-基本操作的函數(shù)原型說明-Status InitStack (SqStack &S);/構(gòu)造一個空棧SStatus DestroyStack (SqStack &S);/銷毀棧S，棧S不再存在Status ClearStack (SqStack &S)

6、;/把S置為空棧Status StackEmpty (SqStack S);/若S為空棧，則返回TRUE，否則返回FALSEStatus StackLength (SqStack S);/返回S的元素個數(shù)，即棧的長度Status GetTop (SqStack S, SElemType &e); /若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERRORStatus Push (SqStack &S, SElemType e); /插入元素e為新的棧頂元素Status Pop (SqStack &S, SElemType &e); /若棧不空，則刪除S的棧頂元素，用e返回其值，并返回O

7、K；否則返回ERRORStatus StackTraverse (SqStack S, Status (*visit) () ); /從棧底到棧頂依次對棧中每個元素調(diào)用函數(shù)visit()。一旦visit()失敗，則操作失敗 GetTop(S, &e) 初始條件：棧 S 已存在且非空。操作結(jié)果：用 e 返回 S 的棧頂元素。a1a2an Push(&S, e) 初始條件：棧 S 已存在。 操作結(jié)果：插入元素 e 為新的棧頂元素。a1a2ane Pop(&S, &e) 初始條件：棧 S 已存在且非空。 操作結(jié)果：刪除 S 的棧頂元素，并用 e 返回其值。a1a2anan-1 /-基本操作的算法描述

8、（部分）- Status InitStack (SqStack &S) /構(gòu)造一個空棧SS.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType);if (!S.base)exit (OVERFLOW);/存儲分配失敗S = S.base;S.stacksize = STACK_INIT_SIZE;return OK; /InitStackStatus GetTop (SqStack S, SElemType &e) /若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERRORif (S = = S.base)retur

9、n ERROR;e = *(S1);return OK; / GetTop Status Push (SqStack &S, SElemType e) /插入元素e為新的棧頂元素if (SS.base = S.stacksize) /棧滿，追加存儲空間 S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof(ElemType); if (!S.base)exit (OVERFLOW); /存儲分配失敗 S = S.base + S.stacksize; S.stacksize += STACKINCREMENT;* S + + = e;return OK; /Push Status Pop (SqStack &S, SElemType &e) /若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK； /否則返回ERRORif (S = = S.base)return ERROR;e = *S;return OK; /Pop棧頂指針鏈棧a1an注意: 鏈棧中指針的方向an