數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列

1、計(jì)算機(jī)軟件技術(shù)基礎(chǔ) 數(shù)據(jù)結(jié)構(gòu)東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組教師：高克寧教師：高克寧E-mailE-mail：c_c_數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組2 2 o 主要內(nèi)容主要內(nèi)容n 棧和隊(duì)列是兩種特殊的線性表，是操作受限棧和隊(duì)列是兩種特殊的線性表，是操作受限的線性表，稱限定性的線性表，稱限定性DSo 棧和隊(duì)列是限定插入和刪除只能在表的棧和隊(duì)列是限定插入和刪除只能在表的“端點(diǎn)端點(diǎn)”進(jìn)行的線性表進(jìn)行的線性表數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組3 3 o

2、 棧棧n 限定僅在表尾進(jìn)行插入或刪除操作的線性表限定僅在表尾進(jìn)行插入或刪除操作的線性表o 表尾表尾棧頂棧頂o 表頭表頭棧底棧底o(hù) 不含元素的空表稱空棧不含元素的空表稱空棧n 特點(diǎn)特點(diǎn)o 先進(jìn)后出（先進(jìn)后出（FILO）o 后進(jìn)先出（后進(jìn)先出（LIFO）a an na a1 1a a2 2.棧底棧底棧頂棧頂.出棧出棧進(jìn)棧進(jìn)棧棧棧s=(a1,a2,s=(a1,a2,an),an)數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組4 4 o 棧棧定義定義ADT Stack 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： D ai | ai ElemSet, i=1,2,.,

3、n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | ai-1, aiD, i=2,.,n 約定約定an 端為棧頂，端為棧頂，a1 端為棧底端為棧底 基本操作：基本操作： ADT Stack數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組5 5 o 棧棧基本運(yùn)算基本運(yùn)算n Setnull（Stack） 置棧為空置棧為空n Empty（Stack） 判定棧是否為空判定棧是否為空n Push（Stack，x）進(jìn)棧操作，在棧頂插入元素）進(jìn)棧操作，在棧頂插入元素n Pop（Stack） 出棧操作，刪除棧頂元素出棧操作，刪除棧頂元素n Gettop（Stac

4、k） 取棧頂元素取棧頂元素?cái)?shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組6 6 o 棧棧存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)n 順序棧順序棧n 鏈棧鏈棧數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組7 7 o 順序棧順序棧n 概念：概念：o 利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素棧頂?shù)臄?shù)據(jù)元素o 棧的操作只能在一端進(jìn)行棧的操作只能在一端進(jìn)行n 棧頂位置隨進(jìn)棧和出棧而變化棧頂位置隨進(jìn)棧和出棧而變化n 棧的順序存儲(chǔ)結(jié)構(gòu)實(shí)際上是一維數(shù)組棧的順序存

5、儲(chǔ)結(jié)構(gòu)實(shí)際上是一維數(shù)組數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組8 8 o 順序棧順序棧處理過程處理過程top=0base123450?？諚？?23450進(jìn)棧進(jìn)棧ABCDEF出棧出棧123450ABCDEFtoptop數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組9 9 o 順序棧順序棧提示提示n 若若base的值為的值為NULL，則表明棧結(jié)構(gòu)不存在，則表明棧結(jié)構(gòu)不存在n 若若top=base可作為棧空的標(biāo)志可作為?？盏臉?biāo)志n 棧頂指針棧頂指針top,指向?qū)嶋H棧頂指向?qū)嶋H棧頂

6、后的空位置后的空位置o 初值為初值為0o top=0,?？眨藭r(shí)出棧，則下溢（?？眨藭r(shí)出棧，則下溢（underflow)o top=M,棧滿，此時(shí)入棧，則上溢（棧滿，此時(shí)入棧，則上溢（overflow)n 非空棧中的棧頂指針始終在棧頂元素的下一個(gè)非空棧中的棧頂指針始終在棧頂元素的下一個(gè)位置上位置上o 插入新的棧頂元素時(shí)，指針插入新的棧頂元素時(shí)，指針top增增1o 刪除棧頂元素時(shí)，指針刪除棧頂元素時(shí)，指針top減減1數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組1010 o 順序棧順序棧入棧入棧n Step1Step1：判別棧滿：判別棧

