對頭出，隊尾入。
基本操作

InitQueue(*Q)
QueueEmpty(Q)
EnQueue(*Q,x)
DeQueue(*Q,*x)
GetHead(Q, *x)

順序?qū)崿F(xiàn)

#define MaxSize 50
typedef struct
{
    ElemType data[MaxSize];
    int front, rear;
}* SqQueue;

初始時Q->front=Q->rear=0
空隊時Q->front==Q->rear
其余時候front指向隊頭，rear指向隊尾的后一個位置
但會出現(xiàn)，數(shù)組前面由于出隊空了很多位置，但rear==MaxSize無法繼續(xù)入隊的假溢出現(xiàn)象。
循環(huán)隊列
初始時：Q->front=Q->rear=0
隊首出隊時加一：Q->front=(Q->front+1)%MaxSize
隊尾入隊時加一：Q->rear=(Q->rear+1)%MaxSize
隊列長度：(Q->rear+MaxSize-Q->front)%MaxSize
由于隊空和隊滿時都有Q->front==Q->rear無法判斷
解決辦法
1.入隊時少用一個隊列單元
隊滿：(Q->rear+1)%MaxSize==Q->front
隊空：Q->front==Q->rear
2.增設(shè)表示元素個數(shù)的數(shù)據(jù)成員
3.增設(shè)tag，代表上次操作，若tag為0，由于出隊導(dǎo)致front==rear則隊空，為1，則是由入隊導(dǎo)致的，則隊滿

隊列.PNG

void InitQueue(SqQueue Q)
{
    Q->rear=Q->front=0;
}

判空

bool isEmpty(SqQueue Q)
{
    if(Q->rear==Q->front)    return true;
    else    return false;
}

入隊

bool EnQueue(SqQueue Q, ElemType x)
{
    if((Q->rear+1)%MaxSize==Q->front) return false;
    Q->data[Q->rear]=x;
    Q->rear=(Q->rear+1)%MaxSize;
    return true;
}

出隊
bool DeQueue(SqQueue Q, ElemType* x)
{
if(Q->rear==Q->front) return false;
*x=Q->data[Q->front];
Q->front=(Q->front+1)%MaxSize;
return true;
}

鏈?zhǔn)酱鎯Y(jié)構(gòu)

同時帶有隊頭指針和隊尾指針的單鏈表

typedef struct
{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct
{
    LinkNode *front, *rear;
}LinkQueue;

為使其空隊時插入刪除操作統(tǒng)一，一般將其設(shè)計成帶頭節(jié)點的單鏈表

帶頭節(jié)點單鏈表實現(xiàn)的隊列.PNG

初始化

void InitQueue(LinkQueue* Q)
{
    Q->front=Q->rear=（LinkNode*)malloc(size of(LinkNode));
    Q->front->next=NULL；
}

判空

bool IsEmpty(LinkQueue* Q)
{
    if(Q->front==Q->rear)    return true;
    return false;
}

入隊

void EnQueue(LinkQueue* Q, ElemType x)
{
    LinkNode* s=(LinkNode*)malloc(size of(LinkNode));
    s->data=x;
    s->next=NULL;
    Q->rear->next=s;
    Q->rear=s;
}

出隊

bool DeQueue(LinkQueue* Q, ElemType* x)
{
    if(Q->front==Q->rear)    return false;
    LinkNode* first=Q->front->next;
    *x=first->data;
    Q->front=first->next;
    if(Q->rear==first)            //原隊列只有一個節(jié)點，刪除后變空
        Q->rear=Q->next;
    free(first);
    return true;
}

雙端隊列

兩端都可以進(jìn)行入隊和出隊操作
輸出受限的雙端隊列：出隊在某一段進(jìn)行
輸入受限的雙端隊列

隊列應(yīng)用

二叉樹層次遍歷
使用隊列來保存下一步的處理順序
1.根節(jié)點入隊
2.若隊列為空則遍歷完畢，否則重復(fù)3
3.隊首出隊，并訪問之，將其左孩子和右孩子依次入隊，返回2
計算機(jī)系統(tǒng)中的應(yīng)用
1.解決主機(jī)與外部設(shè)備之間速度不匹配的問題（打印數(shù)據(jù)緩沖區(qū)）
2.解決由多用戶引起的資源競爭問題（CPU的分配）

特殊矩陣的壓縮存儲

將矩陣更有效地存儲在內(nèi)存中，并能方便地提取矩陣中的元素
壓縮矩陣：為多個值相同的元素只分配一個存儲空間，對零元素不分配存儲空間。
特殊矩陣：具有許多相同矩陣元素或零元素，且分布有一定規(guī)律性。（對稱矩陣，上下三角矩陣，對角矩陣）
找出特殊矩陣中值相同的矩陣元素的分布規(guī)律，把那些呈現(xiàn)規(guī)律性分布的，值相同的多個矩陣元素壓縮存儲到一個存儲空間中。
關(guān)鍵在于找A和B的下標(biāo)轉(zhuǎn)換
1.對稱矩陣
A[1...n][1...n]->B[n(n+1)/2]
2.三角矩陣
A[1...n][1...n]->B[n(n+1)/2+1]
那個1是用來存三角區(qū)域的常數(shù)的
3.對角矩陣
4.稀疏矩陣
將非零元素及其相應(yīng)的行和列構(gòu)成一個三元組（行標(biāo)，列標(biāo)，值），失去了隨機(jī)存取特性。