数组实现循环队列——C语言_c语言数组首尾循环

学习笔记之数组实现循环队列——C语言
数组实现循环队列的逻辑性比指针实现循环链表更强，然而面试多用数组来实现各个数据结构，需要把握好这类知识。
本次代码使用了数据域和尺寸来实现的。
判断循环队列空还是满都直接用到了Q->Size与0和Q->Capacity比较，更易看懂与接受。若不用数据域和指针，分为三种情况判断，具体如下。
1.可以让front指向队列的第一个元素，rear指向队列的最后一个元素的下一个位置；
2.也可以让front指向第一个位置的前一个位置，rear指向最后一个位置；
3.也可以让front指向第一个位置，rear指向最后一个位置
使用前两种方法可以使用front == rear - 1确定队列是否为空，第三种可以使用rear = front 来确定队列为空。
使用前两种方法可以使用front == rear确定队列是否为满，第三种可以使用rear = front - 1来确定队列为满。
使用第一种方法等于把从Q->Array[1]开始存入数据，使用第二、三种方法等于从Q->Array[0]开始存入数据。
本次代码使用第一种方法。

#include<stdio.h>
#include<stdlib.h>
#define Error( Str ) fprintf( stderr, "%s\n" , Str ),exit( 1 )
#define MinQueueSize 5

typedef int ElementType;

typedef struct Queue{
    int Capacity;
    int front;
    int rear;
    int Size;
    ElementType *Array;
}*Queue;
//判断是否为空
int IsEmpty(Queue Q)
{
    return Q->Size == 0;
}
//判断队列是否满
int IsFull(Queue Q)
{
    if(Q->front != 0)
        return Q->front == Q->rear;
    else
        return Q->Capacity == Q->Size;
}
//使队列为空
Queue MakeEmpty(Queue Q)
{
    Q->front = 0;
    Q->rear = 1;
    Q->Size = 0;
    return Q;
}
//创造一个队列
Queue CreatQueue(ElementType QueueSize)
{
    Queue Q;

    if(QueueSize <= MinQueueSize)
        Error("Size too small");

    Q = malloc(sizeof(struct Queue));
    if(Q == NULL)
        Error("Out of space!");

    Q->Array = malloc(sizeof(ElementType) * QueueSize);
    if(Q->Array == NULL)
        Error("Out of space!!");

    Q->Capacity = QueueSize;
    MakeEmpty(Q);

    return Q;
}
//入队
Queue EnQueue(Queue Q)
{
    int Size;
    ElementType X;
    printf("请输入你要输入的队列的大小:");
    scanf("%d",&Size);
    if(IsFull(Q)||Size + Q->Size > Q->Capacity)
        Error("Full Queue!");

    Q->Size = Q->Size + Size;
    for(;--Size != -1;)
    {
        printf("请输入你要输入的数据:");
        scanf("%d",&X);
        if(Q->rear == Q->Capacity)
            Q->rear = 0;
        Q->Array[Q->rear++] = X;
    }
    return Q;
}
//出队
Queue DeQueue(Queue Q)
{
    if(IsEmpty(Q))
        Error("Empty Queue");
    if(++Q->front == Q->Capacity){
        Q->front = 0;
    }
    Q->Size--;
    return Q;
}
//不改变队列的情况输出队列
void printf_Queue(Queue Q)
{
    int Size = Q->Size;
    int Front = Q->front + 1;
    for(;--Size != -1;){
        if(Front == Q->Capacity)
           Front = 0;
        printf("%d ",Q->Array[Front++]);
    }
}
//销毁队列
void DisposeQueue(Queue Q)
{
    if(Q != NULL){
        free(Q->Array);
        free(Q);
    }
}

int main()
{
    Queue Q;
    Q = CreatQueue(8);

    Q = EnQueue(Q);
    printf("队列为:");
    printf_Queue(Q);

    printf("\n");

    Q = DeQueue(Q);
    Q = DeQueue(Q);
    Q = DeQueue(Q);
    Q = DeQueue(Q);
    Q = DeQueue(Q);
    printf("五个数据出列后结果:");
    printf_Queue(Q);

    printf("\n");

    Q = EnQueue(Q);
    printf("队列为:");
    printf_Queue(Q);

    printf("\n");

    Q = DeQueue(Q);
    Q = DeQueue(Q);
    Q = DeQueue(Q);
    Q = DeQueue(Q);
    Q = DeQueue(Q);

    printf("五个数据出列后结果:");
    printf_Queue(Q);

    printf("\n");

    DisposeQueue(Q);
}

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149