數(shù)據(jù)結構(Java版) 模塊3 棧和隊列

上課啦THEPOWERPOINTTEMPALTE模塊3棧和隊列實例引入1棧2隊列3應用舉例4小結5學習目的與要求重點：棧和隊列的特點棧和隊列的進出運算循環(huán)隊列的特點及基本運算難點：棧和隊列的相關運算使用棧和隊列解決實際應用問題3.1實例引入【實例1】棧的實例

棧是用來保存一些尚未處理而又等待處理的數(shù)據(jù)項，這些數(shù)據(jù)項的使用順序與保存數(shù)據(jù)相反。

棧在日常生活中幾乎到處可見，如槍支上的子彈匣，后壓入的子彈總是先射出；餐館中餐盤的堆疊和使用；瀏覽器中后退功能的實現(xiàn)；各種應用軟件中撤銷操作的實現(xiàn)；在程序設計中，經常會需要棧這樣的數(shù)據(jù)結構，例如，在for循環(huán)嵌套執(zhí)行過程中，開始執(zhí)行時，外層循環(huán)先開始，內層循環(huán)后開始，在結束時，內層循環(huán)先結束，外層循環(huán)后結束，這就形成了一個棧；函數(shù)和過程調用都是棧的具體應用。3.1實例引入【實例2】隊列實例

隊列在現(xiàn)實生活中無處不在，例如，去火車站、銀行、醫(yī)院等服務行業(yè)辦理業(yè)務都存在排隊問題；甚至在生產管理中，也存在生產任務的排隊計劃和管理問題。隊列在計算機系統(tǒng)中的應用也非常廣泛，例如，操作系統(tǒng)中的作業(yè)排隊；在允許多道程序運行的計算機系統(tǒng)中，同時有幾個作業(yè)運行，如果運行的結果都需要通過通道輸出，那就要按請求輸出的先后次序排隊，每當通道傳輸完畢可以接受新的輸出任務時，排在前面的作業(yè)先從隊列中退出作輸出操作，凡是申請輸出的作業(yè)都是從隊尾進入隊列。3.2.1棧的概念及基本運算1．基本概念棧（Stack）是限制在表的一端進行插入和刪除的線性表。允許插入、刪除的一端稱為棧頂（top）。無法進行數(shù)據(jù)操作的固定端稱為棧底（bottom）。當表中沒有元素時稱為空棧。棧上溢（Full）是指在棧內空間已存滿數(shù)據(jù)時，如果仍希望能做進棧動作，就會產生“上溢出”，這是一種空間不足的出錯狀態(tài)。棧下溢（Empty）是指在棧內空間已無數(shù)據(jù)時，如果仍然希望能做出棧操作，就會產生“下溢出”，這是一種數(shù)據(jù)不足的出錯狀態(tài)。3.2.1棧的概念及基本運算2．棧的特點

由于棧的插入和刪除操作都是在棧頂進行，所以先進棧的元素后出棧，最后進棧的元素先出棧，基于這個特點，棧又稱為后進先出（LastInFirstOut）的線性表，簡稱為LIFO表。如圖3.1所示，元素是以a1，a2，…，an的順序進棧，出棧的次序卻是an，…，a2，a1。3.2.1棧的概念及基本運算3．進棧出棧變化形式思考：最先進棧的元素，就只能最后出棧呢？答案是不一定。棧對線性表的插入和刪除的位置進行了限制，并沒有對元素進出的時間進行限制，也就是說，在不是所有元素都進棧的情況下，事先進去的元素也可以出棧，只要保證是棧頂元素出棧就可以。例如：現(xiàn)有a1，a2，a3三個元素依次進棧，會有哪些出棧次序呢？第一種：a1，a2，a3進，a3，a2，a1出，出棧序列為a3，a2，a1。第二種：a1進，a1出，a2進，a2出，a3進，a3出，出棧序列為a1，a2，a3。第三種：a1，a2進，a2，a1出，a3進，a3出，出棧序列為a2，a1，a3。第四種：a1進，a1出，a2，a3進，a3，a2出，出棧序列為a1，a3，a2。第五種：a1，a2進，a2出，a3進，a3出，a1出，出棧序列為a2，a3，a1。3.2.1棧的概念及基本運算4．棧的基本運算（1）initStack（S）初始化。構造一個空棧S。（2）stackEmpty（S）判棧空。若S為空棧，則返回true，否則返回false。（3）stackFull（S）判棧滿。若S為滿棧，則返回true，否則返回false。注意：該運算只適用于棧的順序存儲結構。（4）push（S，e）進棧。若棧S不滿，則將元素e插入S的棧頂。（5）pop（S）出棧。若棧S非空，則將S的棧頂元素刪去。3.2.2棧的順序存儲結構及其算法實現(xiàn)1．順序棧的基本概念

