1、佇列：在表的一端插入，表的另一端洗掉，允許插入的一端為隊尾，允許洗掉的一端為隊頭，先進先出FIFO，
2、佇列的基本操作
InitQueue(&Q)：構造空佇列
DestroyQueue(&Q)：銷毀佇列
ClearQueue(&Q)：清空佇列
QueueEmpty(Q)：判斷佇列是否為空
QueueLength(Q)：求佇列長度
GetHead(Q,&e)：用e回傳佇列的隊頭元素
EnQueue(&Q,e)：插入e作為佇列的新隊尾
DeQueue(&Q,&e)：洗掉隊頭元素，并用e回傳
3、佇列的順序存盤：連續的存盤單元，附設兩個指標front指示隊頭元素，rear指示隊尾元素的下一個位置
1）回圈佇列：將順序佇列變成環狀空間，
（1）初始化建空佇列時：front=rear=0
（2）每當插入新的佇列尾元素時，rear=(rear+1)%maxsize
（3）每當洗掉隊頭元素時，front=(front+1)%naxsize
（4）在非空佇列中，頭指標始終指向佇列頭元素，而尾指標始終指向佇列尾元素的下一個位置，
（5）佇列長度：(rear+maxsize-front)%maxsize
2）判別佇列空間是“空”還是“滿”，
（1）設一個標志位tag以區別佇列是“空”還是“滿”，初始tag=0，入隊成功tag=1，出隊成功tag=0，
隊空：因洗掉元素導致rear==front&&tag==0；隊滿：因插入元素導致rear==front&&tag==1
（2）少用一個元素空間，約定以“佇列頭指標在佇列尾指標的下一個位置（指環狀的下一個位置）上”作為佇列“滿”的標志，
隊空：rear==front；隊滿：(rear+1)%maxsize==front；隊中元素的個數：(rear+maxsize-front)%maxsize
（3）設定計數器count，初始count=0，入隊成功count+1，出隊成功count-1，
隊空：count==0；隊滿：count>0&&rear==front
3）佇列的順序存盤型別描述
#define Maxsize 50
typedef struct {
int data[Maxsize];
int front, rear;
int tag = 0;//如果不需要設定標志位可以不宣告，
}SqQueue;
初始狀態（隊空條件）：Q.front==Q.rear==0；進隊操作：隊不滿時，插入隊尾，隊尾指標+1；出隊操作：隊不空時，取隊頭元素的值，頭指標+1，
4）順序存盤時一些基本操作的實作
（1）初始化
void initqueue(SqQueue &Q)
{
Q.rear = Q.front = 0;
}
（2）判斷佇列為空
bool queueempty(SqQueue Q)
{
if (Q.rear == Q.front)
{
return true;
}
else
{
return false;
}
}
（3）入隊
bool enqueue(SqQueue & Q,int e)
{
if ((Q.rear + 1) % Maxsize == Q.front)
{
return false;
}
Q.data[Q.rear] = e;
Q.rear = (Q.rear + 1) % Maxsize;
return true;
}
（4）設有tag標志的回圈佇列入隊
bool enqueue2(SqQueue & Q, int e)
{
if (Q.front == Q.rear&&Q.tag == 1)
{
return false;
}
Q.data[Q.rear] = e;
Q.rear = (Q.rear + 1) % Maxsize;
Q.tag = 1;
return true;
}
（5）出隊
bool dequeue(SqQueue &Q, int &e)
{
if (Q.rear == Q.front)
{
return false;
}
e = Q.data[Q.front];
Q.front = (Q.front + 1) % Maxsize;
return true;
}
（6）設有tag標志的回圈佇列出隊
bool dequeue2(SqQueue &Q, int &e)
{
if (Q.front == Q.rear&&Q.tag == 0)
{
return false;
}
e = Q.data[Q.front];
Q.front = (Q.front + 1) % Maxsize;
Q.tag = 0;
return true;
}
4、雙端佇列：限定插入和洗掉操作在表的兩端進行的線性表，
1）輸出受限的雙端佇列：一個端點允許插入和洗掉，另一個端點只允許插入，
2）輸入受限的雙端佇列：一個端點允許插入和洗掉，另一個端點只允許洗掉，
5、佇列的鏈式存盤
1）鏈佇列：用鏈表表示的佇列，一個含有頭指標（指向隊頭結點）和尾指標（指向隊尾結點）的單鏈表，
2）當鏈佇列有頭結點時，當尾指標和頭指標均指向頭結點，則鏈佇列尾空，
3）佇列的鏈式存盤型別描述
typedef struct {
int data;
struct Linkqueuenode *next;
}Linkqueuenode;
typedef struct {
Linkqueuenode *front, *rear;
}Linkqueue;
//Q.front==null&&Q.rear==null，鏈式佇列為空，
4）鏈式存盤時一些基本操作的實作
（1）初始化
void initqueue(Linkqueue &Q)
{
Q.front = Q.rear = (Linkqueuenode *)malloc(sizeof(Linkqueuenode));
Q.front->next = NULL;
}
（2）判斷佇列是否為空
bool queueempty(Linkqueue Q)
{
if (Q.rear == Q.front)
{
return true;
}
else
{
return false;
}
}
（3）入隊
void enqueue(Linkqueue &Q, int e)
{
Linkqueuenode *s = (Linkqueuenode *)malloc(sizeof(Linkqueuenode));
s->data = https://www.cnblogs.com/xqy1874/p/e;
s->next = NULL;
Q.rear->next = s->next;
Q.rear = s;
}
（4）出隊
bool dequeue(Linkqueue &Q, int &e)
{
if (Q.front == Q.rear)
{
return false;
}
Linkqueuenode *p = Q.front;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)
{
Q.rear = Q.front;
}
free(p);
return true;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/57178.html
標籤：其他
下一篇：資料結構（C語言版）---樹