一、棧和隊列的定義和特點

棧：受約束的線性表，只允許棧頂元素入棧和出棧

對棧來說，表尾端稱為棧頂，表頭端稱為棧底，不含元素的空表稱為空棧

先進后出，后進先出

隊列：受約束的線性表，只允許在隊尾插入，在隊頭刪除

先進先出，后進后出

二、棧的表示和操作的實現

1.順序棧的表示：存儲結構

#define MAXSIZE 100  //順序棧存儲空間的初始分配址
typedef struct{SElemType *base;  //棧底指針SElemType *top;  //棧頂指針int stacksize;  //棧可用的最大容址
}SqStack;

top指棧頂元素的后一個位置，棧空時top指向的索引定義為-1

S.top = = 0 時，棧空?

S.top == stacksize 時，棧滿

2.順序棧的操作

a.初始化

//初始化
Status InitStack(SqStack &S){//構造一個空棧SS.base = (SElemType*)malloc(MAXSIZE * sizeof(SElemType));if(!S.base) exit(OVERFLOW);  //存儲分配失敗，退出程序S.top = S.base;S.stacksize = MAXSIZE;return OK;
}

b.入棧

當 index = arr.length 時，用戶要入棧，給用戶拋出“棧已滿”的異常（上圖最右邊的情況）

//入棧
Status Push(SqStack &S,SElemType e){//插入元素e為新的棧頂元素if(S.top - S.base >= S.stacksize) {  //棧滿//追加存儲空間S.base = (SElemType*)realloc(S.base,(S.stacksize+MAXSIZE) * sizeof(SElemType));if(!S.base){  //存儲分配失敗exit(OVERFLOW)  //退出程序}S.top = S.base + S.stacksize;S.stacksize += MAXSIZE;}*S.top ++ = e;return OK;
}

c.出棧

如果 index = 0 的時候，用戶要彈棧，給用戶拋出“棧為空”的異常（上圖最右邊的情況）

//出棧
Status Pop(SqStack &S,SElemType &e){//若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERRORif(S.top == S.base){  //棧為空return ERROR;}e = * --S.top;return OK;
}

d.順序取棧頂元素

//順序取棧頂元素
Status GetTop(SqStack S,SElemType &e){//若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERRORif(S.top == S.base){  //棧為空e = *(S.top - 1);  //top指向下面的位置即棧頂，然后指向e，即賦值給ereturn OK;}
}

三、循環隊列的表示和操作的實現

1.循環隊列的表示

在循環隊列的順序存儲結構中，除了用一組地址連續的存儲單元依次存放從隊列頭到隊列尾的元素之外，尚需附設兩個指針 front 和 rear 分別指示隊列頭元素及隊列尾元素的位置

初始化建立空隊列時，令 front = rear = 0, 每當插入新的隊列尾元素時，“尾指針增1”；每當刪除隊列頭元素時，“頭指針增1”。因此，在非空隊列中，頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾元素的下一個位置

我們發現，在隊列滿時和空隊列時，頭指針和尾指針都指向同一個元素，那么如何分辨隊列滿和空隊列？

1、少用一個元素空間， 即隊列空間大小為m時，有m-1個元素就認為是隊滿。這樣判斷隊空的條件不變，良D當頭、尾指針的值相同時， 則認為隊空;而當尾指針在循環意義上加1后是等于頭指針，則認為隊滿。隊空的條件:Q.front ==Q.rear
隊滿的條件:(Q.rear+ 1)%MAXQSIZE == Q.front
入隊:Q.rear=(Q.rear +1)% MAXQSIZE
出隊:Q.front=(Q.front +1)% MAXQSIZE

當前元素個數:(Q.rear-Q.front+MAXQSIZE)% MAXQSIZE

如上圖所示，當J7、J8、J9 進入隊列后，(Q.rear+ 1)%MAXQSIZE 的值等于 Q.front，此時認為隊滿。

2、另設一個標志位以區別隊列是“空”還是“滿"

2.循環隊列的操作

（1）定義存儲結構

#define MAXSIZE 100 
typedef struct{QElemType *base;  //初始化的動態分配存儲空間int front;  //頭指針，若隊列不空，指向隊列頭元素int rear;  //尾指針，若隊列不空，指向隊列尾元素的下一個位置
}SqQueue;

（2）初始化

//初始化
Status InitQueue(SqQueue &Q) {//構造一個空隊列QQ.base = (QElemType *)malloc(MAXSIZE * sizeof(QElemType));if(!Q.base){exit(OVERFLOW);}Q.front = Q.rear = 0;return OK;
}

(3)求元素個數

//求元素個數
int QueueLength(SqQueue Q){//返回Q的元素個數return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

（4）插入新元素

//插入新元素
Status EnQueue(SqQueue &Q,QElemType e){//插入元素e為Q的新的隊尾元素//判斷隊列是否為空if((Q.rear + 1) % MAXSIZE == Q.front){return ERROR;}Q.base[Q.rear] = e;Q.rear = (Q.rear + 1) % MAXSIZE;return OK;
}

（5）刪除元素

//刪除元素
Status DeQueue(SqQueue %Q,QElemType &e){//若隊列不空，則刪除Q的對頭元素，用e返回其值，并返回OK；否則返回ERRORif(Q.front == Q.rear){return ERROR;}e = Q.base[Q.front];Q.front = (Q.front + 1) % MAXSIZE;return OK;
}

四、總結與習題

棧是限定僅在表尾進行插入或刪除的線性表，又稱為后進先出的線性表。棧有兩種存儲表示，順序表示(順序棧)和鏈式表示（鏈棧)。棧的主要操作是進棧和出棧，對于順序棧的進棧和出棧操作要注意判棧滿或棧空。

隊列是一種先進先出的線性表。它只允許在表的一端進行插入，而在另一端刪除元素。隊列也有兩種存儲表示順序表示(循環隊列)和鏈式表示(鏈隊)

棧和隊列的邏輯結構都和線性表一樣，數據元素之間存在一對一的關系。

循環隊列中少用一個元素判斷隊空或隊滿時：

隊空的條件:：Q.front == Q.rear

隊滿的條件：(Q.rear+1)%MAXQSIZE == Q.front

答案：C

答案：C

解釋：棧是后進先出的線性表，一個棧的入棧序列是1，2，3，…,n，而輸出序列的第一個元素為n，說明1，2，3，…，n一次性全部進棧，再進行輸出，所以p1=n，p2=n-1，….pi=n-i+1

答案：D

解釋:對于非循環隊列，尾指針和頭指針的差值便是隊列的長度，而對于循環隊列，差值可能為負數，所以需要將差值加上MAXSIZE(本題為n)，然后與MAXSIZE(本題為n)求余，即(n+r-f)%n

答案：B （方法同第一題）

元素出隊序列默認就是元素的入隊序列

答案：C

解釋:初始棧頂指針top為n+1，說明元素從數組向量的高端地址進棧，又因為元素存儲在向量空間V[1...n]中，所以進棧時top指針先下移變為n，之后將元素x存儲在V[n]

答案：A

解釋:x=top->data將結點的值保存到x中，top=top->link棧頂指針指向棧頂下一結點，即摘除棧頂結點。

答案：D

解釋:一般情況下只修改頭指針，但是，當刪除的是隊列中最后一個元素時，隊尾指針也丟失了，因此需對隊尾指針重新賦值。

答案：D

解釋:數組A[0...m]中共含有m+1個元素，故在求模運算時應除以m+1

答案：B

答案：C