东莞手机微信网站,html个人主页源码,网页建站如何保存分享,wordpress缓存文件在目录
0.前言
1.队列的基本概念
2.队列的实现
2.1实现方式
2.2具体实现
3.队列的应用场景
4.一道队列的算法题#xff08;LeetCode225. 用队列实现栈#xff09;
5.结语 #xff08;图像由AI生成#xff09;
0.前言
在计算机科学领域#xff0c;数据结构是组织和…目录
0.前言
1.队列的基本概念
2.队列的实现
2.1实现方式
2.2具体实现
3.队列的应用场景
4.一道队列的算法题LeetCode225. 用队列实现栈
5.结语 图像由AI生成
0.前言
在计算机科学领域数据结构是组织和存储数据的一种方式它允许我们以有效的方式对数据进行访问和修改。今天我们将探讨一种基础但极其重要的数据结构——队列。通过学习我们不仅会了解队列的理论基础还会深入其实现方式探讨其应用场景并通过解决一个实际问题来巩固我们的理解。
1.队列的基本概念
队列是一种基础但非常重要的线性数据结构它在计算机科学和编程中有着广泛的应用。队列遵循先进先出FIFO, First-In-First-Out的原则这意味着最先被加入队列的元素将是最先被移除的。这种特性使得队列非常适合于那些需要按照顺序处理元素的场景。
基本操作
队列的操作通常包括
入队Push在队列的末尾添加一个新的元素。出队Pop移除队列前端的元素。查看队首Peek/Front获取队列前端的元素但不移除它。检查队列是否为空IsEmpty判断队列中是否有元素。获取队列大小Size获取队列中元素的数量。
特性
有序性队列保持元素的添加顺序确保第一个加入的元素将是第一个被移除。动态性队列可以动态地增长和缩减随着元素的入队和出队操作。操作限制在队列中只能在一端队尾添加元素在另一端队首移除元素。
2.队列的实现
2.1实现方式
队列可以通过不同的方式实现其中最常见的两种是
数组实现使用数组存储队列中的元素。这种实现方式简单直观但可能需要处理数组的动态扩容问题或者实现循环队列来优化空间利用。链表实现使用链表存储队列中的元素。链表实现的队列可以动态地增长不需要担心空间限制但每次操作可能涉及更多的内存分配和释放。
综合以上因素以及队列只需要“尾插”和“头删”的特性我们最终决定用带头单向不循环链表来实现队列。
2.2具体实现
在这一部分我们将详细介绍如何使用不带头单向不循环链表来实现队列。这种实现方式利用了链表的动态分配特性允许队列在运行时根据需要增长或缩减。下面是具体的实现方法
队列的结构定义
首先我们定义了两个结构体queueNode 和 queue。queueNode 结构体表示队列中的节点包含数据域 _data 和指向下一个节点的指针 _next。queue 结构体则表示队列本身包含指向队列头部和尾部的指针 _head 和 _tail。
typedef struct queueNode
{QDataType _data; // 节点存储的数据struct queueNode* _next; // 指向下一个节点的指针
} queueNode;typedef struct queue
{queueNode* _head; // 指向队列头部的指针queueNode* _tail; // 指向队列尾部的指针
} queue;初始化队列
queueInit 函数用于初始化队列设置 _head 和 _tail 指针都为 NULL表示一个空队列。
void queueInit(queue* pq)
{assert(pq);pq-_head pq-_tail NULL;
}销毁队列
queueDestroy 函数用于销毁队列释放所有节点占用的内存并将 _head 和 _tail 指针重置为 NULL。
void queueDestroy(queue* pq)
{queueNode* cur pq-_head;while (cur){queueNode* next cur-_next;free(cur);cur next;}pq-_head pq-_tail NULL;
}入队操作
queuePush 函数用于在队列尾部添加新节点。如果队列为空新节点即成为队列的头部和尾部否则将新节点链接到原尾节点的 _next 指针并更新 _tail 指针。
void queuePush(queue* pq, QDataType x)
{assert(pq);queueNode* newNode (queueNode*)malloc(sizeof(queueNode));if (newNode NULL){printf(malloc fail\n);exit(-1);}newNode-_data x;newNode-_next NULL;if (pq-_head NULL){pq-_head pq-_tail newNode;}else{pq-_tail-_next newNode;pq-_tail newNode;}
}出队操作
queuePop 函数用于移除队列头部的节点。如果队列在移除节点后变为空需要同时将 _tail 指针置为 NULL。
void queuePop(queue* pq)
{assert(pq pq-_head);queueNode* next pq-_head-_next;free(pq-_head);pq-_head next;if (pq-_head NULL){pq-_tail NULL;}
}另外我们提供了一些基础的队列操作函数如 queueFront 和 queueBack 分别返回队列的头部和尾部元素queueEmpty 检查队列是否为空queueSize 返回队列中元素的数量。完整代码如下
//queue.h
#pragma once
#ifndef QUEUE_H
#define QUEUE_H
#includestdio.h
#includestdlib.h
#includeassert.h
typedef int QDataType;
typedef struct queueNode
{QDataType _data;struct queueNode* _next;
}queueNode;typedef struct queue
{queueNode* _head;queueNode* _tail;
}queue;void queueInit(queue* pq);
void queueDestroy(queue* pq);
void queuePush(queue* pq, QDataType x);
void queuePop(queue* pq);
QDataType queueFront(queue* pq);//返回队头元素
QDataType queueBack(queue* pq);//返回队尾元素
int queueEmpty(queue* pq);//判断队列是否为空,为空返回1否则返回0
int queueSize(queue* pq);//返回队列中元素的个数#endif // !QUEUE_H
//queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#includequeue.h
void queueInit(queue* pq)
{assert(pq);pq-_head pq-_tail NULL;
}void queueDestroy(queue* pq)
{queueNode* cur pq-_head;while (cur){queueNode* next cur-_next;free(cur);cur next;}pq-_head pq-_tail NULL;
}void queuePush(queue* pq, QDataType x)
{assert(pq);queueNode* newNode (queueNode*)malloc(sizeof(queueNode));if (newNode NULL){printf(malloc fail\n);exit(-1);}newNode-_data x;newNode-_next NULL;if (pq-_head NULL){pq-_head pq-_tail newNode;}else{pq-_tail-_next newNode;pq-_tail newNode;}
}void queuePop(queue* pq)
{assert(pq pq-_head);queueNode*next pq-_head-_next;free(pq-_head);pq-_head next;if(pq-_headNULL){pq-_tail NULL;}
}QDataType queueFront(queue* pq)
{assert(pq pq-_head);return pq-_head-_data;
}QDataType queueBack(queue* pq)
{assert(pq pq-_tail);return pq-_tail-_data;
}int queueEmpty(queue* pq)
{assert(pq);return pq-_head NULL ? 1 : 0;
}int queueSize(queue* pq)
{assert(pq);queueNode* cur pq-_head;int count 0;while (cur){count;cur cur-_next;}return count;
}
3.队列的应用场景
队列作为一种基本的数据结构在计算机科学及其相关领域中有着广泛的应用。其先进先出FIFO的特性使得队列非常适合于处理需要按顺序执行的任务。以下是队列在不同领域中的一些典型应用场景以下查询自网络
操作系统在操作系统中队列被用于多种任务调度和管理过程。例如CPU调度算法如先来先服务FCFS直接使用队列的FIFO特性来管理进程。进程控制块PCB根据进程到达的顺序排队等待CPU时间。此外I/O请求管理也常使用队列设备请求按照到达顺序排队等待处理。网络通信在网络通信中队列用于管理数据包的传输。数据包在进入网络设备如路由器或交换机时排队等待处理。这种机制帮助控制网络拥塞确保数据包以合理的顺序被转发。异步编程在异步编程模型中队列用于管理事件或消息。应用程序将事件放入队列中事件循环依次处理这些事件。这种模型在JavaScript等语言的事件驱动编程中尤为常见。打印任务管理在打印任务管理中打印任务按照提交的顺序排队等待打印。这确保了文档将按照用户提交的顺序被打印避免了因资源竞争造成的混乱。
4.一道队列的算法题LeetCode225. 用队列实现栈
学习了栈和队列的知识之后我们不妨来看一道简单的算法题——用队列实现栈。链接在上面
原题大致如下 请你仅使用两个队列实现一个后入先出LIFO的栈并支持普通栈的全部四种操作push、top、pop 和 empty。 实现 MyStack 类 void push(int x) 将元素 x 压入栈顶。int pop() 移除并返回栈顶元素。int top() 返回栈顶元素。boolean empty() 如果栈是空的返回 true 否则返回 false 。 注意 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。你所使用的语言也许不支持队列。 你可以使用 list 列表或者 deque双端队列来模拟一个队列 , 只要是标准的队列操作即可。 以下是用C语言的实现代码。由于C语言库函数没有“队列”我们只能先“造”出一个队列。
typedef int QueueDataType;// 定义队列节点结构体
typedef struct QueueNode
{QueueDataType data; // 节点存储的数据struct QueueNode* next; // 指向下一个节点的指针
} Node;// 定义队列结构体
typedef struct Queue
{Node* head; // 指向队列头节点的指针Node* tail; // 指向队列尾节点的指针size_t size; // 队列中元素的数量
} Queue;// 初始化队列
void QueueInit(Queue* q)
{// 创建哨兵节点q-head q-tail (Node*)malloc(sizeof(Node));q-head-next NULL;q-size 0;
}// 向队列中添加元素
void QueuePush(Queue* q, QueueDataType x)
{Node* newNode (Node*)malloc(sizeof(Node));newNode-data x;newNode-next NULL;q-tail-next newNode;q-tail newNode;q-size;
}// 从队列中移除元素
void QueuePop(Queue* q)
{assert(q-head-next ! NULL); // 确保队列非空Node* toDelete q-head-next;q-head-next toDelete-next;if (q-tail toDelete) // 如果移除的是尾节点更新tail指向哨兵节点{q-tail q-head;}free(toDelete);q-size--;
}// 获取队列头部元素
QueueDataType QueueFront(Queue* q)
{assert(q-head-next ! NULL);return q-head-next-data;
}// 获取队列尾部元素
QueueDataType QueueBack(Queue* q)
{assert(q-head-next ! NULL);return q-tail-data;
}// 检查队列是否为空
bool QueueEmpty(Queue* q)
{return q-head-next NULL;
}// 获取队列中元素的数量
size_t QueueSize(Queue* q)
{return q-size;
}// 销毁队列释放内存
void QueueDestroy(Queue* q)
{while (q-head-next ! NULL){QueuePop(q);}free(q-head);q-head q-tail NULL;
}// 定义栈结构体内部使用两个队列实现
typedef struct {Queue q1; // 主队列Queue q2; // 辅助队列用于实现栈的pop和top操作
} MyStack;// 创建并初始化栈
MyStack* myStackCreate() {MyStack* stack (MyStack*)malloc(sizeof(MyStack));QueueInit((stack-q1));QueueInit((stack-q2));return stack;
}// 向栈中添加元素
void myStackPush(MyStack* obj, int x) {if(QueueEmpty((obj-q2))) // 如果q2为空向q1中添加元素{QueuePush((obj-q1), x);}else // 如果q1为空向q2中添加元素{QueuePush((obj-q2), x);}
}// 从栈中移除元素
int myStackPop(MyStack* obj) {if(QueueEmpty((obj-q2))) // 如果q2为空从q1中移动元素到q2直到最后一个元素{while(obj-q1.size 1){int num QueueFront((obj-q1));QueuePop((obj-q1));QueuePush((obj-q2), num);}int ret QueueFront((obj-q1));QueuePop((obj-q1));return ret;}else // 如果q1为空从q2中移动元素到q1直到最后一个元素{while(obj-q2.size 1){int num QueueFront((obj-q2));QueuePop((obj-q2));QueuePush((obj-q1), num);}int ret QueueFront((obj-q2));QueuePop((obj-q2));return ret;}
}// 获取栈顶元素
int myStackTop(MyStack* obj) {if(QueueEmpty((obj-q2))) // 如果q2为空栈顶元素在q1的尾部{return QueueBack((obj-q1));}else // 如果q1为空栈顶元素在q2的尾部{return QueueBack((obj-q2));}
}// 检查栈是否为空
bool myStackEmpty(MyStack* obj) {return QueueEmpty((obj-q1)) QueueEmpty((obj-q2));
}// 销毁栈释放内存
void myStackFree(MyStack* obj) {QueueDestroy((obj-q1));QueueDestroy((obj-q2));free(obj);
}实现原理
该实现策略涉及两个队列q1 和 q2它们交替作为主队列和辅助队列。这种方法的核心在于利用队列的先进先出FIFO特性来模拟栈的后进先出LIFO特性。 Push 操作总是向当前非空的队列中添加新元素。如果两个队列都为空则可以选择任意一个队列进行添加。这保证了所有元素都存储在同一个队列中而另一个队列处于空闲状态待下一次pop或top操作时使用。 Pop 操作将主队列中的所有元素除最后一个元素依次出队并入队到辅助队列中然后移除并返回主队列中的最后一个元素。通过这种方式可以实现栈的LIFO特性。操作完成后主队列和辅助队列的角色会互换。 Top 操作与pop操作类似但是不移除最后一个元素只返回其值。 Empty 操作当两个队列都为空时栈也为空。
代码解析
在以上代码中Queue结构体用于实现队列的基本功能而MyStack结构体则使用两个Queue实例来模拟栈的行为。
myStackPush函数向当前活跃的队列中添加元素。myStackPop函数通过将主队列中的元素除了最后一个转移到辅助队列中然后移除并返回最后一个元素实现了栈的pop操作。此后队列的角色将互换。myStackTop函数与myStackPop类似但是在返回最后一个元素的值后不会将其移除。myStackEmpty函数检查两个队列是否都为空以确定栈是否为空。myStackFree函数负责释放两个队列和栈实例所占用的内存资源。
5.结语
队列是数据结构中的基石之一了解其原理和实现方式对于学习更复杂的数据结构和算法至关重要。通过实际编码和解决问题我们可以加深对队列结构和其应用的理解。希望这篇博客能帮助你在数据结构的学习旅程中迈出坚实的一步。
