習題三棧和隊列

-單項選擇題

1.在作進棧運算時，應先判別棧是否（①），在作退棧運算時應先判別棧是否（②)?

當棧中元素為n個，作進棧運算時發生上溢，則說明該棧的最大容量為（③

①，②：A.空B.滿C.上溢D.下溢

(3)：A.n-1B.nC.n+1D.n/2

2.若已知一個棧的進棧序列是1,2,3,?n,其輸出序列為php2,p3,...pn,若

pl=3,則p2為（）o

A可能是2B一定是2C可能是1D一定是1

3.有六個元素6,5,4,3,2,1的順序進棧,問下列哪一個不是合法的出棧序列？()

A.543612B.453126C.346521D.234156

4.設有一順序棧S,元素s,s,s,s,s挨次進棧，如果6個元素出棧的順序是s,s,s

23

s,s，則棧的容量至少應法顯)

51

A.2B.3C.5D.6

5.若棧采用順序存儲方式存儲,現兩棧共享空間top[i]代表第i個棧（i=1,2）

棧頂，棧1的底在v[l],棧2的底在V[m],則棧滿的條件是（）。

A.|top[2]-top[1]|=0B.top[l]+l=top[2]

C.top[l]+top[2]=mD.top[l]=top[2]

6.執行完下列語句段后，i值為：()

intf(intx)

{return((x>0)?x*f(x-1):2);}

inti;