順序棧，即棧的順序存儲結構，是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素。

通常用一維數(shù)組stack[0..stackSize-1]來實現(xiàn)棧的順序存儲，大小stackSize預先定義。stack[0]端表示棧底，設一個整型指針top指向棧頂元素，top=-1時為空棧；每進棧一個元素，指針top加1；每出棧一個元素，指針top減1；top=stackSize-1時表示棧滿。圖3.2表示了順序棧中數(shù)據(jù)元素和棧頂指針之間的對應關系。3.2.2棧的順序存儲結構及其算法實現(xiàn)2．順序棧的類定義public

classArrStack{//定義順序棧

private

int[]stack;

private

inttop;

publicArrStack(intsize){//構造方法 stack=new

int[size]; top=-1; } //成員方法

public

final

int[]getStack(){

returnstack; }

public

final

voidsetStack(int[]stack){

this.stack=stack; }

public

final

intgetTop(){

returntop; }

public

final

voidsetTop(inttop){

this.top=top; }}3.2.2棧的順序存儲結構及其算法實現(xiàn)3．順序棧的基本運算（1）初始化public

voidinitStack(){ //將順序棧置空 top=-1;}（2）判?？誴ublic

booleanstackEmpty(){ //判斷一個棧是否為空，若空，返回true，否則返回false

return(top==-1);}（3）判棧滿public

booleanstackFull(){ //判斷一個棧是否已滿，若滿，返回true，否則返回false

if(top==stack.length-1)

return

true;

else

return

false;}3.2.2棧的順序存儲結構及其算法實現(xiàn)3．順序棧的基本運算（4）進棧publicvoidpush(inte){ //入棧操作

if(stackFull()){//判棧滿 System.out.println("棧滿");//返回出錯信息，退出運行

return; } stack[++top]=e;//棧頂指針加1后將e入棧}（5）出棧public

voidpop(){ //出棧操作

if(stackEmpty())//判?？? System.out.println("空棧");//返回出錯信息，退出運行 else

intstackTop=stack[top--];//棧頂元素放到變量stackTop，棧頂指針減1}以上運算都沒有涉及任何循環(huán)語句，因此，時間復雜度均是O（1）。3.2.2棧的順序存儲結構及其算法實現(xiàn)4．共享同一數(shù)組空間的雙棧結構

當程序中同時使用兩個棧時，可以將兩個棧的棧底設在數(shù)組空間的兩端，兩個棧頂指針分別向中間延伸，如圖3.3所示。當一個棧里的元素較多，超過數(shù)組空間的一半時，只要另一個棧的元素不多，那么前者就可以占用后者的部分存儲空間。3.2.3棧的鏈式存儲結構及其算法實現(xiàn)1．鏈棧的基本概念

鏈棧，即棧的鏈式存儲結構。通常用不帶頭結點的單鏈表表示一個棧，設置一個棧頂指針top，進棧和出棧都在top端進行，如圖3.4所示。棧頂指針就是鏈表的頭指針。鏈棧是動態(tài)存儲結構，元素個數(shù)動態(tài)變化，預先不需要指定。3.2.3棧的鏈式存儲結構及其算法實現(xiàn)2．鏈棧的類型定義public

classLinkedStack{

private

intdata;//數(shù)據(jù)域，可根據(jù)實際情況修改

privateLinkedStacknext;//指針域，存放當前元素直接后繼元素的地址

privateLinkedStacktop;//棧頂指針

privateintcount;//進棧元素計數(shù)器

publicLinkedStack(){//構造方法,創(chuàng)建一個空棧top=null;}//成員方法

public

intgetData(){

returndata;}

public

voidsetData(intdata){

this.data=data;}

publicLinkedStackgetNext(){

returnnext;}

public

voidsetNext(LinkedStacknext){

this.next=next;}}3.2.3棧的鏈式存儲結構及其算法實現(xiàn)3．鏈棧的基本運算（1）初始化public

voidinitStack(){//將鏈棧置空top=null;}（2）判?？誴ublic

booleanstackEmpty(){//判斷一個棧是否為空，若空，返回true，否則返回false

return(top==null);}（3）進棧public

voidpush(LinkedStacknewNode){//入棧操作newNode.setNext(top);top=newNode;count++;}3.2.3棧的鏈式存儲結構及其算法實現(xiàn)3．鏈棧的基本運算（4）出棧public

voidpop(){//出棧操作LinkedStackq;

if(stackEmpty())//判?？誗ystem.out.println("?？?);//返回出錯信息，退出運行

else{q=top;top=top.next;count--;}}注意：鏈棧中的結點是動態(tài)分配的，所以可以不考慮上溢，無須定義stackFull運算。以上運算都沒有涉及任何循環(huán)語句，因此，時間復雜度均是O(1)。3.2.4棧在Java類庫中的實現(xiàn)Java類庫中的java.util.Stack類實現(xiàn)了棧的功能，其直接父類是Vector類，其常用的構造方法和成員方法如下：1）構造方法publicStack()//創(chuàng)建一個空棧2）常用成員方法publicObjectpush(Objectitem)//進棧一個元素publicObjectpop()//出棧一個元素publicbooleanempty()//判斷棧是否為空publicintsize()//獲取棧中元素的個數(shù)publicObjectpeek()//返回棧頂元素publicintsearch(Objecto)//返回對象在棧中的位置，以1為基數(shù)3.3.1隊列的概念及基本運算1．基本概念隊列（Queue）是只允許在一端進行插入，而在另一端進行刪除的運算受限的線性表。允許刪除的一端稱為隊頭（front）。允許插入的一端稱為隊尾（rear）。當隊列中沒有元素時稱為空隊列。2．隊列的特點隊列的修改是依據(jù)先進先出的原則進行的。新來的成員總是加入隊尾，每次離開的成員總是隊列頭上的。因此，隊列亦稱作先進先出（FirstInFirstOut）的線性表，簡稱為FIFO表。如圖3.5所示，在隊列中依次加入元素a1，a2，…，an之后，a1是隊頭元素，an是隊尾元素。退出隊列的次序只能是a1，a2，…，an。3.3.1隊列的概念及基本運算3．隊列的基本運算（1）initQueue（Q）初始化。構造一個空隊列Q。（2）queueEmpty（Q）判隊空。若隊列Q為空，則返回true，否則返回false。（3）queueFull（Q）判隊滿。若隊列Q為滿，則返回true，否則返回false。注意：此操作只適用于隊列的順序存儲結構。（4）enQueue（Q，e）入隊。若隊列Q非滿，則將元素e插入到Q的隊尾。（5）deQueue（Q）出隊。若隊列Q非空，則刪去Q的隊頭元素。3.3.2隊列的順序存儲結構及其算法實現(xiàn)1．順序隊列的基本概念順序隊列，即隊列的順序存儲結構，是利用一組地址連續(xù)的存儲單元依次存儲從隊頭到隊尾的數(shù)據(jù)元素。通常用一維數(shù)組queue[0..queueSize-1]來實現(xiàn)隊列的順序存儲，設置兩個指針front和rear分別指示隊頭元素和隊尾元素在數(shù)組中的位置，并約定隊頭指針指示隊列中的第一個元素，隊尾指針指示隊尾元素位置的后一個位置。如圖3.6表示了順序隊列中數(shù)據(jù)元素和隊頭、隊尾指針之間的對應關系，歸納如下：（1）隊頭隊尾指針在隊列初始化時均應置為0。（2）入隊時：將新元素插入rear所指的位置，然后將rear加1。（3）出隊時：刪去front所指的元素，然后將front加1。（4）假上溢：由于入隊和出隊操作中，頭尾指針只增加不減小，致使被刪元素的空間永遠無法重新利用。如圖3.6（d）所示，front=2，rear=queueSize時再有元素入隊就會發(fā)生溢出，但隊頭前面還有單元是空的。3.3.2隊列的順序存儲結構及其算法實現(xiàn)

當隊列中實際的元素個數(shù)遠遠小于數(shù)組空間的規(guī)模時，也可能由于尾指針已超越數(shù)組空間的上界而不能做入隊操作。該現(xiàn)象稱為“假上溢”現(xiàn)象。注意：①當頭尾指針相等時，隊列為空。②在非空隊列里，隊頭指針始終指向隊頭元素，尾指針始終指向隊尾元素的下一位置。3.3.2隊列的順序存儲結構及其算法實現(xiàn)2．循環(huán)隊列

為充分利用數(shù)組空間，克服“假上溢”現(xiàn)象，將存放隊列元素的數(shù)組空間想象為一個首尾相接的圓環(huán)，這種形式的順序隊列稱為循環(huán)隊列（CircularQueue）。如圖3.7所示。3.3.2隊列的順序存儲結構及其算法實現(xiàn)（1）循環(huán)隊列的基本操作循環(huán)隊列中進行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。只不過當頭尾指針指向數(shù)組上界（queueSize-1）時，其加1操作的結果是指向數(shù)組的下界0。這種循環(huán)意義下的加1操作可以描述為：①方法一：if(i+1==queueSize)//i表示front或reari=0;elsei++;②方法二：利用"模運算"i=(i+1)%queueSize;3.3.2隊列的順序存儲結構及其算法實現(xiàn)（2）循環(huán)隊列邊界條件處理

如圖3.8所示，在循環(huán)隊列中，由于入隊時尾指針向前追趕頭指針；出隊時頭指針向前追趕尾指針，造成隊空和隊滿時頭尾指針均相等。因此，無法通過條件front=rear來判別隊列是"空"還是"滿"。3.3.2隊列的順序存儲結構及其算法實現(xiàn)解決這個問題的方法至少有三種：①另設一布爾變量以區(qū)別隊列的空和滿。②少用一個元素存儲空間。當隊尾指針所指向的空單元的后繼單元是隊頭元素所在的單元時，則停止入隊。這樣一來，隊尾指針永遠追不上隊頭指針，所以隊滿時不會有front=rear。這時隊滿的條件為(rear+1)%queueSize=front。判隊空的條件不變，仍為front=rear。③使用一個存儲隊列中元素個數(shù)的變量如count，當count=0時為隊空，當count=queueSize時為隊滿。以下關于循環(huán)隊列及其操作算法都基于第3種方法實現(xiàn)。注意：循環(huán)隊列中元素的個數(shù)為(rear-front+queueSize)%queueSize3.3.2隊列的順序存儲結構及其算法實現(xiàn)（3）循環(huán)隊列的類型定義public

classArrQueue{//定義循環(huán)隊列

private

int[]queue;

private

intfront;

private

intrear;

private

intcount;

publicArrQueue(intqueueSize){//構造方法 queue=new

int[queueSize]; front=0; count=0; rear=0; } //成員方法

public

final

intgetFront(){

returnfront; }

public

final

voidsetFront(intfront){

this.front=front; }

public

final

int[]getQueue(){

returnqueue; }

public

final

voidsetQueue(int[]queue){

this.queue=queue; }

public

final

intgetRear(){

returnrear; }

public

final

voidsetRear(intrear){

this.rear=rear; }}3.3.2隊列的順序存儲結構及其算法實現(xiàn)（4）循環(huán)隊列的基本運算①初始化public

voidinitQueue(){ //將循環(huán)隊列置空 front=0; count=0; rear=0;}②判斷隊列是否為空public

boolean

queueEmpty(){ //判斷一個循環(huán)隊列是否為空，若空，返回true，否則返回false

return(count==0);}③判斷隊列是否為滿public

booleanqueueFull(){ //判斷一個循環(huán)隊列是否已滿，若滿，返回true，否則返回false。

return(count==queue.length);}3.3.2隊列的順序存儲結構及其算法實現(xiàn)（4）循環(huán)隊列的基本運算④入隊public

voidenQueue(inte){ //入隊操作

if(queueFull())//判循環(huán)隊列是否已滿 System.out.println("隊列已滿");//返回出錯信息，退出運行

else{ queue[rear]=e; rear=(rear+1)%queue.length; count++; }}⑤出隊public

voiddeQueue(){ //出隊操作

if(queueEmpty())//判隊列是否為空 System.out.println("隊列為空");//返回出錯信息，退出運行 else{

inttemp=queue[front];//隊頭元素放到變量temp，隊頭指針加1 front=(front+1)%queue.length; count--;

}}以上運算都沒有涉及任何循環(huán)語句，因此，時間復雜度均是O（1）。3.3.3隊列的鏈式存儲結構及其算法實現(xiàn)1．鏈隊列的基本概念

鏈隊列，即隊列的鏈式存儲結構。它是限制僅在表頭刪除和表尾插入的單鏈表。對于使用中數(shù)據(jù)元素變動較大的隊列，采用鏈隊列比順序隊列更有利。

為了操作方便，通常用帶頭結點的單鏈表來實現(xiàn)鏈隊列，如圖3.9所示，當一個隊列為空時（即front=rear=null），其頭指針和尾指針都指向頭結點；當隊列非空時，隊頭指針指向頭結點，隊尾指針指向最后一個結點。3.3.3隊列的鏈式存儲結構及其算法實現(xiàn)2．鏈隊列的類型定義public

classLinkedQueue{

private

intdata;//數(shù)據(jù)域，可根據(jù)實際情況修改

privateLinkedQueuenext;//指針域，存放當前元素直接后繼元素的地址

privateLinkedQueuefront;//隊頭指針

privateLinkedQueuerear;//隊尾指針

private

intcount;//進隊列元素計數(shù)器

publicLinkedQueue(){//構造方法,創(chuàng)建一個空隊列 front=rear=null; count=0; } //成員方法public

intgetData(){

returndata; }

public

voidsetData(intdata){

this.data=data; }publicLinkedQueuegetNext(){

returnnext; }

public

voidsetNext(LinkedQueuenext){

this.next=next; }}3.3.3隊列的鏈式存儲結構及其算法實現(xiàn)3．鏈隊列的基本運算（1）初始化public

voidinitQueue(){ //將鏈隊列置空

front=rear=null;}（2）判隊空public

booleanqueueEmpty(){ //判斷一個隊列是否為空，若空，返回true，否則返回false

return(count==0);}（3）入隊public

voidenQueue(LinkedQueuenewNode){ //入隊操作 rear.setNext(newNode); rear=newNode; count++;}3.3.3隊列的鏈式存儲結構及其算法實現(xiàn)3．鏈隊列的基本運算（4）出隊public

voiddeQueue(){ //出隊操作 LinkedQueueq;

if(queueEmpty())//判隊空 System.out.println("隊列為空");//返回出錯信息，退出運行 else{ q=front; front=front.getNext();

if(front==rear)rear=front; count--;

}}以上運算都沒有涉及任何循環(huán)語句，因此，時間復雜度均是O（1）。注意：①和鏈棧類似，無須考慮判隊滿的運算及上溢。②在出隊算法中，一般只需修改隊頭指針。但當原隊中只有一個結點時，該結點既就是隊尾，故刪去此結點時亦需修改尾指針，且刪去此結點后隊列變空。3.3.4隊列在Java類庫中的實現(xiàn)在JAVA5以后的版本中，新增了java.util.Queue接口。該接口擴展了java.util.Collection接口，用于支持隊列的常見操作。另外，java.util.LinkedList類實現(xiàn)了Queue接口，因此，可以把LinkedList類當成隊列結構來使用。常用成員方法如下：publicbooleanadd(Objectobj) //在隊尾添加一個元素，成功返回true,否則返回falsepublicbooleanoffer(Objectobj) //在隊尾添加一個元素，成功返回true,否則返回falsepublicbooleanaddLast(Objectobj) //在隊尾添加一個元素，無返回值publicObjectremoveFisrt() //刪除并返回表頭元素publicObjectremove() //刪除并返回隊頭元素publicObjectpoll() //刪除并返回隊頭元素publicObjectelement() //返回隊頭元素，不刪除publicObjectpeek() //返回隊頭元素，不刪除3.4.1棧的應用實例【例3.1】利用