7、滿否，若滿，則顯示否，若滿，則顯示棧溢出信息，停止棧溢出信息，停止執(zhí)行；否則，執(zhí)行執(zhí)行；否則，執(zhí)行step 2step 2； n Step2Step2：棧頂指針：棧頂指針toptop上移上移( (加加1)1)；n Step3Step3：在：在toptop所指所指的位置插入元素的位置插入元素x x。#define MAXSIZE n int stackMAXSIZE; int top = -1; push（int x） if（top = = MAXSIZE -1） printf（“棧上溢棧上溢！n”）; exit （1）; else top + +；/* 棧指針加棧指針加 1 */ stack

8、top = x ； /* 元素元素 x進(jìn)棧進(jìn)棧*/ 數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組1111 o 順序棧順序棧出棧出棧n Step1Step1：判別棧是：判別棧是否為空；若空，則否為空；若空，則輸出輸出 棧下溢信息，棧下溢信息，并停止執(zhí)行；否則，并停止執(zhí)行；否則，執(zhí)行執(zhí)行step2step2；n Step2Step2：彈出（刪：彈出（刪除）棧頂元素；除）棧頂元素； n Step3Step3：棧頂指針：棧頂指針toptop下移下移( (減減1)1)。#define MAXSIZE n int stackMAXSIZE; in

9、t top = -1; pop（ ） int x; if( top = = -1） printf(“ 棧下溢棧下溢 n”); exit(1); else x = stack top ； top - - ； /* 棧頂指針棧頂指針 減減1*/ return x ； 數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組1212 o 鏈棧鏈棧n 概念概念o 用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來表示棧用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來表示棧n 對(duì)于最大空間需要量事先不知的情況，不能使用順序?qū)τ谧畲罂臻g需要量事先不知的情況，不能使用順序棧，需要采用鏈棧棧，需要采用鏈棧n 處理過程處理過程

10、.棧底棧底toptopxptop .棧底棧底topq數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組1313 o 鏈棧鏈棧結(jié)構(gòu)定義結(jié)構(gòu)定義o 鏈棧為空的條件：鏈棧為空的條件：top = NULLo 鏈棧為滿的條件鏈棧為滿的條件: t = NULL n t 為申請(qǐng)的結(jié)點(diǎn)為申請(qǐng)的結(jié)點(diǎn),為為NULL表示失敗表示失敗.struct snode intdata; struct snode *link; ;typedef struct snode SNODE ;數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件

11、技術(shù)基礎(chǔ)課程組1414 o 鏈棧鏈棧入棧入棧n Step1Step1：申請(qǐng)一個(gè)：申請(qǐng)一個(gè)鏈棧結(jié)點(diǎn)鏈棧結(jié)點(diǎn), ,若若t=NULL,t=NULL,則表示鏈則表示鏈滿滿; ;否則否則, ,執(zhí)行執(zhí)行step2 ;step2 ;n Step2Step2：在：在toptop所指所指結(jié)點(diǎn)之前插入新結(jié)結(jié)點(diǎn)之前插入新結(jié)點(diǎn)點(diǎn), ,并將并將toptop指向新指向新申請(qǐng)的結(jié)點(diǎn)申請(qǐng)的結(jié)點(diǎn)t t。push(SNODE *top , int x) SNODE *t; t=(SNODE * ) malloc(sizeof(SNODE); if(t = = NULL ) printf(“內(nèi)存中已無(wú)可用空內(nèi)存中已無(wú)可用空 間間n

12、”); exit(1); else t - data = x; t - link = top; top= t; 數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組1515 o 鏈棧鏈棧出棧出棧n Step1Step1：若鏈棧為：若鏈棧為空，則輸出棧溢出空，則輸出棧溢出信息；否則，執(zhí)行信息；否則，執(zhí)行step 2step 2。n Step2Step2：刪除：刪除toptop所所指結(jié)點(diǎn)，并使指結(jié)點(diǎn)，并使top top 指向被刪除結(jié)點(diǎn)的指向被刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)。后繼結(jié)點(diǎn)。n Step3Step3：釋放被刪：釋放被刪除結(jié)點(diǎn)的存儲(chǔ)空間。除結(jié)點(diǎn)的存儲(chǔ)空

