#202112101836 could be implemented using Array. Since Array is being used, the program need to declare three vairables: Front, Rear and Size to keep track of the queue’s information.
Analysis
- It is important to check if the Queue is empty
- Omit Size could be tricky since there could be some special cases
- If number of Enqueues will not larger than the Size of the queue, the wraparound is not necessary
- As in 202112031221, error testing on Dequeuing on empty queue should be implemented
Implementation
#ifndef _Queue_h
struct QueueRecord;
typedef struct QueueRecord *Queue;
int IsEmpty(Queue Q);
int IsFull(Queue Q);
Queue CreateQueue(int MaxElements);
void DisposeQueue(Queue Q);
void MakeEmpty(Queue Q);
void Enqueue(ElementType X, Queue Q);
ElementType Front(Queue Q);
void Dequeue(Queue Q);
ElementType FrontAndDequeue(Queue Q);
#endif // _Queue_h
struct QueueRecord {
int Capacity;
int Front;
int Rear;
int Size;
ElementType *Array;
};
int IsEmpty(Queue Q) {
return Q->Size == 0;
}
void MakeEmpty(Queue Q) {
Q->Size = 0;
Q->Front = 1;
Q->Rear = 0;
}
int IsFull(Queue Q) {
return Q->Size == Q->Capacity;
}
Queue CreateQueue(int MaxElements) {
Queue Q;
Q = malloc(sizeof(struct QueueRecord));
if (Q == NULL)
FatalError("Out of space!!!");
Q->Array = malloc(sizeof(ElementType) * MaxElements)
if (Q->Array == NULL)
FatalError("Out of space!!!");
Q->Capacity = MaxElements;
MakeEmpty(Q);
return Q;
}
void DisposeQueue(Queue Q) {
if (Q != NULL) {
free(Q->Array);
free(Q);
}
}
static int Succ(int Value, Queue Q)
{
if (++Value == Q->Capacity)
Value = 0;
return Value;
}
void Enqueue(ElementType X, Queue Q) {
if (IsFull(Q))
Error("Full queue");
else {
Q->Size++;
Q->Rear = Succ(Q->Rear, Q);
Q->Array[Q->Rear] = X;
}
}
ElementType Front(Queue Q) {
if (!IsEmpty(Q))
return Q->Array[Q->Front];
Error("Empty queue");
return 0;
}
static int Predec(int Value, Queue Q) {
if (--Value == -1)
return --(Q->Capacity);
return Value;
}
void Dequeue(Queue Q) {
if(IsEmpty(Q))
Error("Empty queue");
else {
Q->Size--;
Q->Front = Predec(Q->Front, Q);
}
}
ElementType FrontAndDequeue(Queue Q) {
if(!IsEmpty(Q)) {
Q->Size--;
PrevFront = Q->Front
Q->Front = Predec(Q->Front, Q);
return Q->Array[PrevFront];
}
Error("Empty queue");
return 0;
}