1, Basic concepts of queue

Note: three elements of data structure - logical structure, data operation and storage structure (physical structure)
Different storage structures lead to different implementations of operations

1. Definition of queue

A linear table is a finite sequence of n (n > = 0) data elements with the same data type, where n is the table length. When n=0, the linear table is an empty table. If L is used to name the linear table, it is generally expressed as

A Stack is a linear table that allows insertion (in Stack) or deletion (out Stack) operations only at one end

A Queue is a linear table that only allows insertion (in the Queue) at one end and deletion (out of the Queue) at the other end

A Queue is a linear table that can only be inserted at one end and deleted at the other end

Features: first in, first out pairs of elements
Main terms:
Queue head, tail, empty queue

2. Basic operation of queue

InitQueue(&Q); Initialize the queue and construct an empty queue Q. (Chuang)

DestoryQueue(&Q); Destroy the queue. Destroy and release queue Q. (PIN)

EnQueue(&Q,x); Join the queue. If queue q is not full, x will be added to make it a new tail. (added)

(delete queue header element) dequeue (& Q, & x); Out of the queue, if queue q is not empty, delete the header element and return it with X. (deleted)

(do not delete header elements) gethead (Q, & x); Read the queue header element. If queue q is not empty, assign the header element to X. (query: most of the queue usage scenarios can only access header elements)

2, Queue operation

1. Sequential implementation of queues

#define MaxSize 10 			// Defines the maximum value of the element in the queue
typedef struct {
	ElemType data[MaxSize];	//Storing queue elements in a static array
	int front,rear;
}SqQuenue;

Sq: sequence -- sequence

Continuous storage space, size MaxSize*sizeof(ElemType)

void testQueue(){
	SqQueue Q;//Declare a queue (sequential storage)
	//... Follow up
}

2. Initialization operation

#include<stdio.h>
#define MaxSize 10 			// Defines the maximum number of elements in the queue 
typedef struct{
	ElemType data[MaxSize];	//Storing queue elements in a static array 
	int front,rear;			//Header pointer and tail pointer 
}SqQueue; 

//Initialize queue
void InitQueue(SqQueue &Q){
	//Initially, the pointer to the head and tail points to Q
	Q.rear = Q.front = 0; 
} 
void testQueue(){
	//Declare a queue (sequential storage)
	SqQueue Q;
	InitQueue(Q);
	//... Follow up 
}
//Determine whether the queue is empty
bool QueueEmpty(SqQueue Q){
	if(Q.rear == Q.front) //Team air condition
		return true;
	else 
		return false;
}

3. Join operation (only join from the end of the queue) (insert)

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int front,rear;
}SqQueue;
//Join the team
bool EnQueue(SqQueue &Q,ElemType x){
	if(The queue is full)
		return false;//When the team is full, an error is reported
	Q.data[Q.rear] = x;//Insert x at the end of the queue
	Q.rear=Q.rear + 1;//End of line pointer backward
	return true;
}

(1) Insert an element

Insert multiple elements

At the end of the queue, rear==MaxSize??? At this time, the queue is not full
Because the front end may be out of the team

When the rear points to the last element

If the front is not at the head node,

The rear will return to the header node and report an error. The newly inserted element will arrive at the header node

(2) Improved version of queue operation

#include<stdio.h>
#define MaxSize 10 			// Defines the maximum number of elements in the queue 
typedef struct{
	ElemType data[MaxSize];	//Storing queue elements in a static array 
	int front,rear;			//Header pointer and tail pointer 
}SqQueue; 

//Join the team
bool EnQueue(SqQueue &Q,ElemType x){
	if(The queue is full)
		return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MaxSize;//If the rear is 9, 1 + 9 = 10, 10 / 10 = 0 = = > the rear will return to the header node 
	return true; 
} 
 

Modulo operation, i.e. remainder operation. Two integers a,b, a% b = = the remainder of a divided by b