13、間。pop (SNODE * top) SNODE *p; int x; if( top = = NULL ) printf(“棧溢出棧溢出n”）；）； exit(1); else p = top； top = top- link ； x = p- data ； free(p) ; 數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組1616 o 隊(duì)列隊(duì)列n 隊(duì)列是一種特殊的線性表，它只允許在表的隊(duì)列是一種特殊的線性表，它只允許在表的前端（前端（frontfront）進(jìn)行刪除操作，而在表的后）進(jìn)行刪除操作，而在表的后端（端（rearrear）

14、進(jìn)行插入操作。）進(jìn)行插入操作。o 隊(duì)尾隊(duì)尾(rear)允許插入的一端允許插入的一端o 隊(duì)頭隊(duì)頭(front)允許刪除的一端允許刪除的一端n 隊(duì)列中沒有元素時(shí)，稱為空隊(duì)列隊(duì)列中沒有元素時(shí)，稱為空隊(duì)列n 隊(duì)列特點(diǎn)隊(duì)列特點(diǎn)o 先進(jìn)先出先進(jìn)先出(FIFO)a1 a2 a3.an 入隊(duì)入隊(duì)出隊(duì)出隊(duì)frontrear隊(duì)列隊(duì)列Q=(a1,a2,an)數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組1717 o 隊(duì)列隊(duì)列定義定義ADT Queue 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R

15、1 | ai-1, ai D, i=2,.,n 約定其中約定其中a1 端為隊(duì)列頭，端為隊(duì)列頭， an 端為隊(duì)列尾端為隊(duì)列尾 基本操作：基本操作： ADT Queue數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組1818 o 隊(duì)列隊(duì)列隊(duì)列類型隊(duì)列類型n 順序隊(duì)列順序隊(duì)列o 用一維數(shù)組表示的隊(duì)列用一維數(shù)組表示的隊(duì)列n 循環(huán)隊(duì)列循環(huán)隊(duì)列o 將順序隊(duì)列臆造為一個(gè)環(huán)狀的空間將順序隊(duì)列臆造為一個(gè)環(huán)狀的空間n 鏈隊(duì)列鏈隊(duì)列o 用鏈表表示的隊(duì)列用鏈表表示的隊(duì)列數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)

16、基礎(chǔ)課程組1919 o 順序隊(duì)列順序隊(duì)列n 順序存儲(chǔ)結(jié)構(gòu)采用一維數(shù)組結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)采用一維數(shù)組結(jié)構(gòu)(c(c語(yǔ)言語(yǔ)言) )o 順序存儲(chǔ)的隊(duì)列中，每次出隊(duì)列的元素必定是隊(duì)順序存儲(chǔ)的隊(duì)列中，每次出隊(duì)列的元素必定是隊(duì)頭元素，因此如果采取與普通順序表同樣的操作頭元素，因此如果采取與普通順序表同樣的操作方式，則每次出隊(duì)操作必然將整個(gè)隊(duì)列向前移動(dòng)，方式，則每次出隊(duì)操作必然將整個(gè)隊(duì)列向前移動(dòng)，這使得效率大大降低。這使得效率大大降低。o 規(guī)定隊(duì)頭指針規(guī)定隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針隊(duì)尾指針rear指向隊(duì)尾元素所在位置，指向隊(duì)尾元素所在位置，入隊(duì)和入隊(duì)和出隊(duì)操作

