队列的数组实现

queue.h

 1         /* 队列的类型声明 */
 2 
 3         typedef int ElementType;
 4 /* START: fig3_57.txt */
 5         #ifndef _Queue_h
 6         #define _Queue_h
 7 
 8         struct QueueRecord;
 9         typedef struct QueueRecord *Queue;
10 
11         int IsEmpty( Queue Q );
12         int IsFull( Queue Q );
13         Queue CreateQueue( int MaxElements );
14         void DisposeQueue( Queue Q );
15         void MakeEmpty( Queue Q );
16         void Enqueue( ElementType X, Queue Q );
17         ElementType Front( Queue Q );
18         void Dequeue( Queue Q );
19         ElementType FrontAndDequeue( Queue Q );
20 
21         #endif  /* _Queue_h */
22 /* END */

queue.c

  1         #include "queue.h"
  2         #include "fatal.h"
  3         #include <stdlib.h>
  4 
  5         #define MinQueueSize ( 5 )
  6 
  7         /*列队结构的定义*/
  8         struct QueueRecord
  9         {
 10             int Capacity;
 11             int Front;
 12             int Rear;
 13             int Size;
 14             ElementType *Array;
 15         };
 16 
 17 /* START: fig3_58.txt */
 18 
 19         /*判断队列是否为空*/
 20         int
 21         IsEmpty( Queue Q )
 22         {
 23             return Q->Size == 0;
 24         }
 25 /* END */
 26         
 27         /*判断队列是否满*/
 28         int
 29         IsFull( Queue Q )
 30         {
 31             return Q->Size == Q->Capacity;
 32         }
 33 
 34         /*创建空队列*/
 35         Queue
 36         CreateQueue( int MaxElements )
 37         {
 38             Queue Q;
 39 
 40 /* 1*/      if( MaxElements < MinQueueSize )
 41 /* 2*/          Error( "Queue size is too small" );
 42 
 43 /* 3*/      Q = malloc( sizeof( struct QueueRecord ) );
 44 /* 4*/      if( Q == NULL )
 45 /* 5*/          FatalError( "Out of space!!!" );
 46 
 47 /* 6*/      Q->Array = malloc( sizeof( ElementType ) * MaxElements );
 48 /* 7*/      if( Q->Array == NULL )
 49 /* 8*/          FatalError( "Out of space!!!" );
 50 /* 9*/      Q->Capacity = MaxElements;
 51 /*10*/      MakeEmpty( Q );
 52 
 53 /*11*/      return Q;
 54         }
 55 
 56 /* START: fig3_59.txt */
 57 
 58         /*初始化队列*/
 59         void
 60         MakeEmpty( Queue Q )
 61         {
 62             Q->Size = 0;
 63             Q->Front = 1;
 64             Q->Rear = 0;
 65         }
 66 /* END */
 67 
 68         /*释放队列内存*/
 69         void
 70         DisposeQueue( Queue Q )
 71         {
 72             if( Q != NULL )
 73             {
 74                 free( Q->Array );
 75                 free( Q );
 76             }
 77         }
 78 
 79 /* START: fig3_60.txt */
 80 
 81         /* 给出Q->Front、Q->Rear自增1后的数组下标值 */
 82         static int
 83         Succ( int Value, Queue Q )
 84         {
 85             if( ++Value == Q->Capacity )
 86                 Value = 0;//上面两行的作用是只要Front和Rear到达数组的尾端，它就又绕到开头，这叫做循环数组实现。
 87             return Value;
 88         }
 89         /*
 90          1：加了static后表示该函数失去了全局可见性，只在该函数所在的文件作用域内可见
 91 
 92          2：当函数声明为static以后,编译器在该目标编译单元内只含有该函数的入口地址,
 93          没有函数名,其它编译单元便不能通过该函数名来调用该函数，这也是对1的解析与说明
 94 
 95          3：所以queue.h头文件中不需要声明
 96          */
 97 
 98 
 99         /* 入队 */
100         void
101         Enqueue( ElementType X, Queue Q )
102         {
103             if( IsFull( Q ) )
104                 Error( "Full queue" );
105             else
106             {
107                 Q->Size++;
108                 Q->Rear = Succ( Q->Rear, Q );
109                 Q->Array[ Q->Rear ] = X;
110             }
111         }
112 /* END */
113 
114 
115         /* 返回队头元素，但不出队 */
116         ElementType
117         Front( Queue Q )
118         {
119             if( !IsEmpty( Q ) )
120                 return Q->Array[ Q->Front ];
121             Error( "Empty queue" );
122             return 0;  /* Return value used to avoid warning */
123         }
124 
125         /* 出队 */
126         void
127         Dequeue( Queue Q )
128         {
129             if( IsEmpty( Q ) )
130                 Error( "Empty queue" );
131             else
132             {
133                 Q->Size--;
134                 Q->Front = Succ( Q->Front, Q );
135             }
136         }
137 
138         /* 返回队头元素，并且出队 */
139         ElementType
140         FrontAndDequeue( Queue Q )
141         {
142             ElementType X = 0;
143 
144             if( IsEmpty( Q ) )
145                 Error( "Empty queue" );
146             else
147             {
148                 Q->Size--;
149                 X = Q->Array[ Q->Front ];
150                 Q->Front = Succ( Q->Front, Q );
151             }
152             return X;
153         }