Chain representation and implementation of queues

Similar to a linear table , Queues can also have two storage representations

The queue represented by the linked list is called the chain queue for short , A chain queue obviously needs two pointers indicating the head and tail of the queue respectively （ They are called head pointer and tail pointer respectively ） The only way to be sure .

The operation of chain queue is the special case of inserting and deleting single chain list , Just need to modify the tail pointer or head pointer

In general , When deleting the queue header element, you only need to modify the pointer in the header node , But when the last element in the queue is deleted , The pointer at the end of the queue is also lost , Therefore, the tail pointer needs to be re assigned （ Point to the head node ）

One ： Initialization operation

Initialize queue , Construct an empty queue

typedef struct LinkNode{ // Chain queue node
 ElemType data;
 struct LinkNode *next;
}LinkNode;

typedef struct{ // Chain queues
 LinkNode *front, *rear // The head and tail pointers of the queue
}LinkQueue;

// Initialize queue ( Leading node )
void InitQueue(LinkQueue &Q){
 // initialization  front、rear All point to the head node
 Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
 Q.front -> next = NULL;
}

viod testLinkQueue(){
 LinkQueue Q; // Declare a queue
 InitQueue(Q); // Initialize queue
}

// Determines if the queue is empty
bool IsEmpty(LinkQueue Q){
 if(Q.front == Q.rear){
 return true;
 }else{
 return false;
 }
}


Joining operation ：

typedef struct LinkNode{ // Chain queue node
 ElemType data;
 struct LinkNode *next;
}LinkNode;

typedef struct{ // Chain queues
 LinkNode *front, *rear // The head and tail pointers of the queue
}LinkQueue;

// New elements in the team ( Leading node )
void EnQueue(LinkQueue &Q, ElemType x){
 LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
 s->data = x;
 s->next = NULL;
 Q.rear->next = s; // Insert new node into rear after
 Q.rear = s; // Modify the tail pointer
}


Out of line operation

typedef struct LinkNode{ // Chain queue node
 ElemType data;
 struct LinkNode *next;
}LinkNode;

typedef struct{ // Chain queues
 LinkNode *front, *rear // The head and tail pointers of the queue
}LinkQueue;

// Team head element out of team operation ( Leading node )
bool DEQueue(LinkQueue &Q, ElemType &x){
 if(Q.front == Q.rear){
 return // Empty queue
 }
 LinkNode *p = Q.front->next;
 x = p->data; // With variable x Return to team leader element
 Q.front->nexy = p->nexy; // Modify the header node next The pointer
 if(Q.rear == p){ // This is the last node out of the team
 Q.rear = Q.front // modify rear The pointer
 }
 free(p); // Release node space
 return true;
}