{0,1,2,3,..., MaxSize-1} logically turns the storage space into a "ring"

Modular operation maps the integer field of wireless limit to a finite set of integers {0,1,2,3,..., b-1}

4. Circular queue (the storage space is logically changed into a "ring" by modular operation)

(1) Queue operation

Q.data[Q.rear] = x;				//Insert new element at the end of the team
Q.rear = (Q.rear + 1) % MaxSize;//End of line pointer plus 1 to take mold

Condition for queue full: the next position of the tail pointer is the queue head, i.e. (Q.rear+1)%MaxSize==Q.front

Cost: sacrifice a storage unit

//Determine whether the queue is empty
bool QueueEmpty(SqQueue Q){
	if(Q.rear == Q.front)	//Judge team air (air to air conditions) 
		return;
	else
		return false;
} 
//Join the team
bool EnQueue(SqQueue &Q,ElemType x){
	if((Q.rear+1) % MaxSize == Q.front )	//Judge team full 
		return false;						//When the team is full, an error is reported 
	Q.data[Q.rear] = x;						//Insert new element at the end of the team 
	Q.rear=(Q.rear + 1)%MaxSize;			//The end of the queue pointer plus 1 takes the modulus (the storage space is logically changed into a "ring" by modulus operation) 
	return true;
}

(2) Out of team operation (only team head elements can be out of the team)

//Out of line (delete a team header element and return with x)
bool DeQueue(SqQueue &Q,ElemType &x){
	if(Q.rear == Q.front)//Judge team empty
		return false;//If the team is empty, an error is reported
	x=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;//The queue head pointer moves back
	return true;
}

Get the value of the header element and return it with x

bool DeQueue(SqQueue &Q,ElemType &x){
	if(Q.rear == Q.front)//Judge team empty
		return false;//If the team is empty, an error is reported
	x=Q.data[Q.front];
	return true;
}

(3) Scheme 1: judge whether the queue is full / empty

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int front,rear;//Initialize real = front = 0
}SqQueue;

Number of queue elements
(rear+MaxSize-front)%MaxSize;

In the current case on the left above
(2+10-3)%10 = 9 % 10 = 9

(4) Scheme 2: judge whether the queue is full / empty (do not waste that storage space)

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int front,rear;//Initialize real = front = 0
	int size;//Current length of the queue (insert successfully, size + +, delete successfully, size --) (during initialization, real = front = 0, size = 0)
}SqQueue;

Insert element

Delete element

(5) Scheme 3: judge whether the queue is full / empty (do not waste that storage space)

#define MaxSize 10
typedef struct{
	ElemType data[MaxSize];
	int front,rear;//Initialize real = front = 0
	int tag;//The most recent is delete / insert
}SqQueue;

Each time the delete operation succeeds, make tag=0
Each time the insert operation succeeds, make tag=1

Only by deleting can the queue be empty
Only the insertion operation can cause the queue to be full

(6) Other methods

Determine whether the queue is empty
(Q.rear+1)%MaxSize == Q.front

Determine whether the queue is full
Scheme 1: sacrifice a storage unit
Scheme 2: add auxiliary variables
Insert picture description here

(7) Knowledge review and important test sites

5. Chain implementation of queue

(1) Knowledge overview

(2) Chain of queues

#include<stdio.h>
typedef struct LinkNode{		//Chain queue node 
	ElemType data;
	struct LinkNode *next;
}LinkNode; 

typedef struct {			//Chain queue 
	LinkNode *front,*rear;	//Header and footer pointers to the queue 
}LinkQueue;

Chain queue – a queue implemented by chain storage

(3) Initialization (lead node)

