棧是限定僅在表尾進行插入和刪除操作的線性表。表尾端稱為棧頂，表頭端稱為棧底。不含元素的空表稱為空棧。
棧是后進先出的線性表。
隊列是只允許在一端進行插入操作、而在另一端進行刪除操作的線性表。隊列是先進先出的線性表。
1. 棧
(1) 順序棧的表示和實現(xiàn)
順序棧是指利用順序存儲結構實現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時附設指針top指示棧頂元素在順序棧中的位置。另設指針base指示棧底元素在順序棧中的位置。
當top和base的值相等時，表示空棧。
1. 順序棧的存儲結構
#define MAXSIZE 100 /* 存儲空間初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType類型根據(jù)實際情況而定，這里假設為int */
/* 順序棧結構 */
typedef struct{
SElemType *base;//棧底指針
SElemType *top;//棧頂指針
int stacksize;//?？捎玫淖畲笕萘?}
base指針的值為NULL，則表明棧結構不存在。
棧非空時，top始終指向棧頂元素的上一個位置。
2. 順序棧的初始化
- 為順序棧動態(tài)分配一個最大容量為MAXSIZE的數(shù)組空間，使base指向這段空間的基地址，即棧底。
- 棧頂指針top初始值為base。
- stacksize置為棧的最大容量MAXSIZE。
Status InitStack(SqStack &S)
{
S.base = new SElemType[MAXSIZE]; //為順序棧動態(tài)分配一個最大容量為MAXSIZE的數(shù)組空間
if(!S.base) exit(OVERFLOW);//存儲分配失敗
S.top = S.base;//top初始為base，空棧
S.stacksize = MAXSIZE;// stacksize置為棧的最大容量MAXSIZE
return OK;
}
3. 順序棧的入棧
- 判斷棧是否為滿，若滿則返回ERROR。
- 將新的元素壓入棧頂，棧頂指針加1。
Status Push(SqStack &S,SElemType e)
{
// 插入元素e為新的棧頂元素
if(S.top - S.base == S.stacksize) return ERROR;//棧滿
＊S.top ++ = e; //元素e壓入棧頂，棧頂指針加1
return OK;
}
4.出棧
- 判斷棧是否為空，若空則返回ERROR。
- 棧頂指針減1，棧頂元素出棧。
Status Pop(SqStack &S,SElemType &e)
{
//刪除S的棧頂元素，用e 返回其值
if(S.top == S.base) return ERROR ; // ?？? e = *--S.top; //棧頂指針減1，將棧頂元素賦值給e
return OK;
}
5. 取棧頂元素
當棧非空時，此操作返回當前棧頂元素的值，棧頂保持不變。
Status GetTop(SqStack S)
{
if (S.top ! = S.base) //棧非空
return *(S.top -1);//返回棧頂元素的值，棧頂指針不變。
}
(2) 鏈棧的表示和實現(xiàn)
鏈棧是指采用鏈式存儲結構實現(xiàn)的棧。
1. 鏈棧的存儲結構
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
2. 鏈棧的初始化
鏈棧的初始化操作就是構造一個空棧，因為沒必要設頭結點，所以直接將棧頂指針置空即可。
Status InitStack(LinkStack &S)
{//構建一個空棧S，棧頂指針置空
S = NULL:
return OK;
}
3. 鏈棧的入棧
- 為棧元素e分配空間，用指針p指向。
- 將新結點數(shù)據(jù)域置為e。
- 將新結點插入棧頂
- 修改棧頂指針為p。
Status Push(LinkStack &S,SElemType e)
{
p = new StackNode; //生成新結點
p->data = e;//將新結點數(shù)據(jù)域置為e
p->next = S;//將新結點插入棧頂
S = p;//修改棧頂指針為p
return OK;
}
4. 鏈棧的出棧
- 判斷棧是否為空，若空則返回ERROR。
- 將棧頂元素賦值給e。
- 臨時保存棧頂元素的空間，以備釋放。
- 修改棧頂指針，指向新的棧頂元素。
- 釋放元棧頂元素
Status Pop(LinkStack &S,SElemType &e)
{
//刪除S的棧頂元素，用e返回其值。
if(S==NULL) return ERROR;
e = S -> data;
p = S;
S = S->next;
delete p;
return OK;
}
5. 取棧頂元素
SElemType GetTop (LinkStack S)
{
if(S != NULL) //棧非空
return S->data;//返回棧頂元素，棧指針不變。
}
(3) 棧與遞歸
Hanoi塔問題
- 每次只能移動一個圓盤。
2.圓盤可以插在A、B和C中的任一塔座上。 -
任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上。
Hanoi塔問題的遞歸算法
- 如果 n＝1,則直接將編號為1的圓盤從A移到C，遞歸結束。
- 否則：
1.遞歸，將A上編號為1至n-1的圓盤移到B，C做輔助塔。
- 直接將編號為n的圓盤從A移到C。
- 遞歸，將B上編號為1至n-1的圓盤移動到C，A做輔助塔。
void Hanoi(int n,char A,,char B,char C)
{
if (n == 1) move(A,1,C); //將編號為1的圓盤從A移到C
else
{
Hanoi(n-1,A,C,B); //將A上編號為1至n-1的圓盤移到B，C做輔助
move(A,n,C);//將編號為 n的圓盤從A移到C
Hanoi(n-1,B,A,C);//將B上編號為1至n-1的圓盤移到C，A做輔助
}
}
/* 將搬動操作定義為move(A,n,C)，是指將編號為n的圓盤從A移動到C，同時設置一個初始值為0的全局變量m,對搬動進行計數(shù)。*/
int m;
void move(char A,int n,char C)
{
count<<++m<<","<<n<<","<<A<<","<<C<<endl;
}
2. 隊列
(1) 循環(huán)隊列-隊列的順序表示和實現(xiàn)
1. 隊列的順序存儲結構
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存儲空間初始分配量 */
typedef int Status;
typedef int QElemType; /* QElemType類型根據(jù)實際情況而定，這里假設為int */
/* 循環(huán)隊列的順序存儲結構 */
typedef struct{
QElemType *base /*存儲空間的基地址*/
int front; /* 頭指針 */
int rear; /* 尾指針，若隊列不空，指向隊列尾元素的下一個位置 */
- 附設兩個整型變量front和rear指針分別指示隊列頭元素及隊列尾元素的位置。
- 初始化創(chuàng)建空隊列時，令front ＝ rear = 0
- 每當插入新的隊列尾元素時，尾指針rear增1，每當刪除隊列頭元素時，頭指針front增1.
- 在非空棧中，頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾元素的下一個位置。
循環(huán)隊列，解決假溢出問題
隊空隊滿的判斷：
- 少用一個元素空間。即隊列空間大小為m時，由m－1個元素就認為是隊滿。
- 當頭、尾指針相等時，隊空。當尾指針在循環(huán)意義上加1后是等于頭指針，則認為隊滿。
隊空條件：Q.front == Q.rear
隊滿條件：(Q.rear+1)%MAXQSIZE == Q.front
2. 循環(huán)隊列的初始化
- 為隊列分配一個最大容量的MAXSIZE的數(shù)組空間，base指向數(shù)組空間的首地址。
- 頭指針和尾指針為零，表示隊列為空。
/* 初始化一個空隊列Q */
Status InitQueue(SqQueue *Q)
{
Q.base = new QElemType[MAXQSIZE]; //為隊列分配一個最大容量為MAXQSIZE的數(shù)組空間
if (!Q.base) exit(OVERFLOW);
Q->front =Q->rear=0;
return OK;
}
3. 求循環(huán)隊列的長度
/* 返回Q的元素個數(shù)，也就是隊列的當前長度 */
int QueueLength(SqQueue Q)
{
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
4. 循環(huán)隊列的入隊
- 判斷隊列是否滿，若滿則返回ERROR。
- 將新元素插入隊尾。
- 隊尾指針加1。
Status EnQueue(SqQueue &Q,QElemType e){
if ((Q.rear+1)%MAXSIZE == Q.front) /* 隊列滿的判斷 */
return ERROR;
Q.base[Q.rear]=e; /* 將元素e賦值給隊尾 */
Q->rear=(Q.rear+1)%MAXSIZE;/* rear指針向后移一位置， */
return OK;
}
5. 循環(huán)隊列的出隊
- 判斷隊列是否為空，若為空則返回ERROR。
- 保存隊列頭元素。
- 對頭指針加1。
Status DeQueue(SqQueue &Q,QElemType &e){
if (Q.front == Q.rear) /* 隊列空的判斷 */
return ERROR;
e=Q.base[Q.front]; /* 將隊頭元素賦值給e */
Q.front=(Q.front+1)%MAXSIZE; /* front指針向后移一位置，若到最后則轉(zhuǎn)到數(shù)組頭部 */
return OK;
}
6. 取循環(huán)隊列的對頭元素
SElemType GetHead(SqQueue Q)
{
if(Q.front != Q.rear)//隊列非空
return Q.base[Q.front];//返回隊頭元素的值，隊頭指針不變。
}
(2) 鏈隊-隊列的鏈式表示和實現(xiàn)
鏈隊采用鏈式存儲結構實現(xiàn)的隊列。為了方便操作，給鏈隊添加一個頭結點，并令頭指針始終指向頭結點。
1. 隊列的鏈式存儲結構
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存儲空間初始分配量 */
typedef int Status;
typedef int QElemType; /* QElemType類型根據(jù)實際情況而定，這里假設為int */
typedef struct QNode /* 結點結構 */
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct /* 隊列的鏈表結構 */
{
QueuePtr front,rear; /* 隊頭、隊尾指針 */
}LinkQueue;
2. 鏈隊的初始化
- 生成一個新結點作為頭結點，對頭和隊尾指針指向此結點。
- 頭結點的指針域置空。
Status InitQueue(LinkQueue &Q)
{
//構造一個空隊
Q.front = Q.rear = new QNode;
Q.front->next = NULL;
return OK;
}
3. 鏈隊的入隊
- 為元素分配新的結點空間，用指針p指向。
- 將新結點數(shù)據(jù)域設置為e。
- 將新結點插入到隊尾。
- 修改隊尾指針為p。
Status EnQueue(LinkQueue &Q,QElemType e)
{
p = new QNode;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear = p
return OK;
}
4. 鏈隊的出隊
- 判斷隊列是否為空，若空則返回ERROR。
- 臨時保存隊列的頭元素，以備釋放空間。
- 修改隊頭指針，指向下一個結點。
- 判斷出隊元素是否為最后一個元素，若是，則將隊尾指針重新賦值，指向隊頭結點。
- 釋放元隊頭元素空間。
Status DeQueue(LinkQueue &Q,QElemType &e)
{
QueuePtr p;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next; //p指向隊頭元素
e=p->data; //e保存隊頭元素的值
Q.front->next=p.next; //修改頭指針
if(Q.rear==p) //最后一個元素被刪，隊尾指針指向隊頭指針
Q.rear=Q.front;
delete p;
return OK;
}
4. 取鏈隊的隊頭元素
SElemType GetHead(LinkQueue Q)
{
if(Q.front != Q.rear)
return Q.front->next->data;
}
(3) 循環(huán)隊列和鏈隊列的比較
- 時間上，基本操作都是常數(shù)時間，即O（1）,不過，循環(huán)隊列是事先申請好空間，使用期間不釋放，而對于鏈隊列，每次申請和釋放結點會存在一些時間開銷，如果入隊出隊頻繁，則兩者還是略有差異。
- 空間上，循環(huán)隊列必須有固定的長度，所以就有了存儲元素個數(shù)和空間浪費的問題。而鏈隊列不存在這樣的問題，盡管它需要一個指針域，會產(chǎn)生一些空間上的開銷，但也可以接受。所以在空間上，鏈隊列更加靈活。
- 總之，在可以確定隊列長度最大值的情況下，建議用循環(huán)隊列，如果無法預估隊列的長度，則用鏈隊列。
插入元素時間復雜度為O（1），刪除時是O（n），因為后面的所有元素要向前移;
