catalogue
Concept and structure of queue
Gets the number of valid elements in the queue
Check whether the queue is empty
Implement all the code of the queue
Concept and structure of queue
Queue: a special linear table that only allows inserting data at one end and deleting data at the other end. The queue has a first in first out FIFO(First In First Out).
Enter queue: the end of the queue at which the insertion operation is performed is called the end of the queue.
Out of queue: the end for deletion is called the queue head.
Implementation of queue
There are two ways to implement queue: 1. Using array and 2. Using linked list.
Array queue
Disadvantages: when the element is out of the queue, it needs to move the subsequent data to the front, which is inefficient.
Chain queue
Save two pointers to the head and tail of the team in the queue. When leaving the team, just point the pointer to the head of the team to the next of the original head, and enter directly behind the tail of the team when entering the team
Therefore, using the structure of linked list will be better.
Implementation of chain queue
First create the structure of a single element in the queue, and then create a queue structure, including two pointers to the head and tail.
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;The interfaces to be implemented are given below:
//Initialize queue void QueueInit(Queue* pq); //Queue void QueuePush(Queue* pq, QDataType x); //Out of queue void QueuePop(Queue* pq); //Get queue header element QDataType QueueFront(Queue* pq); //Get queue tail element QDataType QueueBack(Queue* pq); //Gets the number of valid elements in the queue int QueueSize(Queue* pq); //Check whether the queue is empty. If it is empty, it returns a non-zero result. If it is not empty, it returns 0 bool QueueEmpty(Queue* pq); //Destroy queue void QueueDestroy(Queue* pq);
Initialize queue
The queue initialization only needs to point to null two pointers pointing to the head and tail.
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}Queue
First, apply for space to create the element. If there is no element in the queue, take the element as the head and tail of the queue; If there is an element in the queue, connect the element directly to the end of the queue and point the end pointer of the queue to the element.
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newNode->data = x;
newNode->next = NULL;
if (pq->tail == NULL)
{
pq->head = pq->tail = newNode;
}
else
{
pq->tail->next = newNode;
pq->tail = newNode;
}
}Out of queue
When leaving the queue, first check whether there are elements in the queue. If there are no elements in the queue, let the program directly report an error.
Elements can be divided into one or more elements:
One element: directly release the node and point to null the head and tail pointers in the original queue.
Multiple elements: first save the header pointer to the next node of the node, then release the header node and point the header pointer to the original saved value.
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head);//If the queue is empty, no element can be out of the queue and an error is reported directly
//1. One element
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
//2. Multiple elements
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}Get queue header element
When obtaining elements, first check whether there are elements in the queue. If there are no elements, an error will be reported directly. If there are elements, the data with the header pointer pointing to the node will be returned.
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}Get queue tail element
Similar to getting the team header element.
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}Gets the number of valid elements in the queue
Start from the head of the queue to traverse the whole queue and count. During traversal, a new variable should be created for traversal to ensure that the head pointer is not changed.
int QueueSize(Queue* pq)
{
assert(pq);
int size = 0;
QNode* cur = pq->head;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}Check whether the queue is empty
Returns a non-zero result if it is empty and 0 if it is not empty
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}Destroy queue
Each element in the queue is a newly opened node, so it needs to be destroyed one by one. After all nodes are destroyed, point the head and tail pointers to null.
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}Implement all the code of the queue
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
}Queue;
//Initialize queue
void QueueInit(Queue* pq);
//Team tail in
void QueuePush(Queue* pq, QDataType x);
//Team leader
void QueuePop(Queue* pq);
//Get queue header element
QDataType QueueFront(Queue* pq);
//Get queue tail element
QDataType QueueBack(Queue* pq);
//Gets the number of valid elements in the queue
int QueueSize(Queue* pq);
//Check whether the queue is empty. If it is empty, it returns a non-zero result. If it is not empty, it returns 0
bool QueueEmpty(Queue* pq);
//Destroy queue
void QueueDestroy(Queue* pq);
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newNode->data = x;
newNode->next = NULL;
if (pq->tail == NULL)
{
pq->head = pq->tail = newNode;
}
else
{
pq->tail->next = newNode;
pq->tail = newNode;
}
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(pq->head);
//1. One
//2. Multiple
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
int size = 0;
QNode* cur = pq->head;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->head == NULL;
}
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}test case
void TestQueue()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
printf("%d ", QueueBack(&q));
QueuePop(&q);
printf("%d ", QueueFront(&q));
QueuePop(&q);
printf("%d ", QueueFront(&q));
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
printf("QueueSize:%d\n", QueueSize(&q));
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
QueueDestroy(&q);
}
int main()
{
TestQueue();
return 0;
}