Array Implementation of Queue

#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;
}
Links to this page
  • Queue

    Queue is a kind of data structure that insertions done at one end, deletions done at the other end. It is FIFO by design which is in contrast with 202112031157. It could be implemented in array#.

#data-structure #queue