1, Sequential queue

Because the implementation of sequential queue is relatively simple, let's talk about the implementation ideas and some precautions.

Sequential storage structure of queue

The sequential storage structure of queue is called sequential queue. It uses a group of continuous storage units (one-dimensional array) to store each element from the head of the queue to the tail of the queue. Since the positions of the queue head and tail change with the changes of people in the queue and out of the queue, two integer variables front and rear should be set to indicate the positions of the queue head and tail in the array space respectively. Usually, from is called the queue head pointer and rear is the queue tail pointer. Their initial values should be set to 0 during queue initialization and agreed to be in a non empty queue, The team head pointer from always points to the team head element, and the team tail pointer rear always points to the next position of the team tail element.

Generally, in the sequential storage structure, if double pointers are used for operation, the moving (or moving first) generally points to the next position of the last edge element for convenience of operation.

Sequential queue discussion

"Underflow" phenomenon

When the queue is empty, that is, font == rear, the overflow phenomenon caused by the operation of leaving the queue is called underflow.

"True overflow" phenomenon

When rear == MAXQSIZE, the overflow phenomenon caused by the operation of entering and leaving the queue is called true overflow.

"False overflow" phenomenon

False overflow means that the head pointer and tail pointer only increase but not decrease with the operation of queue out and queue in, so that the space of deleted elements cannot be used. Therefore, although the actual number of elements in the queue may be much smaller than the size of the array, the tail pointer may have exceeded the size of the array and cannot be queued, which is called "false overflow"

2, How to solve the problem of "false overflow"

• When the phenomenon of "false overflow" occurs, move all elements to the low end, making the vacancy move from the high-end area to the low-end area. Obviously, this method is a waste of time.
• Connect the one-dimensional array of storage queue elements to form a ring. The queue represented in this form is called circular queue.
• Chain queue is adopted.

3, Circular queue

Circular queue description

When performing out of line and in line operations in the Xunhua queue, the queue head and tail pointers should still be increased by 1. However, when the head and tail pointers point to the upper bound of the array ((MAXSIZE − 1)), the result of the plus 1 operation is to point to the lower bound 0 of the array, and the circular queue will not overflow. It is also agreed that in the non empty loop queue, the queue head pointer always points to the queue head element and the queue tail pointer always points to the next position of the queue tail element. Therefore, the really practical sequential queue is the circular queue.

Implementation method of circular queue

1. Set a flag to distinguish whether the queue is empty or full

Set flag. When Q.font ==Q.rear and flag = 0, the team is empty; when Q.font ==Q.rear and flag = 1, the team is full.

2. Use a counter to record the total number of elements in the queue

Set a variable count to record the number of elements. It is empty when count ==0 and full when count = =MAXQSIZE -1

3. Keep the empty condition and modify the queue full condition (common)

The storage unit with less than one element is used. The unused unit is not sure where it is. It is agreed that "the queue head pointer is at the next position of the queue tail pointer (the next position of the ring)" is used as the sign that the queue is in the "full" state. When there is only one free cell in the array storing the cyclic queue, the cyclic queue is regarded as full. At this time, the difference between the tail pointer and the head pointer is exactly 1. Therefore, the condition of full queue is( Q⋅rear+1)%MAXQSIZE=Q.font.

Definition of storage structure of progressive queue

# define MAXQSIZE 100 / / define the maximum queue capacity (length)
#Define qelemtype int / / define queue element type


typedef struct {
	QElemType base[MAXQSIZE];
	int font, rear;
}SqQueue;

Initialize queue

//Initialize a queue
void init(SqQueue& Q) {
	Q.font = 0;
	Q.rear = 0;
}

Set flag

Queue operation

void push(SqQueue& Q, int val){
	if(flag == 1){
		printf("The queue is full\n");
		return;
	}
	Q.base[Q.rear] = val; //Add to queue
	Q.rear++;
	if(Q.rear == MAXQSIZE)flag =1;
}

Out of line operation

//Out of line operation
int pop(SqQueue& Q) {
	if (!flag) {
		printf("Queue is empty\n");
		return 0;
	}
	int val = Q.base[Q.font];
	Q.font--;
	if(Q.font == Q.rear)flag = 0;
	return val;
}

Set counter method

Queue operation

void push(SqQueue& Q, int val){
	if(count== MAXQSIZE){
		printf("The queue is full\n");
		return;
	}
	Q.base[Q.rear] = val; //Add to queue
	Q.rear++;
	count ++;
}

Out of line operation

//Out of line operation
int pop(SqQueue& Q) {
	if (count == 0) {
		printf("Queue is empty\n");
		return 0;
	}
	int val = Q.base[Q.font];
	Q.font--;
	Q.count --;
	return val;
}

