队列是一种基本的数据结构，可以认为是线性表的变种，但它又有自己的独特之处，本文将结合代码简单介绍两种队列的实现方式。

队列的定义

与栈相反，队列(queue)是一种先进先出(first in first out,缩写为FIFO)的线性表。这和我们日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端叫做队尾(rear)，允许删除的一端叫做队头(front)。

抽象数据类型定义

ADT Queue{
数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=1,2, …,n }
约定a1为队列头，an为队列尾。
}

代码实现

顺序队列(SqQueue)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <stdio.h>
#include <stdlib.h>

#define MAXQSIZE 100 //队列最大长度

#define OK 1
#define ERROR 0

typedef int QElemType;
typedef int Status;

//顺序队列定义
typedef struct
{
    QElemType *base;
    int front;
    int rear;
}SqQueue;

//初始化
Status InitQueue(SqQueue *Q)
{
    Q->base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
    if (!Q->base) return ERROR;
    Q->front = Q->rear = 0;
    return OK;
}

int Length(SqQueue *Q)
{
    return (Q->rear - Q->front + MAXQSIZE) % MAXQSIZE;
}

//队满
Status QueueFull(SqQueue *Q)
{
    if ((Q->rear + 1) % MAXQSIZE == Q->front)
        return OK;
    return ERROR;
}

//队空
Status QueueEmpty(SqQueue *Q)
{
    if (Q->front == Q->rear)
        return OK;
    return ERROR;
}

//入队
Status EnQueue(SqQueue *Q, QElemType e)
{
    if (QueueFull(Q))
        return ERROR;
    Q->base[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXQSIZE;
    return OK;
}

//出队
Status DeQueue(SqQueue *Q, QElemType *e)
{
    if (QueueEmpty(Q))
        return ERROR;
    (*e) = Q->base[Q->front];
    Q->front = (Q->front + 1) % MAXQSIZE;
    return OK;
}

//遍历
Status Traverse(SqQueue *Q)
{
    int i = 0;
    while (i < Length(Q))
    {
        printf("%d ", Q->base[i]);
        i++;
    }
    printf("\n");
    return OK;
}

完整代码可参见：GitHub

queue

链队列(LinkQueue)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0

typedef int QElemType;
typedef int Status;

//节点定义
typedef struct QNode
{
    QElemType data;
    struct QNode *next;
}QNode, *QueuePtr;

//链队列定义
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
    int length;
}LinkQueue;

//初始化
Status InitQueue(LinkQueue *Q)
{
    Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
    if (!Q->front) return ERROR;
    Q->front->next = NULL;
    Q->length = 0;
    return OK;
}

//入队
Status EnQueue(LinkQueue *Q, QElemType e)
{
    QueuePtr p;
    p = (QueuePtr)malloc(sizeof(QNode));
    if (!p) return ERROR;
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    Q->length++;
    return OK;
}

//队空
Status QueueEmpty(LinkQueue *Q)
{
    if (Q->front == Q->rear) return OK;
    return ERROR;
}

//出队
Status DeQueue(LinkQueue *Q, QElemType *e)
{
    QueuePtr p;
    if (QueueEmpty(Q)) return ERROR;
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if (p == Q->rear) Q->front = Q->rear;
    free(p);
    Q->length--;
    return OK;
}

//销毁
Status Destroy(LinkQueue *Q)
{
    while (Q->front)
    {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return OK;
}

//遍历
Status Traverse(LinkQueue *Q)
{
    QueuePtr p;
    p = Q->front->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

LinkQueue

完整代码可参见：GitHub

DONE！

所示代码如有错误请多加指正，谢谢