17、的出隊(duì)操作的執(zhí)行步驟都是首先執(zhí)行執(zhí)行步驟都是首先執(zhí)行指針移動(dòng)，再指針移動(dòng)，再進(jìn)行元素讀寫。進(jìn)行元素讀寫。 #define MAXSIZE n int queueMAXSIZ； int front,rear;數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組2020 o 順序隊(duì)列順序隊(duì)列執(zhí)行約定執(zhí)行約定n 設(shè)數(shù)組維數(shù)為設(shè)數(shù)組維數(shù)為M，則：則：o frontfront為隊(duì)頭指針為隊(duì)頭指針, ,指示隊(duì)頭元素的位置指示隊(duì)頭元素的位置o rear rear 為隊(duì)尾指針為隊(duì)尾指針, ,指示隊(duì)尾元素的位置指示隊(duì)尾元素的位置o 初值初值front=rear

18、=-1o 空隊(duì)列條件：空隊(duì)列條件：front=rearo 入隊(duì)列：入隊(duì)列：sq+rear=x;o 出隊(duì)列：出隊(duì)列： front = front +1 ；x = queue front ；數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組2121 o 順序隊(duì)列順序隊(duì)列入隊(duì)入隊(duì)/ /出隊(duì)操作出隊(duì)操作(1)空隊(duì)列空隊(duì)列rear(2)A，B，C入隊(duì)入隊(duì)A B CForntForntrear入隊(duì)時(shí)，入隊(duì)時(shí)，rear在變?cè)谧?3)A，B出隊(duì)，出隊(duì)， D,E入隊(duì)入隊(duì)C D E Forntrear出隊(duì)時(shí)，出隊(duì)時(shí)，front在變?cè)谧償?shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東

19、北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組2222 o 順序隊(duì)列順序隊(duì)列入隊(duì)入隊(duì)/ /出隊(duì)操作出隊(duì)操作(1)(1)n 假溢出假溢出o 隨著元素不斷入隊(duì)列、出隊(duì)列，隨著元素不斷入隊(duì)列、出隊(duì)列，rear和和front指針會(huì)不斷向后移動(dòng)（如圖指針會(huì)不斷向后移動(dòng)（如圖(2)（3）所示），）所示），最終會(huì)指向數(shù)組的最大下標(biāo)位置（如圖最終會(huì)指向數(shù)組的最大下標(biāo)位置（如圖(4)所所示）。由于示）。由于rear和和front指針只能單方向移動(dòng)，指針只能單方向移動(dòng)，這時(shí)元素?zé)o法入隊(duì)列，但是隊(duì)列中仍有大量空這時(shí)元素?zé)o法入隊(duì)列，但是隊(duì)列中仍有大量空閑位置閑位置,這種情況稱為假溢出。

20、這種情況稱為假溢出。(4)反復(fù)出隊(duì)反復(fù)出隊(duì)/入隊(duì)入隊(duì)Forntrear假溢出發(fā)生假溢出發(fā)生數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組2323 o 順序隊(duì)列順序隊(duì)列溢出溢出n 當(dāng)當(dāng)front=-1,rear=M-1時(shí)，再有元素入隊(duì)時(shí)，再有元素入隊(duì)發(fā)生溢出發(fā)生溢出真溢出真溢出n 當(dāng)當(dāng)front -1,rear=M-1時(shí)，再有元素入隊(duì)時(shí)，再有元素入隊(duì)發(fā)生溢出發(fā)生溢出假溢出假溢出n 如何解決？如何解決？當(dāng)當(dāng)rear = MAXSIZE+1 時(shí)，即超過隊(duì)列末端時(shí)，時(shí)，即超過隊(duì)列末端時(shí)，令令rear = 1；從而使隊(duì)列的首尾相連接。；從而使隊(duì)列

