棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。表尾端稱為棧頂屠尊，表頭端稱為棧底。不含元素的空表稱為空棧耕拷。
棧是后進(jìn)先出的線性表讼昆。
隊(duì)列是只允許在一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作的線性表骚烧。隊(duì)列是先進(jìn)先出的線性表浸赫。
1. 棧
(1) 順序棧的表示和實(shí)現(xiàn)
順序棧是指利用順序存儲結(jié)構(gòu)實(shí)現(xiàn)的棧，即利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素赃绊，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置既峡。另設(shè)指針base指示棧底元素在順序棧中的位置。
當(dāng)top和base的值相等時(shí)碧查，表示空棧运敢。
1. 順序棧的存儲結(jié)構(gòu)
#define MAXSIZE 100 /* 存儲空間初始分配量 */
typedef int Status;
typedef int SElemType; /* SElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */
/* 順序棧結(jié)構(gòu) */
typedef struct{
SElemType *base;//棧底指針
SElemType *top;//棧頂指針
int stacksize;//椫沂郏可用的最大容量
}
base指針的值為NULL传惠，則表明棧結(jié)構(gòu)不存在。
棧非空時(shí)稻扬，top始終指向棧頂元素的上一個(gè)位置卦方。
2. 順序棧的初始化
- 為順序棧動態(tài)分配一個(gè)最大容量為MAXSIZE的數(shù)組空間，使base指向這段空間的基地址泰佳，即棧底盼砍。
- 棧頂指針top初始值為base尘吗。
- stacksize置為棧的最大容量MAXSIZE。
Status InitStack(SqStack &S)
{
S.base = new SElemType[MAXSIZE]; //為順序棧動態(tài)分配一個(gè)最大容量為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. 取棧頂元素
當(dāng)棧非空時(shí)，此操作返回當(dāng)前棧頂元素的值隆圆，棧頂保持不變漱挚。
Status GetTop(SqStack S)
{
if (S.top ! = S.base) //棧非空
return *(S.top -1);//返回棧頂元素的值，棧頂指針不變渺氧。
}
(2) 鏈棧的表示和實(shí)現(xiàn)
鏈棧是指采用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)的棧旨涝。
1. 鏈棧的存儲結(jié)構(gòu)
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
2. 鏈棧的初始化
鏈棧的初始化操作就是構(gòu)造一個(gè)空棧，因?yàn)闆]必要設(shè)頭結(jié)點(diǎn)侣背，所以直接將棧頂指針置空即可白华。
Status InitStack(LinkStack &S)
{//構(gòu)建一個(gè)空棧S，棧頂指針置空
S = NULL:
return OK;
}
3. 鏈棧的入棧
- 為棧元素e分配空間贩耐，用指針p指向弧腥。
- 將新結(jié)點(diǎn)數(shù)據(jù)域置為e。
- 將新結(jié)點(diǎn)插入棧頂
- 修改棧頂指針為p潮太。
Status Push(LinkStack &S,SElemType e)
{
p = new StackNode; //生成新結(jié)點(diǎn)
p->data = e;//將新結(jié)點(diǎn)數(shù)據(jù)域置為e
p->next = S;//將新結(jié)點(diǎn)插入棧頂
S = p;//修改棧頂指針為p
return OK;
}
4. 鏈棧的出棧
- 判斷棧是否為空管搪，若空則返回ERROR。
- 將棧頂元素賦值給e消别。
- 臨時(shí)保存棧頂元素的空間抛蚤，以備釋放。
- 修改棧頂指針寻狂，指向新的棧頂元素岁经。
- 釋放元棧頂元素
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塔問題
- 每次只能移動一個(gè)圓盤。
2.圓盤可以插在A塘慕、B和C中的任一塔座上筋夏。 -
任何時(shí)刻都不能將一個(gè)較大的圓盤壓在較小的圓盤之上。
Hanoi塔問題的遞歸算法
- 如果 n＝1,則直接將編號為1的圓盤從A移到C图呢，遞歸結(jié)束条篷。
- 否則：
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免猾，同時(shí)設(shè)置一個(gè)初始值為0的全局變量m,對搬動進(jìn)行計(jì)數(shù)是辕。*/
int m;
void move(char A,int n,char C)
{
count<<++m<<","<<n<<","<<A<<","<<C<<endl;
}
2. 隊(duì)列
(1) 循環(huán)隊(duì)列-隊(duì)列的順序表示和實(shí)現(xiàn)
1. 隊(duì)列的順序存儲結(jié)構(gòu)
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存儲空間初始分配量 */
typedef int Status;
typedef int QElemType; /* QElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */
/* 循環(huán)隊(duì)列的順序存儲結(jié)構(gòu) */
typedef struct{
QElemType *base /*存儲空間的基地址*/
int front; /* 頭指針 */
int rear; /* 尾指針掸刊，若隊(duì)列不空免糕，指向隊(duì)列尾元素的下一個(gè)位置 */
- 附設(shè)兩個(gè)整型變量front和rear指針分別指示隊(duì)列頭元素及隊(duì)列尾元素的位置。
- 初始化創(chuàng)建空隊(duì)列時(shí)忧侧，令front ＝ rear = 0
- 每當(dāng)插入新的隊(duì)列尾元素時(shí)石窑，尾指針rear增1，每當(dāng)刪除隊(duì)列頭元素時(shí)蚓炬，頭指針front增1.
- 在非空棧中松逊，頭指針始終指向隊(duì)列頭元素，而尾指針始終指向隊(duì)列尾元素的下一個(gè)位置肯夏。
循環(huán)隊(duì)列经宏，解決假溢出問題
隊(duì)空隊(duì)滿的判斷：
- 少用一個(gè)元素空間。即隊(duì)列空間大小為m時(shí)驯击，由m－1個(gè)元素就認(rèn)為是隊(duì)滿烁兰。
- 當(dāng)頭、尾指針相等時(shí)徊都，隊(duì)空沪斟。當(dāng)尾指針在循環(huán)意義上加1后是等于頭指針，則認(rèn)為隊(duì)滿暇矫。
隊(duì)空條件：Q.front == Q.rear
隊(duì)滿條件：(Q.rear+1)%MAXQSIZE == Q.front
2. 循環(huán)隊(duì)列的初始化
- 為隊(duì)列分配一個(gè)最大容量的MAXSIZE的數(shù)組空間主之，base指向數(shù)組空間的首地址择吊。
- 頭指針和尾指針為零，表示隊(duì)列為空槽奕。
/* 初始化一個(gè)空隊(duì)列Q */
Status InitQueue(SqQueue *Q)
{
Q.base = new QElemType[MAXQSIZE]; //為隊(duì)列分配一個(gè)最大容量為MAXQSIZE的數(shù)組空間
if (!Q.base) exit(OVERFLOW);
Q->front =Q->rear=0;
return OK;
}
3. 求循環(huán)隊(duì)列的長度
/* 返回Q的元素個(gè)數(shù)几睛，也就是隊(duì)列的當(dāng)前長度 */
int QueueLength(SqQueue Q)
{
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
4. 循環(huán)隊(duì)列的入隊(duì)
- 判斷隊(duì)列是否滿，若滿則返回ERROR粤攒。
- 將新元素插入隊(duì)尾所森。
- 隊(duì)尾指針加1。
Status EnQueue(SqQueue &Q,QElemType e){
if ((Q.rear+1)%MAXSIZE == Q.front) /* 隊(duì)列滿的判斷 */
return ERROR;
Q.base[Q.rear]=e; /* 將元素e賦值給隊(duì)尾 */
Q->rear=(Q.rear+1)%MAXSIZE;/* rear指針向后移一位置夯接， */
return OK;
}
5. 循環(huán)隊(duì)列的出隊(duì)
- 判斷隊(duì)列是否為空必峰，若為空則返回ERROR。
- 保存隊(duì)列頭元素钻蹬。
- 對頭指針加1。
Status DeQueue(SqQueue &Q,QElemType &e){
if (Q.front == Q.rear) /* 隊(duì)列空的判斷 */
return ERROR;
e=Q.base[Q.front]; /* 將隊(duì)頭元素賦值給e */
Q.front=(Q.front+1)%MAXSIZE; /* front指針向后移一位置凭需，若到最后則轉(zhuǎn)到數(shù)組頭部 */
return OK;
}
6. 取循環(huán)隊(duì)列的對頭元素
SElemType GetHead(SqQueue Q)
{
if(Q.front != Q.rear)//隊(duì)列非空
return Q.base[Q.front];//返回隊(duì)頭元素的值问欠，隊(duì)頭指針不變。
}
(2) 鏈隊(duì)-隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)
鏈隊(duì)采用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)的隊(duì)列粒蜈。為了方便操作顺献，給鏈隊(duì)添加一個(gè)頭結(jié)點(diǎn)，并令頭指針始終指向頭結(jié)點(diǎn)枯怖。
1. 隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存儲空間初始分配量 */
typedef int Status;
typedef int QElemType; /* QElemType類型根據(jù)實(shí)際情況而定注整，這里假設(shè)為int */
typedef struct QNode /* 結(jié)點(diǎn)結(jié)構(gòu) */
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct /* 隊(duì)列的鏈表結(jié)構(gòu) */
{
QueuePtr front,rear; /* 隊(duì)頭、隊(duì)尾指針 */
}LinkQueue;
2. 鏈隊(duì)的初始化
- 生成一個(gè)新結(jié)點(diǎn)作為頭結(jié)點(diǎn)度硝，對頭和隊(duì)尾指針指向此結(jié)點(diǎn)肿轨。
- 頭結(jié)點(diǎn)的指針域置空。
Status InitQueue(LinkQueue &Q)
{
//構(gòu)造一個(gè)空隊(duì)
Q.front = Q.rear = new QNode;
Q.front->next = NULL;
return OK;
}
3. 鏈隊(duì)的入隊(duì)
- 為元素分配新的結(jié)點(diǎn)空間蕊程，用指針p指向椒袍。
- 將新結(jié)點(diǎn)數(shù)據(jù)域設(shè)置為e。
- 將新結(jié)點(diǎn)插入到隊(duì)尾藻茂。
- 修改隊(duì)尾指針為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. 鏈隊(duì)的出隊(duì)
- 判斷隊(duì)列是否為空，若空則返回ERROR辨赐。
- 臨時(shí)保存隊(duì)列的頭元素优俘，以備釋放空間。
- 修改隊(duì)頭指針掀序，指向下一個(gè)結(jié)點(diǎn)帆焕。
- 判斷出隊(duì)元素是否為最后一個(gè)元素，若是森枪，則將隊(duì)尾指針重新賦值视搏，指向隊(duì)頭結(jié)點(diǎn)审孽。
- 釋放元隊(duì)頭元素空間。
Status DeQueue(LinkQueue &Q,QElemType &e)
{
QueuePtr p;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next; //p指向隊(duì)頭元素
e=p->data; //e保存隊(duì)頭元素的值
Q.front->next=p.next; //修改頭指針
if(Q.rear==p) //最后一個(gè)元素被刪浑娜，隊(duì)尾指針指向隊(duì)頭指針
Q.rear=Q.front;
delete p;
return OK;
}
4. 取鏈隊(duì)的隊(duì)頭元素
SElemType GetHead(LinkQueue Q)
{
if(Q.front != Q.rear)
return Q.front->next->data;
}
(3) 循環(huán)隊(duì)列和鏈隊(duì)列的比較
- 時(shí)間上佑力，基本操作都是常數(shù)時(shí)間，即O（1）,不過筋遭，循環(huán)隊(duì)列是事先申請好空間打颤，使用期間不釋放，而對于鏈隊(duì)列漓滔，每次申請和釋放結(jié)點(diǎn)會存在一些時(shí)間開銷编饺，如果入隊(duì)出隊(duì)頻繁，則兩者還是略有差異响驴。
- 空間上透且，循環(huán)隊(duì)列必須有固定的長度，所以就有了存儲元素個(gè)數(shù)和空間浪費(fèi)的問題豁鲤。而鏈隊(duì)列不存在這樣的問題秽誊，盡管它需要一個(gè)指針域，會產(chǎn)生一些空間上的開銷琳骡，但也可以接受锅论。所以在空間上，鏈隊(duì)列更加靈活楣号。
- 總之最易，在可以確定隊(duì)列長度最大值的情況下，建議用循環(huán)隊(duì)列炫狱，如果無法預(yù)估隊(duì)列的長度藻懒，則用鏈隊(duì)列。
插入元素時(shí)間復(fù)雜度為O（1）视译，刪除時(shí)是O（n）束析，因?yàn)楹竺娴乃性匾蚯耙?
