队列的数组实现

  1 /*
  2   队列的数组实现。
  3   为避免出现队列“看似满了”现象，采用循环数组实现。
  4   当Size = 0 或 Rear = Front - 1 ，说明队列为空。
  5   要注意的是，插入的第一个元素的位置是Array[ 1 ]，而不是Array[ 0 ]。
  6 */
  7 
  8 /*接口头文件*/
  9 typedef int ElementType;
 10 #ifndef _QUEUE_H
 11 #define _QUEUE_H
 12 #include <stdbool.h>
 13 
 14 struct Node;
 15 typedef struct Node * PtrToNode;
 16 typedef PtrToNode Queue;
 17 
 18 /*操作集*/
 19 Queue CreateQueue( int MaxElements );
 20 void MakeEmpty( Queue Q );
 21 bool IsEmpty( Queue Q );
 22 bool IsFull( Queue Q );
 23 void Enqueue( ElementType X, Queue Q );
 24 void Dequeue( Queue Q );
 25 ElementType Front( Queue Q );
 26 ElementType FrontAndDequeue( Queue Q );
 27 void DisposeQueue( Queue Q );
 28 void PrintfQueue( Queue Q );
 29 
 30 #endif 
 31 
 32 
 33 /*接口实现*/
 34 #include <stdio.h>
 35 #include <stdlib.h>
 36 #include "queue.h"
 37 
 38 /*获取下个队头或队尾，实现循环数组*/
 39 int Succ( int Value, Queue Q );
 40  
 41 /*指定队列数组的最小空间*/
 42 #define MinQueueSize ( 5 )
 43 
 44 /*特定结构体定义*/
 45 struct Node
 46 {
 47     int Capacity;         //队列数组空间大小
 48     int Size;             //队列元素个数
 49     int Front;            //队头
 50     int Rear;             //队尾
 51     ElementType * Array; 
 52 };
 53 
 54 /*创建队列*/
 55 Queue CreateQueue( int MaxElements )
 56 {
 57     Queue Q;
 58     
 59     if ( MaxElements < MinQueueSize )
 60     {
 61        printf( "Space is smallr!!!
" );
 62        exit( 1 );
 63     }
 64     
 65     Q = ( Queue )malloc( sizeof( struct Node ) );
 66     if ( Q == NULL )
 67     {
 68        printf( "No Space!!!
" );
 69        exit( 1 );
 70     }
 71     
 72     Q->Array = ( ElementType * )malloc( sizeof( ElementType ) * MaxElements );
 73     if ( Q->Array == NULL )
 74     {
 75        printf( "No Space!!!
" );
 76        exit( 1 );
 77     }
 78     
 79     Q->Capacity = MaxElements;
 80     MakeEmpty( Q );
 81     return Q;
 82 }
 83 
 84 /*使队列为空*/
 85 void MakeEmpty( Queue Q )
 86 {
 87     Q->Size = 0;
 88     Q->Front = 1;        //注意，首次插入元素插入Q->Array[ 1 ] 
 89     Q->Rear = 0;
 90 }
 91 
 92 bool IsEmpty( Queue Q )
 93 {
 94     return Q->Size == 0;
 95 }
 96 
 97 bool IsFull( Queue Q )
 98 {
 99     return Q->Size == Q->Capacity;
100 }
101 
102 /*入队操作*/
103 void Enqueue( ElementType X, Queue Q )
104 {
105     if ( IsFull( Q ) )
106     {
107        printf( "Queue is full
" );
108        exit( 1 );
109     }
110     else
111     {
112         Q->Size++;
113         Q->Rear = Succ( Q->Rear, Q );     //获取队尾
114         Q->Array[ Q->Rear ] = X;
115     }   
116 }
117 
118 void Dequeue( Queue Q )
119 {
120     if ( IsEmpty( Q ) )
121     {
122        printf( "Queue is empty
" );
123        exit( 1 );
124     }
125     else
126     {
127         Q->Size--;
128         Q->Front = Succ( Q->Front, Q );
129     }
130 }
131 
132 ElementType Front( Queue Q )
133 {
134     return Q->Array[ Q->Front ];
135 }
136 
137 ElementType FrontAndDequeue( Queue Q )
138 {
139     ElementType n;
140     
141     if ( IsEmpty( Q ) )
142     {
143        printf( "Queue is empty
" );
144        exit( 1 );
145     }
146     else
147     {
148         n = Q->Array[ Q->Front ];
149         Q->Size--;
150         Q->Front = Succ( Q->Front, Q );
151         return n;   
152     }
153 }
154 
155 void DisposeQueue( Queue Q )
156 {
157     free( Q->Array );
158     free( Q );
159 }
160 
161 void PrintfQueue( Queue Q )
162 {
163     while ( ! IsEmpty( Q ) )
164         printf( "%3d", FrontAndDequeue( Q ) );
165         
166     printf( "
" );
167 }
168 
169 int Succ( int Value, Queue Q )
170 {
171     if ( ++Value == Q->Capacity )
172        Value = 0;
173        
174     return Value;
175 }