[数据结构与算法] : 队列

头文件

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

fatal.h如下

1 #include <stdio.h>
2 #include <stdlib.h>
3 
4 #define Error( Str )        FatalError( Str )
5 #define FatalError( Str )   fprintf( stderr, "%s
", Str ), exit( 1 )

源文件

  1 #include "queue.h"
  2 #include <malloc.h>
  3 #include "fatal.h"
  4 
  5 #define MinQueueSize (5)
  6 
  7 struct QueueRecord
  8 {
  9     int Capacity; // 容量
 10     int Front;    // 队头, 出队--
 11     int Rear;     // 队尾, 进队++
 12     int Size;     // 队列实际长度
 13     ElementType *Array; // 动态数组
 14 };
 15 
 16 int IsEmpty(Queue Q)
 17 {
 18     return Q->Size == 0;
 19 }
 20 
 21 int IsFull(Queue Q)
 22 {
 23     return Q->Size == Q->Capacity;
 24 }
 25 
 26 // 创建队列: 1. 建队列节点, 2. 为队列分配内存
 27 Queue CreateQueue(int MaxElements)
 28 {
 29     if(MaxElements < MinQueueSize)
 30         Error("Queue size is too small!");
 31 
 32     Queue Q = (Queue)malloc( sizeof(struct QueueRecord) );
 33     if(Q == NULL)
 34         FatalError("Out of space!");
 35     Q->Array = (ElementType*)malloc( sizeof(ElementType) * MaxElements );
 36 
 37     if(Q->Array == NULL)
 38         FatalError("Out of space!");
 39     Q->Capacity = MaxElements; // 非常重要
 40     MakeEmpty(Q);
 41 
 42     return Q;
 43 }
 44 
 45 void DisposeQueue(Queue Q)
 46 {
 47     if(Q != NULL)
 48     {
 49         free(Q->Array);
 50         free(Q);
 51     }
 52 }
 53 
 54 // 清空状态, Front = 1, Rear = 0, size = 0
 55 void MakeEmpty(Queue Q)
 56 {
 57     if(Q == NULL)
 58         FatalError("Create queue first!");
 59     Q->Size = 0;
 60     Q->Front = 1;
 61     Q->Rear = 0;
 62 }
 63 
 64 // 进队, 先++下标, 再存放元素
 65 void Enqueue(ElementType X, Queue Q)
 66 {
 67     if( IsFull(Q) )
 68         Error("Queue is full!");
 69     else
 70     {
 71         ++Q->Size;
 72         Q->Rear = (Q->Rear + 1) % Q->Capacity;
 73         Q->Array[Q->Rear] = X;
 74     }
 75 }
 76 
 77 // Front所指即为队首
 78 ElementType Front(Queue Q)
 79 {
 80     if( IsEmpty(Q) )
 81         Error("Queue is empty!");
 82     return Q->Array[Q->Front];
 83 }
 84 
 85 // 出队
 86 void Dequeue(Queue Q)
 87 {
 88     if( IsEmpty(Q) )
 89         Error("Queue is empty!");
 90     --Q->Size;
 91     Q->Front = (Q->Front + 1) % Q->Capacity;
 92 }
 93 
 94 ElementType FrontAndDequeue(Queue Q)
 95 {
 96     if( IsEmpty(Q) )
 97         Error("Queue is empty!");
 98     --Q->Size;
 99     ElementType Element = Q->Array[Q->Front];
100     Q->Front = (Q->Front + 1) % Q->Capacity;
101     return Element;
102 }

测试文件

 1 #include <stdio.h>
 2 #include "queue.h"
 3 
 4 main( )
 5 {
 6     Queue Q;
 7     int i;
 8 
 9     Q = CreateQueue( 12 );
10 
11     for( i = 0; i < 10; i++ )
12         Enqueue( i, Q );
13 
14     while( !IsEmpty( Q ) )
15     {
16         printf( "%d
", Front( Q ) );
17         Dequeue( Q );
18     }
19     for( i = 0; i < 10; i++ )
20         Enqueue( i, Q );
21 
22     while( !IsEmpty( Q ) )
23     {
24         printf( "%d
", FrontAndDequeue( Q ) );
25     }
26 
27     DisposeQueue( Q );
28     return 0;
29 }