隊(duì)列（Queue）只允許在表的一端進(jìn)行插入，表的另一端進(jìn)行刪除操作的線性表尉共。
特點(diǎn)：先進(jìn)先出晨逝。
隊(duì)列的基本操作
InitQueue(&Q)：初始化隊(duì)列，構(gòu)造一個(gè)空隊(duì)列Q捷绒。
QueueEmpty(Q)：判隊(duì)列空瑰排，若隊(duì)列Q為空返回true，否則返回false暖侨。
EnQueue(&Q,x)：入隊(duì)椭住，若隊(duì)列Q未滿，則將x加入使之成為新的隊(duì)尾字逗。
DeQueue(&Q,&x)：出隊(duì)京郑，若隊(duì)列Q非空，則刪除隊(duì)頭元素葫掉，并用x返回些举。
GetHead(Q,&x)：讀隊(duì)頭元素，若隊(duì)列Q非空則用x返回隊(duì)頭元素俭厚。
ClearQueue(&Q)：銷毀隊(duì)列户魏，并釋放隊(duì)列Q占用的內(nèi)存空間。
順序隊(duì)：采用順序存儲(chǔ)的隊(duì)列挪挤。
#define MaxSize 50
typedef struct{
? ? ? ? Element data[MaxSize];
? ? ? ? int front,rear;
}SqQueue;
-front指向隊(duì)頭元素叼丑，rear指向隊(duì)尾元素的下一位置（或front指向隊(duì)頭元素的前一位置，rear指向隊(duì)尾元素）
-初始時(shí)front == rear ==0
判空：Q.front == Q.rear?
隊(duì)長：Q.rear -?Q.front
循環(huán)隊(duì)列：把存儲(chǔ)隊(duì)列的順序隊(duì)列在邏輯上視為一個(gè)環(huán)
取余 （%MaxSize）
front指針移動(dòng)：Q.front = （Q.front + 1）% MaxSize
rear指針移動(dòng)：Q.rear= （Q.rear+ 1）% MaxSize
隊(duì)列長度：（Q.rear + MaxSize - Q.front?）%?MaxSize
方法一：犧牲一個(gè)存儲(chǔ)單元
隊(duì)空條件：Q.front ==?Q.rear
隊(duì)滿條件：Q.front == （Q.rear + 1）% MaxSize
方法二：增加一個(gè)變量代表元素的個(gè)數(shù)
Q.size = 1
隊(duì)空條件：Q.size == 0
隊(duì)滿條件：Q.size == MaxSize
方法三：增加tag標(biāo)識(shí)
隊(duì)空條件：Q.front==Q.size&&tag==0
隊(duì)滿條件：Q.front==Q.size&&tag==1
初始化
void InitQueue(SqQueue &Q){
? ??????Q.front = Q.rare = 0扛门；
}
判隊(duì)空
bool isEmpty(SqQueue Q){
? ? ? ? if(Q.rear == Q.front)
? ? ? ? ? ? ? ? return true;
? ? ? ? else
? ? ? ? ? ? ? ? return false;
}
入隊(duì)
bool EnQueue(SqQueue &Q,ElemType x){
? ? ? ? if((Q.rare+1)%Maxsize == Q.front){
? ? ? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? Q.data[Q.rare]=x;
? ? ? ? Q.rare = (Q.rare+1)%Maxsize;
? ? ? ? return true;
}
出隊(duì)
bool DeQueue(SqQueQue &Q,ElemType &x){
? ??????if(Q.rear == Q.front)
? ? ? ? ? ? ? ? return false;
? ? ? ? x = Q.data[Q.front];
? ? ? ? Q.front = (Q.front + 1)%Maxsize;
? ? ? ? return true;
}
鏈隊(duì)：采用鏈?zhǔn)酱鎯?chǔ)的隊(duì)列
type struct{
? ? ? ? ElemType data;
? ? ? ? struct LinkNode *next;
}LinkNode;
typedef struct{
? ? ? ? LinkNode *front,*rear;
}LinkQueue;
初始化
void InitQueue(LinkQueue &Q){
? ? ? ? Q.front = (LinkNode*)malloc(sizeof(LinkNode));
? ? ? ? Q.rear = Q.front;
? ? ? ? Q.front->next = null;
}
判隊(duì)空
bool isEmpty(LinkQueue?Q){
? ? ? ? if(Q.rear == Q.front)
????????????????return true;
????????else
? ? ? ? ? ? ? ? return false;
}
入隊(duì)
void EnQueue(LinkQueue &Q,ElemType x){
? ? ? ? LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
? ? ? ? s->data = x;
? ? ? ? s->next = null;
? ? ? ? Q.rear->next = s;
? ? ? ? Q.rear = s;
}
出隊(duì)
bool DeQueue(LinkQueue &Q ,ElemType &x){
? ? ? ? if(Q.front == Q.rear)
? ? ? ? ? ? ? ? return false;
? ? ? ? LinkNode *p = Q.front->next;
? ? ? ? x = p->data;
? ? ? ? Q.fornt->next = p->next;
? ? ? ? if(Q.rear == p)
? ? ? ? ? ? ????Q.rear = Q.front;
? ? ? ? free(p);
? ? ? ? return true;
}
輸出序列
出棧序列中每一個(gè)元素后面所有比它小的元素組成一個(gè)遞減序列巾表。
合法出棧序列個(gè)數(shù)：f(n)=C(2n,n)/(n+1)
雙端隊(duì)列允許兩端都可以進(jìn)行入隊(duì)以及出隊(duì)操作的隊(duì)列
