数据结构-队列

队列的数组实现

在队列的数组结构中，包含一个数组 Queue[] 以及位置 Front 和 Rear 分别作为队列的两端，记录队列中元素个数的 Size。

struct QueueRecord
{
    int Capacity;
    int Front;
    int Rear;
    int Size;
    ElementType *Array;
};

队列的操作:

当一个元素 X 入队，Size++, Rear++, Queue[Rear] = X
当出队操作，返回值为 Queue[Front], Size--, Front++

为了避免 Rear 在数组末端而无法入队操作，队列采用循环数组(circular array)实现。如果 Front 或 Rear 增 1 使得超越了数组，就把值置为数组的第一个位置。入队、出队的操作过程如图所示。

通过循环数组实现队列的代码:

 1 /* Queue.h */
 2 #ifndef _Queue_H
 3 #define _Queue_H
 4 struct QueueRecord;
 5 typedef struct QueueRecord *Queue;
 6 typedef int ElementType;
 7 
 8 int IsEmpty(Queue Q);
 9 int IsFull(Queue Q);
10 Queue CreateQueue(int MaxElements);
11 void DisposeQueue(Queue Q);
12 void MakeEmpty(Queue Q);
13 void Enqueue(ElementType X, Queue Q);
14 ElementType Front(Queue Q);
15 void Dequeue(Queue Q);
16 ElementType FrontAndDequeue(Queue Q);
17 
18 // Queue implementation is a dynamically allocated arry
19 #define MinQueueSize(S)
20 
21 struct QueueRecord
22 {
23     int Capacity;
24     int Front;
25     int Rear;
26     int Size;
27     ElementType *Array;
28 };
29 
30 #endif

 1 /* Queue.cpp */
 2 #include "Queue.h"
 3 #include <stdlib.h>
 4 #include <stdio.h>
 5 
 6 int IsEmpty(Queue Q)
 7 {
 8     return Q->Size == 0;
 9 }
10 
11 int IsFull(Queue Q)
12 {
13     return Q->Capacity == Q->Size;
14 }
15 
16 Queue CreateQueue(int MaxElements)
17 {
18     Queue Q;
19 
20     Q = (struct QueueRecord*)malloc(sizeof(struct QueueRecord));
21     Q->Capacity = MaxElements;
22     Q->Front = 0;
23     Q->Rear = 0;
24     Q->Size = 0;
25 }
26 
27 // 构造空队列
28 void MakeEmpty(Queue Q)
29 {
30     Q->Size = 0;
31     Q->Front = 1;
32     Q->Rear = 0;
33 }
34 
35 static int Succ(int Value, Queue Q)
36 {
37     if(++Value == Q->Capacity)  // 对尾 rear 达到数组尾端, 绕回到开头
38         Value = 0;
39     return Value;
40 }
41 void Enqueue(ElementType X, Queue Q)    // 入队操作
42 {
43     if(IsFull(Q))
44         printf("Full queue");
45     else
46     {
47         Q->Size++;
48         Q->Rear = Succ(Q->Rear, Q);
49         Q->Array[Q->Rear] = X;
50     }
51 }
52 
53 ElementType Front(Queue Q)
54 {
55     return Q->Array[Q->Front];
56 }
57 
58 void Dequeue(Queue Q)
59 {
60     free(Q);
61 }
62 
63 ElementType FrontAndDequeue(Queue Q)
64 {
65     ElementType front;
66     if(IsEmpty(Q))
67         printf("Full queue");
68     else
69     {
70         front = Q->Array[Q->Front];
71         Q->Front = Succ(Q->Front, Q);
72         Q->Size--;
73         return front;
74     }
75 }

参考：