## One, Abstract Data Type Description of Queue#

Type name: Queue

Data object set: a finite linear table with 0 or more elements

Operation set: stack Q with length MaxSize ∈ Queue, queue element item ∈ ElementType

1. Generate an empty queue with a length of MaxSize

Queue CreatQueue(int MaxSize);

2. Determine if queue Q is full

bool IsFullQ(Queue Q, int MaxSize);

3. Insert data element item into queue Q

bool AddQ(Queue Q, ElementType item);

4. Determine if queue Q is empty

bool IsEmptyQ(Queue Q);

5. Delete and return the first element of the queue

ElementType DeleteQ(Queue Q);

## Two, Sequential Storage Implementation of Queue#

### 1. Definition#

The sequential storage structure of the queue usually consists of a **one-dimensional array**, a variable front that records the position of the queue head element, and a variable rear that records the position of the queue tail element.

The formed array is moved over and becomes a ring, which is a circular queue.

In order to determine whether the queue is empty or full, the circular queue uses only n-1 array spaces.

The definition code is as follows

```
typedef struct QNode *Queue;
struct QNode {
ElementType Data[MaxSize];//one-dimensional array
int rear;//record the position of the queue tail element
int front;//record the position of the queue head element
int MaxSize;
//In fact, front points to the index before the queue head element
};
```

### 2. Operation#

#### (1) Create a circular queue (CreateQueue)#

```
Queue CreateQueue( int MaxSize ) {
Queue Q = (Queue)malloc(sizeof(struct QNode));
Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
Q->front = Q->rear = 0;
Q->MaxSize = MaxSize;
return Q;
}
```

#### (2) Determine if the queue is full (IsFull)#

```
bool IsFull( Queue PtrQ ) {//The remainder of front and rear+1 is equal when the queue is full
return ((PtrQ->rear+1) % PtrQ->MaxSize == PtrQ->front);
}
```

#### (3) Enqueue (AddQ)#

When enqueuing, you need to determine if the queue is full

```
bool AddQ(Queue PtrQ, ElementType item) {
if ( IsFull(PtrQ) ) {
printf("Queue is full");//The remainder of front and rear+1 is equal when the queue is full
return false;
} else {
PtrQ->rear = (PtrQ->rear+1) % PtrQ->MaxSize;
//Move the rear of the queue to achieve circulation by using the remainder operation
PtrQ->Data[PtrQ->rear] = item;
return true;
}
}
```

#### (4) Determine if the queue is empty (IsEmpty)#

```
bool IsEmpty(Queue PtrQ) {
return ( PtrQ->front == PtrQ->rear );
}
```

#### (5) Dequeue (DeleteQ)#

When dequeuing, determine if the current queue is empty

```
ElementType DeleteQ(Queue PtrQ) {
if(IsEmpty(PtrQ)) {//The queue is empty when rear and front are equal
printf("Queue is empty");
return false;
} else {
PtrQ->front = (PtrQ->front+1) % PtrQ->MaxSize;//Move the front of the queue
return PtrQ->Data[PtrQ->front];
}
}
```

## Three, Linked Storage Implementation of Queue#

### 1. Definition#

The linked storage structure of the queue can also be implemented using a **single linked list**, and the insertion and deletion operations are performed at both ends of the linked list. The queue pointer front should point to the head of the linked list.

```
struct Node {
ElementType Data;
struct Node * Next;
}
struct QNode {//Linked queue structure
struct Node *rear; //Points to the rear node of the queue
struct Node *front; //Points to the head node of the queue
};
typedef struct QNode *Queue;
Queue PtrQ;
```

### 2. Operation#

#### (1) Initialization of linked queue without header node (CreateQueue)#

```
Queue CreateQueue() {
Queue Q;
Q = (Queue)malloc(sizeof(struct QNode));
Q->front = Q->rear = NULL;//Both pointers are empty
return Q;
}
```

#### (2) Enqueue operation of linked queue without header node#

```
bool AddQ(Queue PtrQ, ElementType item) {
struct Node *RearCell = PtrQ->rear;//Pointer to the rear element of the queue
struct Node *Temp = (struct Node *) malloc(sizeof(struct Node));
Tmp->Data = X;
Tmp->Next = NULL;
if ( PtrQ->front == NULL ) {//The queue is empty and the first element is entered
PtrQ->rear = PtrQ->front = Tmp;
} else {
RearCell->Next = Tmp;
PtrQ->rear = Tmp;
}
return true;
}
```

#### (3) Dequeue operation of linked queue without header node#

```
ElementType DeleteQ(Queue PtrQ) {
struct Node * FrontCell;
ElementType FrontElem;//Value of the first element of the queue
if (PtrQ->front == NULL) {//1. First determine if it is empty, it cannot be dequeued if it is empty
printf("Queue is empty");
return ERROR;
}
FrontCell = PtrQ->front;
if(PtrQ->front == PtrQ->rear) //If the queue has only one element, the queue is set to empty after deletion
PtrQ->front = PtrQ->rear = NULL;
else
PtrQ->front = FrontCell->Next;
FrontElem = FrontCell->Data;
free(FrontCell); //Release the space of the deleted node
return FrontElem;
}
```