Article directory
- Chain storage implementation of queue
- 2. Implementation process
-
- 1. Conceptual diagram of chain queue (with head node):
- 2. Chain queue structure:
- 3. Basic operation of the queue
- 4. Code implementation:
Chain storage implementation of queue
Chained queue: A queue implemented in the form of a linked list. The linked list node is the queue data storage area, and the linked list node includes two parts of data storage
area and pointer storage area.
Data storage area: the area where real and valid data is stored.
Pointer storage area: store the address of the next linked list node.
2. Implementation process
1. Conceptual diagram of chain queue (with head node):
2. Chain queue structure:
The head pointer executes the head node, and the tail pointer points to the tail node
//Linear table storage structure
typedef struct LNode
{<!-- -->
ElemType data; //Store the elements in the queue.
struct LNode* next; //next pointer
}LNode;
//The pointer head and tail of the queue
typedef struct
{<!-- -->
LNode *front,*rear; // Head pointer and tail pointer of the queue.
}LinkQueue,*PLinkQueue;
3. Basic operation of the queue
4. Code implementation:
/*
Program name: linkqueue.cpp This program demonstrates the linked list implementation of the queue (leading node).
*/
#include
#include
#include
typedef int ElemType; //The data elements of the custom queue are integers.
//Linear table storage structure
typedef struct LNode
{<!-- -->
ElemType data; //Store the elements in the queue.
struct LNode* next; //next pointer
}LNode;
//The pointer head and tail of the queue
typedef struct
{<!-- -->
LNode *front,*rear; // Head pointer and tail pointer of the queue.
}LinkQueue,*PLinkQueue;
//Initialization operation of queue QQ.
int InitQueue(PLinkQueue QQ);
// Destroy the queue QQ.
void DestroyQueue(PLinkQueue QQ);
// Clear the queue.
void Clear(PLinkQueue QQ);
// Elements are enqueued, return value: 0-failure; 1-success.
int InQueue(PLinkQueue QQ, ElemType *ee);
// Print all elements in the queue.
void PrintQueue(PLinkQueue QQ);
// Find the length of the queue, return value: >=0-the number of QQ elements in the queue.
int Length(PLinkQueue QQ);
// Determine whether the queue is full. There is no such thing as a full queue in a chained queue.
int IsFull(PLinkQueue QQ);
// Determine whether the queue is empty, return value: 1-empty, 0-non-empty or failed.
int IsEmpty(PLinkQueue QQ);
// Elements are dequeued, return value: 0-failure; 1-success.
int OutQueue(PLinkQueue QQ, ElemType *ee);
// Get the element at the head of the queue, return value: 0-failure; 1-success.
// Only check the value of the element at the head of the queue, and the element is not queued.
int GetHead(PLinkQueue QQ, ElemType *ee);
int main()
{
LinkQueue QQ; // Create a queue.
memset( & amp;QQ,0,sizeof(LinkQueue));
InitQueue( & amp;QQ); // Initialize the queue.
ElemType ee; // Create a data element.
printf("Elements (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) are enqueued.\
");
ee=1; InQueue( &QQ, &ee);
ee=2; InQueue( &QQ, &ee);
ee=3; InQueue( &QQ, &ee);
ee=4; InQueue( &QQ, &ee);
ee=5; InQueue( &QQ, &ee);
ee=6; InQueue( &QQ, &ee);
ee=7; InQueue( &QQ, &ee);
ee=8; InQueue( &QQ, &ee);
ee=9; InQueue( &QQ, &ee);
ee=10; InQueue( &QQ, &ee);
printf("The length of the queue is %d\
", Length( & amp;QQ));
printf("Print queue elements:\
");
PrintQueue( &QQ);
if (OutQueue( & amp;QQ, & amp;ee)==1) printf("The value of the element out of the queue is %d\
", ee);
if (OutQueue( & amp;QQ, & amp;ee)==1) printf("The value of the element out of the queue is %d\
", ee);
if (OutQueue( & amp;QQ, & amp;ee)==1) printf("The value of the element out of the queue is %d\
", ee);
if (OutQueue( & amp;QQ, & amp;ee)==1) printf("The value of the element out of the queue is %d\
", ee);
if (OutQueue( & amp;QQ, & amp;ee)==1) printf("The value of the element out of the queue is %d\
", ee);
if (OutQueue( & amp;QQ, & amp;ee)==1) printf("The value of the element out of the queue is %d\
", ee);
if (OutQueue( & amp;QQ, & amp;ee)==1) printf("The value of the element out of the queue is %d\
", ee);
printf("The length of the queue is %d\
", Length( & amp;QQ));
PrintQueue( &QQ);
printf("Elements (11, 12, 13, 14, 15) are enqueued.\
");
ee=11; InQueue( &QQ, &ee);
ee=12; InQueue( &QQ, &ee);
ee=13; InQueue( &QQ, &ee);
ee=14; InQueue( &QQ, &ee);
ee=15; InQueue( &QQ, &ee);
printf("The length of the queue is %d\
", Length( & amp;QQ));
PrintQueue( &QQ);
// Only check the value of the element at the head of the queue, and the element is not queued.
if (GetHead( & amp;QQ, & amp;ee)==1) printf("The element value of the queue head is %d\
",ee);
// printf("clear front=%p, rear=%p\
", QQ.front, QQ.rear);
Clear( & amp;QQ); // Destroy the queue QQ.
// printf("after clearing front=%p, rear=%p\
", QQ.front,QQ.rear);
// printf("front=%p, rear=%p\
", QQ.front, QQ.rear);
DestroyQueue( & amp;QQ); // Destroy the queue QQ.
// printf("after destruction front=%p, rear=%p\
", QQ.front,QQ.rear);
return 0;
}
//Initialization operation of queue QQ.
int InitQueue(PLinkQueue QQ)
{
if(QQ == NULL){ printf("The queue does not exist\
"); return 0; }
//Create head node
LNode* head=(LNode*)malloc(sizeof(LNode));
if(head==NULL){ printf("Insufficient memory, node allocation failed.\
");return 0; }
head->next=NULL;
QQ->front=QQ->rear=head;
return 1;
}
// Destroy the queue QQ. delete all nodes
void DestroyQueue(PLinkQueue QQ)
{
// Queue pointer does not exist
if(QQ==NULL){ printf("The queue does not exist\
"); return ; }
// uninitialized, that is, the head and tail pointers do not point to the head node
if(QQ->front==NULL){
printf("The queue is not initialized.\
");
return;
}
LNode* tmp=QQ->front;
// Delete node by node
while(tmp != QQ->rear->next)
{
tmp=tmp->next; //next node address
free(QQ->front); //Release the address of this node
QQ->front=tmp; //The pointer points to the next node
}
QQ->front=QQ->rear=NULL;
return;
}
// Clear the queue. Removed all nodes except the head node
void Clear(PLinkQueue QQ)
{
// Queue pointer does not exist
if(QQ==NULL){ printf("The queue does not exist\
"); return ; }
// uninitialized, that is, the head and tail pointers do not point to the head node
if(QQ->front==NULL){
printf("The queue is not initialized.\
");
return;
}
LNode *head=QQ->front; //Save the head node
LNode* tmp=QQ->front->next; //Delete from the first node
// Delete node by node
while(tmp != QQ->rear->next)
{
tmp=tmp->next; //next node address
free(QQ->front); //Release the address of this node
QQ->front=tmp; //The pointer points to the next node
}
QQ->front=QQ->rear=head;
QQ->front->next=QQ->rear->next=NULL;
}
// Elements are enqueued, return value: 0-failure; 1-success.
int InQueue(PLinkQueue QQ, ElemType *ee)
{
// Queue pointer does not exist
if(QQ==NULL){ printf("The queue does not exist\
"); return 0; }
//Uninitialized, that is, the head and tail pointers do not point to the head node
if(QQ->front==NULL){
printf("The queue is not initialized.\
");
return 0;
}
//Create a new node
LNode *newnode=(LNode*)malloc(sizeof(LNode));
if(newnode==NULL) return 0;
//Assign the element value to the new node
memcpy( & amp;newnode->data,ee,sizeof(ElemType));
newnode->next=NULL;
QQ->rear->next=newnode;
QQ->rear=newnode;
return 1;
}
// Print all elements in the queue.
void PrintQueue(PLinkQueue QQ)
{
// Queue pointer does not exist
if(QQ==NULL){ printf("The queue does not exist\
"); return ; }
//Uninitialized, that is, the head and tail pointers do not point to the head node
if(QQ->front==NULL){
printf("The queue is not initialized.\
");
return;
}
LNode* tmp=QQ->front->next; //Output from the first node
//When the pointer does not query the next field of the tail pointer, keep querying
while(tmp!=QQ->rear->next){
printf("=",tmp->data);
tmp=tmp->next;
}
printf("\
");
}
// Find the length of the queue, return value: >=0-the number of QQ elements in the queue.
int Length(PLinkQueue QQ)
{
// Queue pointer does not exist
if(QQ==NULL){ printf("The queue does not exist\
"); return 0; }
//Uninitialized, that is, the head and tail pointers do not point to the head node
if(QQ->front==NULL){
printf("The queue is not initialized.\
");
return 0;
}
LNode* tmp=QQ->front->next; //Start counting from the first node
if(tmp==NULL) return 0;
int length=1; //The serial number of the head node is 1
while(tmp!=QQ->rear)
{
length + + ;
tmp=tmp->next;
}
return length;
}
// Determine whether the queue is full. There is no such thing as a full queue in a chained queue.
int IsFull(PLinkQueue QQ)
{
// Queue pointer does not exist
if(QQ==NULL){ printf("The queue does not exist\
"); return 0; }
return 1;
}
// Determine whether the queue is empty, return value: 1-empty, 0-non-empty or failed.
int IsEmpty(PLinkQueue QQ)
{
// Queue pointer does not exist
if(QQ==NULL){ printf("The queue does not exist\
"); return 0; }
// Equal first and last is empty
if(QQ->front==QQ->rear) return 1;
return 0;
}
// Elements are dequeued, return value: 0-failure; 1-success.
int OutQueue(PLinkQueue QQ, ElemType *ee)
{
// Queue pointer does not exist
if(QQ==NULL){ printf("The queue does not exist\
"); return 0; }
if(QQ->front==NULL){printf("The queue is not initialized"); return 0;}
if(IsEmpty(QQ)){ printf("The team is empty, no elements can be dequeued.\
"); return 0; }
//Queue head element out of the queue
LNode* tmp=QQ->front->next;
// end of queue
memcpy(ee, &tmp->data, sizeof(ElemType));
QQ->front->next=tmp->next;
// If the queue is the last node.
if (QQ->rear==tmp) QQ->rear=QQ->front;
free(tmp);
return 1;
}
// Get the element at the head of the queue, return value: 0-failure; 1-success.
// Only check the value of the element at the head of the queue, and the element is not queued.
int GetHead(PLinkQueue QQ, ElemType *ee)
{
if(QQ==NULL){ printf("The queue does not exist\
"); return 0; }
if(QQ->front==NULL){printf("The queue is not initialized"); return 0;}
if(IsEmpty(QQ)){ printf("The team is empty, no elements can be dequeued.\
"); return 0; }
// get the queue head element
memcpy(ee, & amp;QQ->front->next->data,sizeof(ElemType));
return 1;
}