当前位置：首页 > news >正文

队列的数组实现

news 来源：原创 2024/5/12 6:13:02

声明 curosr_queue.h:

 1 #ifndef CURSOR_QUEUE_H_INCLUDED
 2 #define CURSOR_QUEUE_H_INCLUDED
 3 struct QueueRecord;
 4 typedef struct QueueRecord *Queue;
 5 
 6 int IsEmpty(Queue Q);
 7 int IsFull(Queue Q);
 8 Queue CreateQueue(int MaxElements);
 9 void DisposeQueue(Queue Q);
10 void MakeEmpty(Queue Q);
11 void Enqueue(int X, Queue Q);
12 int Front(Queue Q);
13 int Dequeue(Queue Q);
14 int FrontAndDequeue(Queue Q);
15 
16 #endif // CURSOR_QUEUE_H_INCLUDED

实现 implementation.c:

 1 #include<stdio.h>
 2 #include "cursor_queue.h"
 3 
 4 #define MinQueueSize 5
 5 
 6 struct QueueRecord{
 7     int Capacity;
 8     int Front;
 9     int Rear;
10     int Size;
11     int *Array;
12 };
13 
14 int IsEmpty(Queue Q){
15     return Q->Size == 0;
16 }
17 
18 Queue CreateQueue(int MaxElements) {
19     Queue Q;
20     if(MaxElements < MinQueueSize)
21         printf("Too small queue size!");
22     Q = malloc(sizeof(struct QueueRecord));
23     if(Q == NULL) {
24         printf("Out of space!");
25     }
26     Q->Array = malloc(sizeof(int) * MaxElements);
27     if(Q->Array == NULL){
28         printf("Out of space!");
29     }
30     MakeEmpty(Q);
31     Q->Capacity = MaxElements;
32     return Q;
33 }
34 
35 void MakeEmpty(Queue Q) {
36     Q->Rear = 0;
37     Q->Front = 1;
38     Q->Size = 0;
39 }
40 
41 static int Succ(int Value, Queue Q) {
42     if(++Value == Q->Capacity)
43         Value = 0;
44     return Value;
45 }
46 
47 int IsFull(Queue Q) {
48     return Q->Size == Q->Capacity;
49 }
50 
51 void Enqueue(int X, Queue Q) {
52     if(IsFull(Q))
53         printf("Error! Full Queue!\n");
54     else{
55         Q->Size++;
56         Q->Rear = Succ(Q->Rear, Q);
57         Q->Array[Q->Rear] = X;
58     }
59 }
60 
61 int Dequeue(Queue Q){
62     int Data;
63     if(IsEmpty(Q)){
64         printf("Error, empty queue!");
65         return -1;
66     }
67     else{
68         Q->Size--;
69         Data = Q->Array[Q->Front];
70         Q->Front = Succ(Q->Front, Q);
71     }
72     return Data;
73 }
74 
75 void DisposeQueue(Queue Q) {
76     free(Q->Array);
77     free(Q);
78 }

测试 main.c:

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include "cursor_queue.h"
 4 
 5 int main()
 6 {
 7     Queue Q;
 8     Q = CreateQueue(10);
 9     int i = 0;
10     for(i = 0; i < 10; i++)
11         Enqueue(i ,Q);
12     Enqueue(10, Q);
13     for(i = 0; i < 10; i++)
14         printf("%d ", Dequeue(Q));
15     printf("\n");
16     DisposeQueue(Q);
17     Q = CreateQueue(10);
18     for(i = 0; i < 10; i++)
19         printf("%d\n", Dequeue(Q));
20     return 0;
21 }