#include<stdio.h>
typedef struct LinkNode{		//Chain queue node 
	ElemType data;
	struct LinkNode *next;
}LinkNode;
typedef struct {			//Chain queue 
	LinkNode *front,*rear;	//Header and footer pointers to the queue 
}LinkQueue;
//Initialize queue (lead node)
void InitQueue(LinkQueue &Q){
	//The initialization front rear points to the head node
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));//And allocate memory space 
	Q.front->next = NULL;//The pointer to the header node points to null 
}
//Determine whether the queue is empty
bool IsEmpty(LinkQueue &Q){
	if(Q.front == Q.rear)
		return true;
	else
		return false;
}
void testLinkQueue(){
	LinkQueue Q;//Declare a queue 
	InitQueue(Q);//initialization
	//... Follow up 
}

(4) Initialization (no node)

//Initialize the queue (do not take the lead node)
void InitQueue(LinkQueue &Q){
	//Initially, both front and rear point to NULL
	Q.front = NULL;
	Q.rear = NULL; 
} 
//Judge whether the queue is empty (no leader node)
bool IsEmpty(LinkQueue Q){
	if(Q.front == NULL)
		return true;
	else 
		return false;
}

rear–>NULL
front–>NULL

Empty queue without leading node

(5) Join the team (lead node)

//Join the team (lead node)
//New elements join the team (lead node)
void EnQueue(LinkQueue &Q,ElemType x){
	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));//Allocate memory space for linked list 
	s->data = x;
	s->next = NULL;
	Q.rear->next = s;		//After the new node is inserted into the rear 
	Q.rear = s;				//Modify footer pointer 
}

(6) Join the team (do not take the lead)

//New elements join the team (do not take the lead)
void EnQueue(LinkQueue &Q,ElemType x){
	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	if(Q.front == NULL){	//Insert the first element in an empty queue 
		Q.front = s;		//Modify the end of line pointer 
		Q.front = s;		//The queue without the leading node needs special processing when the first element enters the queue 
		Q.rear = s;
	}else{
		Q.rear->next = s;//The new node is inserted after the rear node
		Q.rear=s;		//Modify the real pointer 
	}
} 

(7) Out of line (lead node)

//Queue head element out of the queue (no leading node)
bool DeQueue(LinkQueue &Q,ElemType &x){
	if(Q.front == Q.rear)
		return false;//Team air
	LinkNode *p = Q.front->next;
	x=p->data;//Returns the queue header element with the variable x
	Q.front->next = p->next;//Modify the next pointer of the header node
	if(Q.rear == p)			//This is the last node out of the team 
		Q.rear = Q.front;	//Modify the real pointer 
	free(p);			//Free node space 
	return true; 
} 

(8) Out of line (not leading node)

//Queue head element out of the queue (no leading node)
bool DeQueue(LinkQueue &Q,ElemType &x) {//The incoming parameter is the address value of the queue and the element to be dequeued
	if(Q.front == NULL)//Judge whether the first address value of the incoming queue is empty. If it is empty, it will directly return false
		return false;	//Air force 
	LinkNode *p = Q.front;//p points to the head node of the stack, and the pointer declaring the queue type points to the head position of the queue
	x=p->data;			//Returns the queue header element with the variable x
	Q.front = p->next; //Modify the front pointer
	if(Q.rear == p){		//Modify the front pointer 
		Q.front = NULL;	//front points to NULL 
		Q.rear = NULL;//Real points to NULL 
	} 
	free(p);	//Free node space 
	return true;
}

(9) Queue full condition

3, Double ended queue

1. A double ended queue is a linear table that is inserted at both ends and deleted at both ends

If you only use the insert and delete operation at one end, the effect is equivalent to the stack.

2. Double ended queue with limited input: linear tables that are only allowed to be inserted from one end and deleted from both ends

3. Double ended queue with limited output: linear tables that are only allowed to be inserted from both ends and deleted from one end

4. Test point: judge the legitimacy of output sequences: if the input sequences of data elements are 1,2,3,4, those output sequences are legal and those are illegal?

(1) Stack

The following red is an illegal output sequence

(2) Input restricted Dual Ended queue

(3) Output constrained Dual Ended queue

6. Review of knowledge points