Method 3

Queue operation

// Queued operation
void push(SqQueue& Q, int val) {
	if ((Q.rear + 1) % MAXQSIZE == Q.font) {
		printf("The queue is full\n");
		return;
	}
	Q.base[Q.rear] = val; //Add to queue
	Q.rear = (Q.rear + 1) % MAXQSIZE; //End of line pointer backward
}

Out of line operation

//Out of line operation
int pop(SqQueue& Q) {
	if (Q.font == Q.rear) {
		printf("Queue is empty\n");
		return 0;
	}
	int val = Q.base[Q.font];
	Q.font = (Q.font + 1) % MAXQSIZE;
	return val;
}

Other operations

//Determine whether the queue is empty
int empty(SqQueue& Q) {
	if (Q.font == Q.rear)
		return 1;
	else
		return 0;
}

// Returns the first element of the queue

int font(SqQueue& Q) {
	if (Q.font == Q.rear) {
		printf("Queue is empty\n");
		return 0;
	}
	return Q.base[Q.font];
}

//Returns the last element in the queue
int back(SqQueue& Q) {
	if (Q.font == Q.rear) {
		printf("Queue is empty\n");
		return 0;
	}
	return Q.base[Q.rear];
}

//Returns the number of elements in the queue
int size(SqQueue& Q) {
	return (Q.rear - Q.font + MAXQSIZE) % MAXQSIZE;
}

//Print all elements
void show(SqQueue Q) {
	while (!empty(Q)) {
		printf("%d ", pop(Q));
	}
}

4, Chain queue

explain

The difference between chain queue and chain stack is that chain stack is a single linked list without head node, while chain queue consists of head node. At the beginning, the head pointer and tail pointer point to the head node at the same time.

Unlike double pointers stored sequentially, tail pointers point to the last node.

Linked Storage Structure

#define QElemType int / / element type

typedef struct QNode { //Node structure of queue
	QElemType data;
	QNode* next;
}QNode, * Queueptr;

typedef struct {
	Queueptr font; //Queue head pointer
	Queueptr rear; //Tail pointer
}LinkQueue;

Queue operation

//Queue operation
void push(LinkQueue& Q, QElemType val) {
	//Create a new node
	QNode* node;
	node = (QNode*)malloc(sizeof(QNode));
	if (!node) {
		printf("Failed to allocate memory\n");
		return;
	}
	node->data = val; node->next = NULL; //Form a new node
	Q.rear->next = node;  //The new node is inserted into the tail of the queue. Q.rear is equivalent to obtaining the address of a node
	Q.rear = node; //Tail pointer backward
}

Out of line operation

**Note: * * when there is only one node in the chain queue, if the node is deleted directly, the tail pointer will be lost because the tail pointer points to the node, so the head pointer must be assigned to the tail pointer before deletion.

//Out of line operation
QElemType pop(LinkQueue& Q) {
	if (Q.font == Q.rear) {
		printf("Queue is empty\n");
		return 0;
	}
	QNode* p = Q.font->next;//Remove the team head pointer
	QElemType val = p->data; //Take out the team head data
	Q.font->next = p->next;//Head pointer backward
	if (p == Q.rear)Q.rear = Q.font; //Prevents the tail pointer from being lost when there is only one node
	free(p);//Free up space
	return val;
}

Other operations

//Initialize queue
void init(LinkQueue& Q) {
	Q.font = Q.rear = (QNode*)malloc(sizeof(QNode));
	if (!Q.font) {
		printf("Failed to allocate memory\n");
		return;
	}
	Q.font->next = NULL;
}
//Determine whether the queue is empty
int empty(LinkQueue Q) {
	if (Q.font == Q.rear)
		return 1;
	else
		return 0;
}

//Read header element
QElemType font(LinkQueue& Q) {
	if (Q.font == Q.rear) {
		printf("Queue is empty\n");
		return -1;
	}
	QElemType val = Q.font->next->data;
	/*Can be decomposed into
	* QNode *  p = Q.font->next;
	* QElemType val = p->data;
	*/
	return val;
}

//Read tail element
QElemType back(LinkQueue& Q) {
	if (Q.font == Q.rear) {
		printf("Queue is empty\n");
		return -1;
	}
	QElemType val = Q.rear->data;
	return val;
}

//Destroy queue
void clear(LinkQueue& Q) {//Reference type
	while (Q.font) {
		Q.rear = Q.font->next; //Make the tail pointer point to the first element of the queue
		free(Q.font); //After release, you do not need to set the pointer to null, so it is not easy to have wild pointers
		Q.font = Q.rear; //The first is the head node, followed by the element node
	}
}