Data Structure Study Notes <3> Queue

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.

Insert picture description here

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;
}