1. 隊(duì)列定義

//順序存儲(chǔ)隊(duì)列
typedef struct
{
    elemType data[maxSize];
    int front, rear;        
}queue; 

//鏈表存儲(chǔ)隊(duì)列
typedef struct Node
{
    elemType data;
    Node *next;
};

typedef struct queue
{
    Node *front;
    Node *rear;
};

通過隊(duì)列的定義可以看出，隊(duì)列除了按先后順序都數(shù)據(jù)進(jìn)行存儲(chǔ)外，還需要兩個(gè)指針，分別代表隊(duì)頭和隊(duì)尾。

2. 進(jìn)隊(duì)出隊(duì)操作

出隊(duì)操作將隊(duì)頭指針往后移動(dòng)一位，進(jìn)隊(duì)操作則將隊(duì)尾指針向后移動(dòng)一位

順序存儲(chǔ)隊(duì)列

進(jìn)隊(duì)

bool enterQueue(queue &q, elemType data)
{
    if(q.rear == maxSize)
        return false;
    //隊(duì)尾往后移一位，添加數(shù)據(jù)
    q.rear++;
    q.data[q.rear] = data;
    
    return true;    
}

出隊(duì)

elemType outQueue(queue &q)
{
    //判斷隊(duì)列是否為空
    if(q.front == q.rear)
        return -9999;
    //返回隊(duì)頭元素，隊(duì)頭指針往后移動(dòng)一位 
    return q.data[q.front++];
}

鏈表存儲(chǔ)隊(duì)列

進(jìn)隊(duì)

bool enterQueue(queue &q,elemType e)
{
    Node *p;
    p = (Node *)malloc(sizeof(Node));
    
    p->data = e;
    p->next = NULL;
    
    //隊(duì)列最后一個(gè)元素指針域指向新添加的元素
    q.rear->next = p;
    //隊(duì)尾指針指向新的隊(duì)尾
    q.rear = p;
    
    return true;
}

出隊(duì)

elemType outQueue(queue &q)
{
    //判斷隊(duì)伍是否為空
    if(q.front == q.rear)
        return -999;
    
    elemType e;
    e = q.front->next->data;
    
    //使隊(duì)頭指針指向新的隊(duì)頭
    Node *p = q.front->next;
    q.front->next = p->next;
    //釋放已經(jīng)出隊(duì)的結(jié)點(diǎn)的空間  
    free(p);
    
    return e;
}

3. 特殊隊(duì)列——循環(huán)隊(duì)列與雙端隊(duì)列

此處僅討論循環(huán)隊(duì)列。循環(huán)隊(duì)列是基于順序表，與普通隊(duì)列不同的是

1. 指針移動(dòng)到數(shù)組最后的時(shí)候需要進(jìn)行處理使之指向數(shù)組最前
2. 如何計(jì)算隊(duì)伍長(zhǎng)度
3. 如何判斷隊(duì)列空隊(duì)，滿隊(duì)

問題1

//當(dāng)指針指向最后一個(gè)位置時(shí)，再進(jìn)一位時(shí)候，就會(huì)指向0
front = (front + 1) % maxSize;

問題2

//普通隊(duì)列
length = q.rear - q.front;
//循環(huán)隊(duì)列
length = (q.rear - q.front + maxSize) % maxSize;

與普通隊(duì)列區(qū)別在于，循環(huán)隊(duì)列存在 q.rear < q.front 的情況。

1. 當(dāng) q.rear < q.front 時(shí)，q.rear - q.front就等于隊(duì)列中為空的位置個(gè)數(shù)的相反數(shù)，(q.rear - q.front + maxSize)就等于隊(duì)伍長(zhǎng)度，再%maxSize還是等于長(zhǎng)度本身
2. 當(dāng) q.rear > q.front 時(shí)，(q.rear - q.front + maxSize) % maxSize等于q.rear - q.front 即隊(duì)伍長(zhǎng)度

問題3
一般情況下循環(huán)隊(duì)列空的時(shí)候q.rear = q.front，隊(duì)滿的時(shí)候q.rear = q.front。所以無法區(qū)分隊(duì)空，隊(duì)滿。

1. 添加tag，隊(duì)空為0，隊(duì)滿為1.
2. 添加size屬性，每次 出隊(duì)/進(jìn)隊(duì) 后，修改隊(duì)列長(zhǎng)度
3. rear指向最后一個(gè)元素的后一個(gè)位置，隊(duì)列中空出一個(gè)空位。
   (1) 隊(duì)空的條件仍為：q.front == q.rear
   (2) 隊(duì)滿的條件為：(q.rear + 1) % maxSize == q.front
   此時(shí)隊(duì)滿只存在兩種情況：
   (1) rear == maxSize && front == 0
   (2) rear > front
   都能通過(rear + 1) % maxSize 求得front。