21、的首尾相連接。 用表達(dá)式描述用表達(dá)式描述: if （rear MAXSIZE ） rear = 1 ; else rear = rear + 1 ;數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組2424 o 循環(huán)隊(duì)列循環(huán)隊(duì)列基本思想基本思想n 把隊(duì)列設(shè)想成環(huán)形，讓把隊(duì)列設(shè)想成環(huán)形，讓sq0接在接在sqM-1之后，若之后，若rear+1=M,則令則令rear=0;n 實(shí)現(xiàn)實(shí)現(xiàn)o 入隊(duì)入隊(duì)n rear=(rear+1)%M; sqrear=x;o 出隊(duì)出隊(duì)n front=(front+1)%M; x=sqfront;0M-11frontre

22、ar.數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組2525 o 循環(huán)隊(duì)列循環(huán)隊(duì)列基本思想基本思想(1)(1)n 為了將隊(duì)空和隊(duì)滿的條件加以區(qū)分，一般不為了將隊(duì)空和隊(duì)滿的條件加以區(qū)分，一般不使用使用front指針?biāo)傅奈恢弥羔標(biāo)傅奈恢胦 隊(duì)空條件為隊(duì)空條件為front=rearo 隊(duì)滿條件為隊(duì)滿條件為(rear+1)%M=front30124567frontrear循環(huán)隊(duì)列空循環(huán)隊(duì)列空30124567frontrearABCDFGE循環(huán)隊(duì)列滿循環(huán)隊(duì)列滿30124567frontrearABCD非空循環(huán)隊(duì)列非空循環(huán)隊(duì)列數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2

23、007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組2626 o 循環(huán)隊(duì)列循環(huán)隊(duì)列常用算法常用算法n 入隊(duì)操作入隊(duì)操作o Step1Step1：判別隊(duì)列是否已滿：判別隊(duì)列是否已滿; ;o Step2Step2：隊(duì)尾指針后移一個(gè)位置：隊(duì)尾指針后移一個(gè)位置, ,將新結(jié)點(diǎn)將新結(jié)點(diǎn)元素值存入當(dāng)前結(jié)點(diǎn)單元。元素值存入當(dāng)前結(jié)點(diǎn)單元。addqueue(int x) if (front = = rear % MAXIZE +1 ) printf(“循環(huán)隊(duì)列已滿循環(huán)隊(duì)列已滿n”); exit(1); else rear = rear % MAXSIZE +1; queuerea

24、r = x ; 數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組2727 o 循環(huán)隊(duì)列循環(huán)隊(duì)列常用算法常用算法n 出隊(duì)操作出隊(duì)操作o Step1Step1：判別隊(duì)列是否為空：判別隊(duì)列是否為空; ;若空若空, ,則顯示隊(duì)列則顯示隊(duì)列下下溢溢; ;o Step2Step2：隊(duì)頭指針后移一個(gè)位置。：隊(duì)頭指針后移一個(gè)位置。delqueue( ) int m; if ( front = = rear ) printf( “ 循環(huán)隊(duì)列已空循環(huán)隊(duì)列已空n”) ; m = -1 ； else front = front % MAXSIZE +1 ； m=

25、 queuefront ； return m ； 數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組2828 o 鏈隊(duì)列鏈隊(duì)列n 鏈隊(duì)列實(shí)質(zhì)上就是只能在頭部刪除元素、只能鏈隊(duì)列實(shí)質(zhì)上就是只能在頭部刪除元素、只能在尾部插入元素的單鏈表在尾部插入元素的單鏈表o 隊(duì)頭指針隊(duì)頭指針frontfront就是單鏈表的頭指針就是單鏈表的頭指針o 隊(duì)尾指針隊(duì)尾指針rearrear則是指向單鏈表最后一個(gè)結(jié)點(diǎn)的指針則是指向單鏈表最后一個(gè)結(jié)點(diǎn)的指針頭結(jié)點(diǎn)頭結(jié)點(diǎn) .front隊(duì)頭隊(duì)頭隊(duì)尾隊(duì)尾rear存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言描述，語(yǔ)言描述， struct qnod

