棧和隊列是兩種重要的數(shù)據(jù)結(jié)構(gòu)减拭，棧和隊列是特殊的線性表蔽豺。
1、棧（stack）是限定僅在表的一端進行插入或刪除操作的線性表拧粪。通常稱插入修陡、刪除的這一端為棧頂（top），另一端為棧底（bottom）可霎。棧操作的特點是先進后出（后進先出）魄鸦。
- 棧（順序棧）的數(shù)據(jù)結(jié)構(gòu)定義：
//棧的順序存儲表示（順序棧）
#define STACK_INIT_SIZE 10 // 存儲空間初始分配量
#define STACK_INCREMENT 2 // 存儲空間分配增量
struct SqStack
{
SElemType *base; // 在棧構(gòu)造之前和銷毀之后，base的值為NULL
SElemType *top; // 棧頂指針
int stacksize; // 當前已分配的存儲空間癣朗，以元素為單位
};
下圖展示了順序棧中的數(shù)據(jù)元素和top指針之間的對應關(guān)系：
top為棧頂指針拾因，其初始值指向棧底，即top=base。每當插入棧頂元素時绢记，元素數(shù)據(jù)儲存在當前top指針所指位置扁达，然后top指針增加1個位置；刪除棧頂元素時蠢熄，返回數(shù)據(jù)等于*--top跪解，即指針top減1。因此签孔，非空棧的top指針始終在棧頂元素的下一個位置上惠遏。
- 棧（順序棧）的基本操作
構(gòu)造一個空棧
void InitStack(SqStack &S)
{
if(!(S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))))
exit(OVERFLOW); // 存儲分配失敗
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}
入棧
// 插入元素e為新的棧頂元素
void Push(SqStack &S,SElemType e)
{
if(S.top-S.base>=S.stacksize) // 棧滿，追加存儲空間
{
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); // 存儲分配失敗
S.top=S.base+S.stacksize;
S.stacksize+=STACK_INCREMENT;
}
*(S.top)++=e;
}
出棧
// 若棧不空骏啰，則刪除S的棧頂元素，用e返回其值抽高，并返回OK判耕；否則返回ERROR
Status Pop(SqStack &S,SElemType &e)
{
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
2、隊列（queue）是限定在一端（隊尾）進行插入翘骂，另一端（隊頭）進行刪除的線性表壁熄。隊列操作的特點是先進先出（后進后出）。
- 鏈隊列 用鏈表表示的隊列簡稱鏈隊列碳竟。其含有指向頭結(jié)點的頭指針和指向尾元素的尾指針草丧。
鏈隊列結(jié)構(gòu)圖如下：
結(jié)構(gòu)定義如下：
// 單鏈隊列－－隊列的鏈式存儲結(jié)構(gòu)
typedef struct QNode
{
QElemType data;
QNode *next;
}*QueuePtr;
struct LinkQueue
{
QueuePtr front,rear; // 隊頭、隊尾指針
};
主要操作算法：
構(gòu)造一個空隊列Q
void InitQueue(LinkQueue &Q)
{
if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))
exit(OVERFLOW);
Q.front->next=NULL;
}
入隊
// 入隊莹桅，插入元素e為Q的新的隊尾元素
void EnQueue(LinkQueue &Q,QElemType e)
{
QueuePtr p;
if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存儲分配失敗
exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
出隊
// 出隊昌执，若隊列不空，刪除Q的隊頭元素诈泼，用e返回其值懂拾，并返回OK，否則返回ERROR
Status DeQueue(LinkQueue &Q,QElemType &e)
{
QueuePtr p;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return OK;
}
- 循環(huán)隊列
在介紹循環(huán)隊列前铐达，先了解下順序隊列岖赋。順序隊列的結(jié)構(gòu)如下圖：
用一組地址連續(xù)的存儲單元依次存放從隊頭到隊尾的元素。Q.front為指向隊頭的序號瓮孙，Q.rear指向隊尾唐断。當初始化隊列時Q.front=Q.rear=整型0。每當插入新的隊尾元素時杭抠，“隊尾指針”（Q.rear）加 1 脸甘；每當從隊頭刪除元素時，“隊頭指針” （Q.front）減 1 祈争。因此在非空隊列中斤程，隊頭元素等于 Q[Q.front]，隊尾元素的下一個位置為 Q.rear 。
假設忿墅，當前隊列存儲最大空間為6扁藕。當隊列處于上圖的（d）狀態(tài)是不能再存儲新的元素，而此時動態(tài)增加存儲空間是不合適的疚脐，因為隊列的實際可用空間并未用滿（之前刪除隊列元素時挪出了新的空間）亿柑。一個巧妙的辦法是將順序隊列想象成一個環(huán)狀的空間。
在隊尾增加新的元素時有Q.rear = (Q.rear+1)%maxsize棍弄。另外為了區(qū)分空隊列和滿隊列的判斷條件（空隊列為Q.front=Q.rear）望薄，我們約定當隊列“頭指針”在“尾指針”下一個位置時，認為隊列已滿呼畸。即當(Q.rear+1)%maxsize等于Q.front時認為隊列已滿（最后一個存儲空間不能存元素）痕支。這樣，有一個存儲節(jié)點是不能存數(shù)據(jù)的蛮原，隊列的最大存儲元素的個數(shù)為 maxsize - 1卧须。
下面是循環(huán)隊列的存儲結(jié)構(gòu)：
// c3-4.h 隊列的順序存儲結(jié)構(gòu)(元素出隊時不移動元素，只改變隊頭元素的位置)
#define QUEUE_INIT_SIZE 10 // 隊列存儲空間的初始分配量
#define QUEUE_INCREMENT 2 // 隊列存儲空間的分配增量
struct SqQueue2
{
QElemType *base; // 初始化的動態(tài)分配存儲空間
int front; // 頭指針儒陨，若隊列不空,指向隊列頭元素
int rear; // 尾指針花嘶，若隊列不空,指向隊列尾元素的下一個位置
int queuesize; // 當前分配的存儲容量(以sizeof(QElemType)為單位)
};
主要操作算法：
構(gòu)造一個空隊列Q
void InitQueue(SqQueue2 &Q)
{
if(!(Q.base=(QElemType *)malloc(QUEUE_INIT_SIZE*sizeof(QElemType)))) // 存儲分配失敗
exit(ERROR);
Q.front=Q.rear=0;
Q.queuesize=QUEUE_INIT_SIZE;
}
入隊
// 插入元素e為Q的新的隊尾元素
void EnQueue(SqQueue2 &Q,QElemType e)
{
int i;
if((Q.rear+1)%Q.queuesize==Q.front)
{ // 隊列滿，增加存儲單元
Q.base=(QElemType *)realloc(Q.base,(Q.queuesize+QUEUE_INCREMENT)*sizeof(QElemType));
if(!Q.base) // 增加單元失敗
exit(ERROR);
if(Q.front>Q.rear) // “頭指針”大于“尾指針”蹦漠，比如front=3 rear=2
{
// 移動高端元素到新的高端
//比如 [102,103,null,4,5,6,7,8,9,10,101,null,null],
//移完后為[102,103,null,null,null,4,5,6,7,8,9,10,101],
for(i=Q.queuesize-1;i>=Q.front;i--)
Q.base[i+QUEUE_INCREMENT]=Q.base[i];
Q.front+=QUEUE_INCREMENT; // 移動隊頭指針
}
Q.queuesize+=QUEUE_INCREMENT; // 增加隊列長度
}
Q.base[Q.rear]=e; // 將e插入隊尾
Q.rear=++Q.rear%Q.queuesize; // 移動隊尾指針
}
出隊
// 若隊列不空椭员，則刪除Q的隊頭元素，用e返回其值笛园，并返回OK隘击；否則返回ERROR
Status DeQueue(SqQueue2 &Q,QElemType &e)
{
if(Q.front==Q.rear) // 隊列空
return ERROR;
e=Q.base[Q.front]; // 用e返回隊頭元素
Q.front=++Q.front%Q.queuesize; // 移動隊頭指針
return OK;
}
- 鏈隊列和循環(huán)隊列對比：循環(huán)隊列適合能預估隊列長度的情況，這種情況時間效率較高研铆。鏈隊列比較靈活闸度，但每次出隊或者入隊都需要釋放或者申請節(jié)點空間，效率較低蚜印。
