隊列
隊列掘殴，可以說是日常生活中最常見的一種現(xiàn)象碰辅，隊列與平時排隊有著相似的特點。隊列也是一種運算受限制的線性表净嘀，與棧不同的是，其是限制在兩端操作的線性表
定義：
隊列就跟日常排隊有一樣的特點：先進先出侠讯，只允許在隊列的一端插入數(shù)據(jù)元素（入隊）挖藏，只允許在隊列的另一端刪除數(shù)據(jù)元素（出隊），可刪除的一端稱為隊頭厢漩，可插入的一端稱為隊尾膜眠。
隊列的修改總是按照先進先出的原則進行的，也就是說新的元素溜嗜，只能添加在對尾宵膨，每次離開的元素只能從隊頭離開，就和排隊打飯一樣炸宵，不過這個隊不允許中途離隊辟躏，比如隊列中加入元素a1,a2,a3……an，a1就是隊頭元素焙压，an就是隊尾元素,退出隊列的順序也只能是a1,a2……an.
隊列的基本操作
- InitQueue(Q): 構造一個空隊列
- EmptyQueue(Q): 判斷一個隊列是否為空
- LengthQueue(Q): 求隊列的長度
- FrontQueue(Q,e): 獲取隊頭元素
- EnQueue(Q,e): 入隊操作
- DeQueue(Q,e): 出隊操作
和棧同理鸿脓，隊列也可以分為順序隊列和鏈隊列。
順序隊
順序存儲結構的類型定義
#define MAXSIZE 20 //單純的空間大小涯曲，并不能代表隊列中的元素有多少
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int front,rear; //尾指針和頭指針
}SeQueue;
具體操作
#define OK 1
#define ERROR 0
typedef int Status;
//將隊列初始化置為空
Status InitQueue(SeQueue *q)
{
q->front = 0;
q->rear = 0;
return OK;
}
//判斷隊列是否為空
int EmptyQueue(SeQueue *q)
{
if(q->front == q->rear)
return 1;
else
return 0;
}
//獲取隊列長度
int LengthQueue(SeQueue q)
{
return q.rear-q.front; //隊尾指針減去隊頭獲得長度
}
//入隊操作
Status EnQueue(SeQueue *q,ElemType e)
{
if(q->rear == MAXSIZE) //隊滿
{
printf("FULL\n");
return ERROR;
}
q->data[q->rear] = e; //入隊操作
q->rear++; //隊尾指針向后移
return OK;
}
//獲取隊頭元素
Status FrontQueue(SeQueue *q,ElemType *e)
{
if(EmptyQueue(q)) //隊空
{
printf("Empty\n");
return ERROR;
}
*e = q->data[q->front];
return OK;
}
//出隊操作
Status DeQueue(SeQueue *q,ElemType *e)
{
if(EmptyQueue(q))
{
printf("Empty\n");
return ERROR;
}
*e = q->data[q->front]; //出隊操作
q->front++;
return OK;
}
缺點：
由于出隊操作和入隊操作中野哭，頭尾指針只會增加，所以會導致被刪除元素無法被重新利用幻件，所以有一種情況拨黔，當隊列中元素個數(shù)少于最大空間時，但也會因為尾指針超過空間上限而不能做入隊操作绰沥。所以這種隊列還是很弱的篱蝇，但是如果表示成循環(huán)隊列就能克服這種情況了
循環(huán)隊列
（腦補長成一條的隊列被拗成環(huán)的樣子）當隊尾指針移動到空間的上限位置時贺待，因為這是一個環(huán)，所以隊尾指針還可以繼續(xù)移動下去進入到數(shù)組最小下標的位置（用取模來實現(xiàn)）零截，這樣就可以最大限度的利用存儲空間了麸塞。
還有一個要解決的問題就是如何判斷隊滿，有兩種解決方案：
- 因為是環(huán)所以當頭尾指針相等就是隊滿的情況了涧衙，但是一開始的
時候如果頭尾指針相等就是隊空了哪工，所以可以多開設一個一個變量
來記錄隊空還是隊滿 - 還有一個比較簡便的方法就是空出一格來，這樣隊滿和隊空就可
以被區(qū)分了(下面有這種來處理隊滿情況)
循環(huán)隊列的具體操作：
循環(huán)隊列也是用的順序存儲結構弧哎，所以類型定義和順序隊是基本一樣的雁比，而在部分運算操作上就有些不同了。
//隊列長度
int LengthQueue(SeQueue q)
{
int len = (q.rear-q.front+MAXSIZE)%MAXSIZE;
return len;
}
//入隊操作
Status EnQueue(SeQueue *q,ElemType e)
{
if((q->rear+1)%MAXSIZE == q->front)//犧牲多一個空間來判斷隊滿的情況
return ERROR;
q->data[rear] = e; //入隊
q->rear = (q->rear+1)%MAXSIZE; //尾指針加一并保證循環(huán)狀態(tài)
return OK;
}
//出隊操作
Status DeQueue(SeQueue *q,ElemType *e)
{
if((q->rear+1)%MAXSIZE == q->front)
return ERROR;
*e = q->data[q->front]; //出隊
q->front = (q->front+1)%MAXSIZE;//頭指針加一并保證循環(huán)意義
}
鏈隊
顧名思義撤嫩，用鏈表來表示的隊列被稱為鏈隊偎捎。鏈隊的結點結構和單鏈表是一樣的，只不過隊列的插入和刪除操作是分別在隊尾和隊頭進行的序攘。因此除了設置頭指針外還要設置尾指針在指向隊尾茴她，為了方便，這里采用有頭結點的單鏈表來表示隊列
隊列的鏈式存儲結構類型定義
typedef int ElemType; //數(shù)據(jù)類型
typedef struct node
{
ElemType data; //數(shù)據(jù)域
struct node *next; //指針域
}QueueNode;
typedef struct
{
QueueNode *front; //頭指針
QueueNode *rear; //尾指針
}LinkQueue;
鏈隊運算的具體操作
//初始化隊列置為空
Status InitQueue(LinkQueue *q)
{
QueueNode *head;
head = (QueueNode*)malloc(sizeof(QueueNode));//為頭結點開辟存儲空間
if(!head) //空間申請失敗
return ERROR;
head->next = NULL; //頭結點指針域置為空
q->front = head; //頭指針指向頭結點
q->rear = head; //尾指針指向頭結點
return OK
}
//判斷隊列是否為空
Status EmptyQueue(LinkQueue *q)
{
return q->rear == q->front;
}
//獲取隊頭元素
Status FrontQueue(LinkQueue *q.ElemType *e)
{
if(EmptyQueue(q)) //隊列為空
return ERROR;
*e = q->front->data;
return OK;
}
//元素入隊
Status EnQueue(LinkQueue *q,ElemType e)
{
QueueNode *s;
s = (QueueNode*)malloc(sizeof(QueueNode)); //為新結點申請空間
if(!s) //申請空間失敗
return ERROR;
s->data = e; //新結點數(shù)據(jù)域賦值
s->next = NULL; //新結點指針域置為空
q->next->next = s; //新結點插入到隊尾
q->rear = s; //更新尾結點
return OK;
}
//元素出隊
Status DeQueue(LinkQueue *q,ElemType *e)
{
if(EmptyQueue(q)) //隊空
return ERROR;
QueueNode *s;
s = q->front->next; //s指向隊頭元素
q->front->next = s->next; //將s指向的元素移出隊列
if(q->rear = s) //如果移出的元素是最后一個
q->rear = q->front; //隊尾指針指向頭結點
*e = s->data; //用e返回移出的元素值
free(s);
return OK;
}