26、e int data ； struct qnode * next； ；typedef struct qnode QNODE ；QNODE *front， *rear；數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組2929 o 鏈隊(duì)列鏈隊(duì)列操作操作frontrearx入入隊(duì)隊(duì)xfrontreary入入隊(duì)隊(duì)xyfront rear空隊(duì)空隊(duì)Queue.front = Queue.rear數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組3030 o 鏈隊(duì)列鏈隊(duì)列操作操作(1)(1)fron

27、trearx出出隊(duì)隊(duì)xyfront reary出出隊(duì)隊(duì)數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組3131 o 鏈隊(duì)列鏈隊(duì)列常用算法常用算法n 入隊(duì)操作入隊(duì)操作o Step1Step1：申請(qǐng)建立一個(gè)新結(jié)點(diǎn)：申請(qǐng)建立一個(gè)新結(jié)點(diǎn)T;T;o Step2Step2：判別：判別T T是否為空是否為空; ;若空若空, ,表示隊(duì)列已滿表示隊(duì)列已滿; ;o Step3Step3：非空：非空, ,將將T T插入鏈中插入鏈中, ,修改修改rearrear指針。指針。addqueue(int x) QNODE *t; t = (QNODE*)malloc(

28、sizeof(QNODE); if （ t = = NULL） printf（“ 內(nèi)存無(wú)可用空間內(nèi)存無(wú)可用空間n”); exit(1); else rear - next = t; rear = t; t -data = x; t -next = NULL ; 數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組3232 o 鏈隊(duì)列鏈隊(duì)列常用算法常用算法n 出隊(duì)操作出隊(duì)操作o 判別隊(duì)列是否為空判別隊(duì)列是否為空; ;若若空空, ,則顯示隊(duì)列則顯示隊(duì)列下下溢溢; ;o 非空非空, ,則判別隊(duì)長(zhǎng)度是則判別隊(duì)長(zhǎng)度是否為否為1;1;n 為為1,1,則修

29、改頭、尾指針；則修改頭、尾指針；n 不為不為1,1,修改頭指針修改頭指針; ;o 釋放釋放T T。delqueue( ) int n; QNODE *t; if ( front = = rear) printf(“鏈隊(duì)列已空鏈隊(duì)列已空n”); exit(1) ; else t = front-next; n = t- data ; front-next = t-next; if (t-next = = NULL ) rear = front; free(t); return x; 數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組3333

30、o 應(yīng)用應(yīng)用n 計(jì)算表達(dá)式計(jì)算表達(dá)式o 正確地定義運(yùn)算規(guī)則正確地定義運(yùn)算規(guī)則n 算數(shù)表達(dá)式的計(jì)算規(guī)則算數(shù)表達(dá)式的計(jì)算規(guī)則先括號(hào)內(nèi)，再括號(hào)外先括號(hào)內(nèi)，再括號(hào)外先乘除、后加減先乘除、后加減從左到右從左到右o 計(jì)算機(jī)識(shí)別表達(dá)式計(jì)算機(jī)識(shí)別表達(dá)式n規(guī)定規(guī)定表達(dá)式由操作數(shù)（表達(dá)式由操作數(shù)（Operand）和操作符）和操作符（Operator）和定界符（）和定界符（Delimiter）組成）組成例如，例如，#3*（7-2）#；n 實(shí)際處理表達(dá)式是用兩個(gè)棧結(jié)構(gòu)實(shí)際處理表達(dá)式是用兩個(gè)棧結(jié)構(gòu)OPTR（算符）和（算符）和OPND（操作數(shù)）加運(yùn)算規(guī)則組成（操作數(shù)）加運(yùn)算規(guī)則組成限于二元運(yùn)算符的表達(dá)式定義限于二元運(yùn)算符