i=f(f(D)；

A.2B.4C.8D.無限遞歸

7.表達式3*2'(4+2*2-6*3)-5求值過程中當掃描到6時，對象棧和算符棧為()，其中

”為乘幕。

A.3,2,4,1,1；(*?+*-B.3,2,8；(*〈

C.3,2,4,2,2；(*'(-D.3,2,8；(*"(-

8.用鏈接方式存儲的隊列，在進行刪除運算時()o

A.僅修改頭指針B.僅修改尾指針

C.頭、尾指針都要修改D.頭、尾指針可能都要修改

9.遞歸過程或者函數調用時，處理參數及返回地址，要用一種稱為（）的數據結構。

A.隊列B.多維數組C.棧D.線性表

10.設C語言數組Data[m+I]作為循環隊列SQ的存儲空間，front為隊頭指針，rear為隊

尾指針，則執行出隊操作的語句為()

A.front=front+lB.fronts(front+1)%m

C.rear=(rear+l)%(m+l)D.front=(front+1)%(m+1)

IL循環隊列的隊滿條件為()

A.(sq.rear+1)%maxsize==(sq.front+1)%maxsize;

B.(sq.front+1)%maxsize==sq.rear

C.(sq.rear+1)%maxsize==sq.front

D.sq.rear==sq.front

12.棧和隊列的共同點是()。

A.都是先進先出B.都是先進后出

C.只允許在端點處插入和刪除元素D.沒有共同點

二、填空題

1.棧是_____的線性表，其運算遵循_______的原則。

2.一個棧的輸入序列是：1,2,3則不可能的棧輸出序列是。

3.用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234,為了得到1342出棧順

序，相應的S和X的操作串為o

4.循環隊列的引入，目的是為了克服。

5.隊列是限制插入只能在表的一端，而刪除在表的另一端進行的線性表，其特點是.

6.己知鏈隊列的頭尾指針分別是f和r,則將值x入隊的操作序列是_____。

7.表達式求值是_____應用的一個典型例子。

8.循環隊列用數組A[O..mT]存放其元素值，已知其頭尾指針分別是front和rear,則當

前隊列的元素個數是。

9.以下運算實現在鏈棧上的初始化，請在處用請適當句子予以填充。

VoidInitStacl(LstackTp*ls){;}

10.'以下運算實現在鏈棧上的進棧，請在處用請適當句子予以填充。

VoidPush(LStackTp*ls,DataTypex)

{LstackTp*p;p=malloc(sizeof(LstackTp));

p->next=ls;

)

11.以下運算實現在鏈棧上的退棧，請在______________處用請適當句子予以填充。

IntPop(LstackTp*ls,DataType*x)

{LstackTp*p;

if(ls!=NULL)

{P=ls;

*x=;

ls=ls->next;

return(1)；

}elsereturn(0);

12.以下運算實現在鏈隊上的入隊列，請在處用適當句子予以填充。

VoidEnQueue(QueptrTp*lq,DataTypex)

{LqueueTp*p;

p=(LqueueTp*)malloc(sizeof(LqueueTp));

_________=x;

p->next=NULL;

(lq->rear)->next=;

}

三、應用題

1.給出棧的兩種存儲結構形式名稱，在這兩種棧的存儲結構中如何判別棧空與棧滿？

2.畫出對算術表達式A-B*C/D-EtF求值時操作數棧和運算符棧的變化過程。

3.將兩個棧存入數組應如何安排最好？這時棧空、棧滿的條件是什么？

4.怎樣判定循環隊列的空和滿？

四、算法設計題

1.借助棧（可用棧的基本運算）來實現單鏈表的逆置運算。

2.設表達式以字符形式已存入數組E［n］中，'中為表達式的結束符，試寫出判斷表達式中

括號（‘（'和'）'）是否配對的C語言描述算法：EXYX（E）;（注：算法中可調用棧操作的基

本算法。）

3.假設以［和（）分別表示入棧和出棧操作。棧的初態和終態均為空，入棧和出棧的操作序

列可表示為僅由I和0組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。

（1）下面所示的序列中哪些是合法的？

A.I0II0I00B.I00I0II0C.III0I0I0D.III00I00

（2）通過對（1）的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回

true,否則返回false（假定被判定的操作序列已存入一維數組中）。

4.設有兩個棧S/S都采用順序棧方式，并且共享一個存儲區［0一maxsize-1］,為了盡量利

用空間，減少溢足前可能，可采用棧頂相向，迎面增長的存儲方式。試設計有關入棧

和出棧的操作算法。

5.請利用兩個棧S1和S2來摹擬一個隊列。已知棧的三個運算定義如下：PUSH（ST,x）:元素

x入ST棧；POP（ST,x）：ST棧頂元素出棧，賦給變量x；Sempty（ST）：判ST棧是否為空。

那末如何利用棧的運算來實現該隊列的三個運算：enqueue:插入一個元素入隊列；dequeue:

刪除一個元素出隊列；queue_empty：判隊列為空。（請寫明算法的思想及必要的注釋）

6.要求循環隊列不損失一個空間全部都能得到利用，設置一個標志tag,以tag為0或

者1來區分頭尾指針相同時的隊列狀態的空與滿，請編寫與此相應的入隊與出隊算法。

7.已知Q是一個非空隊列，S是一個空棧。僅用隊列和棧的ADT函數和少量工作變量，編

寫一個算法，將隊列Q中的所有元素逆置。棧的ADT函數有：

makeEmpty(s:stack);置空棧

push(s:stack;value:datatype);新元素value進棧

pop(s:stack):datatype;出棧，返回棧頂值

isEmpty(s:stack):Boolean;判棧空否

隊列的ADT函數有：

enqueue(q:queue:value:datatype);元素value進隊

deQueue(q:queue):datatype;出隊列，返回隊頭值

isEmpty(q:queue):boolean;判隊列空否

第3章棧和隊列

一單項選擇題

1.BAB

2.A

3.C

4.B

5.B

6.B

7.D

8.D

9.C

10.D

ll.C

12.C

二、填空題

1.操作受限（或者限定僅在表尾進行插入和刪除操作）后進先出

2.312

3.SXSSXSXX

4.假溢出時大量挪移數據元素

5.先進先出

6.s=（LinkedList）malloc（sizeof（LNode））；s->data=x;s->next=r->next；r->next=s；

7.棧

8.(rear-front+m)%m；

9.ls=NULL

10.p->data=x,ls=p

11.p->data,free(p)

12.p->data,P，lq->rear=p

三、應用題

1.【解答】（D順序棧（top用來存放棧頂元素的下標）

判斷棧S空:如果S->top=T表示棧空。

判斷棧S滿：如果S->top==Stack_Size-1表示棧滿。

（2）鏈棧（top為棧頂指針，指向當前棧頂元素前面的頭結點）

判斷棧空：如果top->next==NULL表示棧空。

判斷棧滿：當系統沒有可用空間時，申請不到空間存放要進棧的元素，此時棧滿。

2.設操作數棧是opnd,操作符棧是optr,對算術表達式A-B*C/D-EtF求值，過程如下:

步驟opnd棧optr棧輸入字符主要操作

初始#A-B*C/D-EtF#PUSH(OPTR,'#'

1A#A-B*C/D-EtFit)PUSH(OPND,A)

2A#-二B*C/D-EfF#PUSH(OPTR,f-')

3AB#-B*C/D-EtF#PUSH(OPND,B)

4AB#一**C/D-EtF#PUSHSPTR,'*')

5ABC#一*￡/D-EtF#PUSH(0PND,C)

6AT(T=B*C)#-/ZD-EtFitPUSH(OPND,POP(OPND)*P0P(OPND))

PUSH(0PTR,'/')

7ATD#-/D-EtF#PUSH(OPND,D)

8AT(T=T/D)#-二EtF#x=P0P(OPND);y=P0P(OPND)

T(T=A-T)#-PUSH(OPND,y/x);

x=P0P(OPND);y=POP(OPND);

PUSH(OPND,y-x)

PUSH(OPTR,'-')

9TE#-EtF#PUSH(OPND,E)

10TE#-tPUSH(0PTR,'t')

11TEF#-tE#PUSH(OPND,F)

12TE#X=POP(OPND)Y=POP(OPND)

TS(S=Et#一POP(OPTR)PUSH(OPND,ytx)

F)x=POP(OPND)y=P0P(0PND)

#POP(OPTR)PUSH(OPND,y-x)

R(R=T-S)

3.設棧S1和棧S2共享向量初始時，棧S1的棧頂指針top[0]=0,棧S2的棧頂

指針top[l]=ni+l,當top[0]=0為左棧空，top[l]=m+l為右棧空；當top[0]=0并且top[l]=m+l

時為全棧空。當top[l]-top[0]=l時為棧滿。

4.設順序存儲隊列用一維數組q[m]表示，其中m為隊列中元素個數，隊列中元素在向量中

的下標從0到m-U設隊頭指針為front,隊尾指針是rear,約定front指向隊頭元素的前

一位置，rear指向隊尾元素。當front等于T時隊空，rear等于m-1時為隊滿。由于隊列

的性質(“刪除”在隊頭而“插入”在隊尾)，所以當隊尾指針rear等于m-1時，若front

不等于T,則隊列中仍有空暇單元，所以隊列并非真滿。這時若再有入隊操作，會造成假

“溢出”。其解決辦法有二，一是將隊列元素向前“平移”(占用0至rear-front-1)；二是

將隊列看成首尾相連，即循環隊列(0..m-1)。在循環隊列下，仍定義front=rear時為隊空，

而判斷隊滿則用兩種辦法，一是用“犧牲一個單元”，即rear+l=front(準確記是

(rear+1)%m=front,m是隊列容量)時為隊滿。另一種解法是“設標記”方法,如設標記

tag,tag等于0情況下，若刪除時導致front=rear為隊空；tag=l情況下，若因插入導致

front=rear則為隊滿。

四算法設計題

1.解：方法是先挨次讓單鏈表上的元素進棧，然后再挨次出棧。

Voidinvert(Iklisthead)

{LstackTps;

initstack(s);

p=head;

while(pOnull)

{Push(s,p->data);p=p->next;}

p=head;

while(notemptystack(s))

{pop(s,p->data);p=p->next;}

)

2.[題目分析]判斷表達式中括號是否匹配，可通過棧，簡單說是左括號時進棧，右括號時

退棧。退棧時，若棧頂元素是左括號，則新讀入的右括號與棧頂左括號就可消去。如此下去，

輸入表達式結束時，棧為空則正確，否則括號不匹配。

intEXYX(charE[],intn)

〃E口是有n字符的字符數組，存放字符串表達式，以結束。本算法判斷表達式中圓

括號是否匹配。

{chars[30];〃s是一維數組，容量足夠大，用作存放括號的棧。

inttop=0;//top用作棧頂指針。

s[top]=;//先入棧，用于和表達式結束符號匹配。

inti=0;〃字符數組E的工作指針。

while(E[i]!=)〃逐字符處理字符表達式的數組。

switch(E[i])

{case'(':s[++top]='(';i++;break;

case')，:if(s[top]=，('{top-;i++;break;}

else{printf("括號不配對");exit(0);)

case:if(s[top]==){printf("括號配對nf,);return(1);)

else{printf("括號不配對n");return(0);)〃括號不配對

default:i++；〃讀入其它字符，不作處理。

"/算法結束。

[算法討論]本題是用棧判斷括號匹配的特例：只檢查圓括號的配對。普通情況是檢查花

括號('{'，'}')、方括號('['，)和圓括號('('，')’)的配對問題。編寫算法中如

遇左括號(,或者'(')就壓入棧中，如遇右括號(,或者')')，則與

棧頂元素比較，如是與其配對的括號(左花括號，左方括號或者左圓括號)，則彈出棧頂

元素；否則，就結論括號不配對。在讀入表達式結束符時，棧中若應只剩,表

示括號全部配對成功；否則表示括號不匹配。

止匕外，由于本題只是檢查括號是否匹配，故對從表達式中讀入的不是括號的那些字符，

一律未作處理。再有，假設棧容量足夠大，因此入棧時未判斷溢出。

3.(1)A和D是合法序列，B和C是非法序列。

(2)設被判定的操作序列已存入一維數組A中。

intJudge(charA[])

〃判斷字符數組A中的輸入輸出序列是否是合法序列。如是，返回true,否則返

回false。

{i=0;//i為下標。

j=k=0;//j和k分別為I和字母0的的個數。

while(A[i]!='0')〃當未到字符數組尾就作。

{switch(A[i])

{case”'：j++;break;〃入棧次數增1。

case'O':k++;if(k>j){printf(“序列非法")；exit(0);)

i++;〃不論A[i]是或者'O',指針i均后移。}

if(j!=k){printf("序列非法")；return(false);)

else{printf("序列合法")；return(true);}

"/算法結束。

[算法討論]在入棧出棧序列(即由‘I'和'O'組成的字符串)的任一位置，入棧次

數(”’的個數)都必須大于等于出棧次數(即'O'的個數)，否則視作非法序列，即將

給出信息，退出算法。整個序列(即讀到字符數組中字符串的結束標記'’)，入棧次數

必須等于出棧次數(題目中要求棧的初態和終態都為空)，否則視為非法序列。

4.[題目分析]兩棧共享向量空間，將兩棧棧底設在向量兩端，初始時，si棧頂指針為T,

s2棧頂為maxsize。兩棧頂指針相鄰時為棧滿。兩棧頂相向，迎面增長，棧頂指針指向棧頂

八1素'O

#definemaxsize兩棧共享順序存儲空間所能達到的最多元素數

^defineelemtpint〃假設元素類型為整型

typedefstruct

{elemtpstack[maxsize];〃棧空間

inttop[2];//top為兩個棧頂指針

}stk;

stks;//s是如上定義的結構類型變量，為全局變量。

⑴入棧操作：

intpush(inti,intx)

//入棧操作。i為棧號，i=0表示左邊的棧si,i=l表示右邊的棧s2,x是入棧元素。

入棧成功返回1,否則返回0。

{if(i<0||i>l){printf("棧號輸入不對")；exit(0);}

if(s.top[l]-s.top[0]==l){printf("棧已滿nf,);return(0);)

switch(i)

{case0:s.stack[++s.top[0]]=x;return(1);break;

case1:s.stack[--s.top[l]]=x;return(1);

}

}//push

(2)退棧操作

elemtppop(inti)

〃退棧算法。i代表棧號，i=0時為si棧，i=l時為s2棧。退棧成功返回退棧元素，

否則返回-1。

{if(i<0i>l){printf(“棧號輸入錯誤n")；exit(O);)

switch(i)

{case0:if(s.top[0]==-l){printf(“棧空n")；return(-1)；}

elsereturn(s.stack[s.top[0]--1);

case1:if(s.top[l]-maxsize{printf(“棧空n");return(-1);)

elsereturn(s.stack[s.top[l]++]);

)

"/算法結束

[算法討論]請注意算法中兩棧入棧和退棧時的棧頂指針的計算。兩棧共享空間示意圖

略，S1棧是通常意義下的棧，而S2棧入棧操作時，其棧頂指針左移(減1),退棧時，棧頂

指針右移(加1)。

5.［題目分析］棧的特點是后進先出，隊列的特點是先進先出。所以，用兩個棧si和s2模

擬一個隊列時，si作輸入棧，逐個元素壓棧，以此摹擬隊列元素的入隊。當需要出隊時，

將棧si退棧并逐個壓入棧s2中，si中最先入棧的元素，在s2中處于棧頂。s2退棧，相當

于隊列的出隊，實現了先進先出。顯然，惟獨棧s2為空且si也為空，才算是隊列空。

(1)intenqueue(stacksi,elemtpx)

//si是容量為n的棧，棧中元素類型是elemtp.本算法將x入棧，若入棧成功返回I,

否則返回0。

{if(topl==n&&!Sempty(s2))//topi是棧si的棧頂指針,是全局變量。

{printf("棧滿");return(0);}//si滿s2非空，這時si不能再入棧。

if(topl==n&&Scmpty(s2))〃若s2為空，先將si退棧，元素再壓棧到s2。

{while(!Sempty(si)){POP(si,x);PUSH(s2,x);}

PUSH(si,x);return(1);//x入棧，實現了隊列元素的入隊。

}

(2)voiddequeue(stacks2,si)

//s2是輸出棧，本算法將s2棧頂元素退棧，實現隊列元素的出隊。

{if(!Sempty(s2))〃棧s2不空，則直接出隊。

{P0P(s2,x);printf(“出隊元素為"，x);}

else〃處理s2空棧。

if(Sempty(sl)){printf("隊列空")；exit(0);}//若輸入棧也為空,則判

定隊空。

else〃先將棧si倒入s2中，再作出隊操作。

{while(!Sempty(si))［POP(si,x);PUSH(s2,x);}

P0P(s2,x);〃s2退棧相當隊列出隊。

printf("出隊元素”，x);

)

"/結束算法dequue。

(3)intqueue_empty()

〃本算法判用棧si和s2摹擬的隊列是否為空。

{if(Sempty(si)&&Sempty(s2))return(l);〃隊列空。