隊(duì)列的抽象數(shù)據(jù)類型描述：

• 類型名稱：隊(duì)列（Queue）
• 數(shù)據(jù)對(duì)象集： 一個(gè)用 0 個(gè)或多個(gè)元素的又窮線性表。
• 操作集：長(zhǎng)度為 max_size 的隊(duì)列 Q ∈ Queue，隊(duì)列元素 item ∈ ElementType。

1. Queue creat_queue(int max_size): 生成長(zhǎng)度為 max_size 的空隊(duì)列；
2. int is_full_q(queue q, int max_size): 判斷隊(duì)列 Q 是否已滿；
3. void add_q(queue q, element_type item): 將元素 item 插入隊(duì)列 Q 中；
4. int is_empty(queue q): 判斷隊(duì)列 Q 是否為空；
5. element_type delete_q(queue q)：將隊(duì)列元素從隊(duì)列中刪除并返回。

隊(duì)列的順序存儲(chǔ)實(shí)現(xiàn)：

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)通常由一個(gè)一維數(shù)組和一個(gè)記錄隊(duì)列頭元素位置的變量 front 以及一個(gè)記錄隊(duì)列尾元素位置的變量 rear 組成。

純C語(yǔ)言實(shí)現(xiàn)：

// 隊(duì)列(Queue)
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 10
#define elem_type int
#define Position int
#define bool int
#define True 1
#define Flase 0
#define ERROR -1    // 錯(cuò)誤標(biāo)識(shí)

typedef struct {
    elem_type data[MAXSIZE];
    Position front; // 出隊(duì)
    Position rear;  // 入隊(duì)
    int len;
} Queue;

// 初始化
Queue* create_queue(void)
{
    Queue* Q = (Queue*)malloc(sizeof(Queue));
    Q->front = 0;
    Q->rear = -1;
    Q->len = 0;
    
    return Q;
}

// 隊(duì)列是否已滿
bool is_full(Queue* Q)
{
    bool n = Flase;
    if (Q->len == MAXSIZE){
        n = True;
    }
    
    return n;
}

// 入隊(duì)
bool add_q(Queue* Q, elem_type x)
{
    bool n = Flase;

    if (is_full(Q) == 0){
                // 用取余實(shí)現(xiàn)循環(huán)隊(duì)列
        Q->rear = (Q->rear + 1) % MAXSIZE;
        Q->data[Q->rear] = x;
        Q->len++;
        n = True;
    }
    
    return n;
}

// 隊(duì)列是否為空
bool is_empty(Queue* Q)
{
    bool n = Flase;
    if (Q->len == 0){
        n = True;
    }
    
    return n;
}

// 出隊(duì)
elem_type delete_q(Queue* Q)
{
    Position idx;
    if (is_empty(Q) == 0){
        idx = Q->front;
        Q->front = (Q->front + 1) % MAXSIZE;    // 更新出隊(duì)指針
        Q->len--;
        
        return Q->data[idx];
    } else {
        return ERROR;
    }
}

// 輸出隊(duì)列元素
void print(Queue* Q)
{
    int i;
    int n;
    for (i=0; i<Q->len; i++){
        n = (Q->front + i) % MAXSIZE;
        printf("%d\t", Q->data[n]);
    }
    printf("\n");
}

int main(void)
{
    Queue* Q = NULL;
    Q = create_queue();
    // 才創(chuàng)建的隊(duì)列應(yīng)為空
    if (is_empty(Q)){
        printf("隊(duì)列為空\(chéng)n");
    }
    int i = 0;
    // 入隊(duì) 0 1 2 3 4
    while (i<5){
        add_q(Q, i++);
    }
    // 出隊(duì) 0
    delete_q(Q);
    // 輸出 1 2 3 4
    print(Q);
    printf("Q->front = %d\tQ->rear = %d\tQ->len = %d", Q->front, Q->rear, Q->len);
    
    return 0;
}

IMG_20170629_225417.jpg