31、的表達(dá)式定義: 表達(dá)式表達(dá)式 := (操作數(shù)操作數(shù)) + (運(yùn)算符運(yùn)算符) + (操作數(shù)操作數(shù)) 操作數(shù)操作數(shù) := 簡(jiǎn)單變量簡(jiǎn)單變量 | 表達(dá)式表達(dá)式 簡(jiǎn)單變量簡(jiǎn)單變量 : = 標(biāo)識(shí)符標(biāo)識(shí)符 | 無(wú)符號(hào)整數(shù)無(wú)符號(hào)整數(shù)數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組3434 o 應(yīng)用應(yīng)用(1)(1)n 計(jì)算表達(dá)式計(jì)算表達(dá)式o 表達(dá)式的三種標(biāo)識(shí)方法（設(shè)表達(dá)式的三種標(biāo)識(shí)方法（設(shè) Exp = S1+OP+S2）n 前綴表示法：前綴表示法：OP + S1 + S2n 中綴表示法：中綴表示法：S1 + OP + S2n 后綴表示法：后綴表示法：S1

32、 + S2 + OPn 前綴式的運(yùn)算規(guī)則為前綴式的運(yùn)算規(guī)則為連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)連續(xù)出現(xiàn)的兩個(gè)操作數(shù)和在它們之前且緊靠它們的運(yùn)算符構(gòu)成一個(gè)最小表達(dá)式算符構(gòu)成一個(gè)最小表達(dá)式;n 中綴式丟失了括弧信息，致使運(yùn)算的次序不確定中綴式丟失了括弧信息，致使運(yùn)算的次序不確定n 后綴式的運(yùn)算規(guī)則為后綴式的運(yùn)算規(guī)則為運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序運(yùn)算符在式中出現(xiàn)的順序恰為表達(dá)式的運(yùn)算順序;每個(gè)每個(gè)運(yùn)算符和在它之前出現(xiàn)運(yùn)算符和在它之前出現(xiàn) 且緊靠它的兩個(gè)操作數(shù)構(gòu)成一且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式個(gè)最小表達(dá)式例如例如:表達(dá)式表達(dá)式Exp = a b + (c d / e

33、) f前綴式前綴式: + a b c / d e f中綴式中綴式: a b + c d / e f后綴式后綴式: a b c d e / f + 數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組3535 o 應(yīng)用應(yīng)用(2)(2)n 計(jì)算表達(dá)式計(jì)算表達(dá)式o 結(jié)論結(jié)論n 操作數(shù)之間的相對(duì)次序不變操作數(shù)之間的相對(duì)次序不變n 運(yùn)算符的相對(duì)次序不同運(yùn)算符的相對(duì)次序不同數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組3636 o 應(yīng)用應(yīng)用(3)(3)n 計(jì)算表達(dá)式計(jì)算表達(dá)式o 利用后綴式求值處理

34、的方法利用后綴式求值處理的方法n 先找運(yùn)算符，再找操作數(shù)先找運(yùn)算符，再找操作數(shù)n 例：例：a b c d e / f +axbd/ec-(d/e)(c-(d/e)xfaxb+ (c-(d/e)xf數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組3737 o 應(yīng)用應(yīng)用(4)(4)n 計(jì)算表達(dá)式計(jì)算表達(dá)式o 如何從原表達(dá)式求得后綴式？如何從原表達(dá)式求得后綴式？n 分析分析 “原表達(dá)式原表達(dá)式” 和和 “后綴式后綴式”中的運(yùn)算符中的運(yùn)算符n 每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來定每個(gè)運(yùn)算符的運(yùn)算次序要由它之后的一個(gè)運(yùn)算符來定在后綴式中，優(yōu)先數(shù)高的運(yùn)算符領(lǐng)先于優(yōu)先數(shù)低的在后綴式中，優(yōu)先數(shù)高的運(yùn)算符領(lǐng)先于優(yōu)先數(shù)低的運(yùn)算符運(yùn)算符a + b c d / e fa b c + d e / f 數(shù)據(jù)結(jié)構(gòu)棧和隊(duì)列2007東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程組東北大學(xué)網(wǎng)絡(luò)學(xué)院計(jì)算機(jī)軟件技術(shù)基礎(chǔ)課程