当前位置:网站首页>Implementation of queue
Implementation of queue
2022-07-06 18:05:00 【qzt__ l0ve】
Catalog
1. The concept and structure of queue
// Get the number of valid elements in the queue
1. The concept and structure of queue
queue : Data insertion is only allowed at one end , A special linear table that deletes data at the other end , Queue has first in first out
FIFO(First In First Out) Queue entry : The end of the insertion is called the end of the queue
Outgoing queue : The end of the delete operation is called the queue head
2. Implementation of queues
Queues can also be implemented in the structure of arrays and linked lists , It is better to use the structure of linked list , Because if you use the structure of an array , Out of the queue, out of the data on the array header , It will be less efficient .
typedef int QDataType;
// The chain structure : Represents a queue
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
// The structure of the queue
typedef struct Queue
{
QNode* _front;
QNode* _rear;
}Queue;
// Initialize queue
void QueueInit(Queue* q);
// Tail in queue
void QueuePush(Queue* q, QDataType data);
// Team leader out of line
void QueuePop(Queue* q);
// Get queue header elements
QDataType QueueFront(Queue* q);
// Get queue tail element
QDataType QueueBack(Queue* q);
// Get the number of valid elements in the queue
int QueueSize(Queue* q);
// Check if the queue is empty , If NULL, return non-zero result , If not null, return 0
int QueueEmpty(Queue* q);
// Destroy queue
void QueueDestroy(Queue* q);
Initialize queue
void QueueInit(Queue* q);// No matter what structure , We all need to initialize first .
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
}
Tail in queue
void QueuePush(Queue* q, QDataType data);// Because the queue is FIFO , So it can only be inserted from the tail
void QueuePush(Queue* pq, QDataType x)// Insert , Insert... At the end of the line ; fifo
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));// Every time you insert a data, you open up a space
if (newnode == NULL)// Judge whether the development fails
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)// When no data is inserted for the first time
{
pq->head = pq->tail = newnode;
}
else// With data
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
// Team leader out of line
void QueuePop(Queue* q);// Outgoing queue , The first one is the data of the team leader , Make sure it's first in, first out .
void QueuePop(Queue* pq)// It is equivalent to deleting the team header data
{
assert(pq);
assert(!QueueEmpty(pq));// Determines if the queue is empty
// A node
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
// Multiple nodes
else
{
Queue* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
// Get queue header elements
QDataType QueueFront(Queue* q);// First judge the capacity of the queue , Then return to the team head element
QDataType QueueFront(Queue* pq)// Get the correct header data
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
// Get queue tail element
QDataType QueueBack(Queue* q);// First judge the queue capacity , Then return the tail data
QDataType QueueBack(Queue* pq)// Take the tail data
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
// Get the number of valid elements in the queue
int QueueSize(Queue* q);// Create a current pointer , Go back one by one ,size Count the quantity for size .
int QueueSize(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;// Create a pointer to the current element
int size = 0;// Used to count the number of elements
while (cur)
{
++size;
cur = cur->next;
}
return size;
}
// Check if the queue is empty , If NULL, return non-zero result , If not null, return 0
int QueueEmpty(Queue* q);// here return It's to judge first pq->head Is it equal to empty , Return to true later , Return false before waiting .
bool QueueEmpty(Queue* pq)// Judge capacity ;
{
assert(pq);
return pq->head == NULL;
}
// Destroy queue
void QueueDestroy(Queue* q); Because we have opened up space , So we have to release one by one in the end .
void Queuestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)// Release space one by one
{
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
Expand :
In practice, we sometimes use a queue called circular queue . For example, when the operating system course explains the producer consumer model, you can use the circular queue . Ring queues can be implemented using arrays , You can also use a circular linked list to achieve .
边栏推荐
- TCP packet sticking problem
- [Android] kotlin code writing standardization document
- 分布式不来点网关都说不过去
- declval(指导函数返回值范例)
- Will openeuler last long
- Is it meaningful for 8-bit MCU to run RTOS?
- It doesn't make sense without a distributed gateway
- Flet教程之 13 ListView最常用的滚动控件 基础入门(教程含源码)
- Pourquoi Li shufu a - t - il construit son téléphone portable?
- Take you through ancient Rome, the meta universe bus is coming # Invisible Cities
猜你喜欢
The easycvr authorization expiration page cannot be logged in. How to solve it?
基本磁盘与动态磁盘 RAID磁盘冗余阵列区分
STM32按键状态机2——状态简化与增加长按功能
Optimization of middle alignment of loading style of device player in easycvr electronic map
编译原理——自上而下分析与递归下降分析构造(笔记)
Olivetin can safely run shell commands on Web pages (Part 1)
10 advanced concepts that must be understood in learning SQL
微信为什么使用 SQLite 保存聊天记录?
Summary of Android interview questions of Dachang in 2022 (I) (including answers)
队列的实现
随机推荐
微信小程序中给event对象传递数据
In terms of byte measurement with an annual salary of 30W, automated testing can be learned in this way
Will openeuler last long
Release of the sample chapter of "uncover the secrets of asp.net core 6 framework" [200 pages /5 chapters]
How to output special symbols in shell
Jerry's access to additional information on the dial [article]
Codeforces Round #803 (Div. 2)
Shell input a string of numbers to determine whether it is a mobile phone number
declval(指导函数返回值范例)
带你穿越古罗马,元宇宙巴士来啦 #Invisible Cities
Spark accumulator and broadcast variables and beginners of sparksql
Smart street lamp based on stm32+ Huawei cloud IOT design
历史上的今天:Google 之母出生;同一天诞生的两位图灵奖先驱
Cool Lehman has a variety of AI digital human images to create a vr virtual exhibition hall with a sense of technology
30 分钟看懂 PCA 主成分分析
Heavy! Ant open source trusted privacy computing framework "argot", flexible assembly of mainstream technologies, developer friendly layered design
HMS core machine learning service creates a new "sound" state of simultaneous interpreting translation, and AI makes international exchanges smoother
Manifest of SAP ui5 framework json
Dichotomy (integer dichotomy, real dichotomy)
scratch疫情隔离和核酸检测模拟 电子学会图形化编程scratch等级考试三级真题和答案解析2022年6月