出售家教网站模板,做卷皮网类似网站,做金融网站有哪些要求,张掖网站设计公司目录 前言 一#xff0c;队列的基本知识 二#xff0c;用数组实现队列 三#xff0c;用链表实现队列 总结 前言
接下来我们将学习队列的知识#xff0c;这会让我们了解队列的基本概念和基本的功能 一#xff0c;队列的基本知识 (Queue) 我们先来研究队列的ADT#xff0c…目录 前言 一队列的基本知识 二用数组实现队列 三用链表实现队列 总结 前言
接下来我们将学习队列的知识这会让我们了解队列的基本概念和基本的功能 一队列的基本知识 (Queue) 我们先来研究队列的ADTADT这个概念我们再数据结构引论就已经知道ADT是什么东西了总的来说我们先学习队列操作和特征 队列的特征 队列就跟上面的人排队一样所以它就有一个自己的简称First In First Out(先进先出) 所以队列就有一个简称叫FIFO 队列的功能 栈都是再栈顶进行操作的但是队列是再对头和对尾进行操作的 队列的基本功能 插入push or EnQueue删除pop or DeQueue 返回头部front or peek检查是否为空IsEmpty检查是否满员IsFull C中插入和删除为push和pop C#中的插入和删除为EnQueue和DeQueue 队列对于功能的要求 插入队尾进行操作 pushenQueue删除对头进行操作 popDeQueue 这就可以参考上面的图就是人都是队头出来的所以队列也是一样的删除从队列的头删除当我们要插入的时候就好比如队伍我们插入是从对尾来的所以队列也同理可得 队列的抽象视图 队列的应用 说明 我们往往都会有共享资源但是对于用这些共享资源我们需要进行服务请求对于这个请求我们可能同时又很多个所以我们可以运用队列这个数据结构让这些请求进行排队每一次处理只可以处理一个请求这样就会做的十分又条理先来的先享受服务 实例 计算机的处理器就是一个共享资源很多很多的程序或者说是进程需要处理器的时间片处理的处理器每次只可以对一个进程进行服务处理器用来执行指令算术和逻辑运算 补充处理器的时间片是什么呢 计算机里面的处理器时间片是把进程里面的每一个东西细分化就比如我的电脑是边听歌边打游戏的我的电脑处理器会把这个进程细分化比如我游戏角色正在跳跃我们处理器就会处理游戏的跳跃然后再取处理音乐这个时间非常短所以使用者是感受不到的这个就是处理器的时间片 二用数组实现队列 ADT Feature Opearations 1EnQueue 2DeQueue 3Front 4IsEmpty——————————O(1) 数组 Implementation #includeiostream
#includequeueusing namespace std;int A[10];
int rear -1;
int front -1;bool IsEmpty();
void EnQueue(int x);int main()
{}bool IsEmpty() {if (front -1 rear -1) {return false;}else {return true;}
}void EnQueue(int x) {if (rear size(A) - 1) {cout Queue is full endl;return;}else if (IsEmpty()) {front 0;rear 0;}else {rear rear 1;}A[rear] x;
}void DeQueue() {if (IsEmpty()) {return;}else if (rear front) {front rear -1;}else {front front 1;}
}int front1(){return A[front];
} 这里是实现这个队列的十分的简单但是这个数组到最后都没了前面全部都是空的那我们要利用好前面的所以我们来一个循环数组 这样的就是循环数组我们只需这么改 #includeiostream
#includequeueusing namespace std;int A[10];
int rear -1;
int front -1;bool IsEmpty();
void EnQueue(int x);int main()
{}bool IsEmpty() {if (front -1 rear -1) {return false;}else {return true;}
}void EnQueue(int x) {if ((rear1)%10 front) {cout Queue is full endl;return;}else if (IsEmpty()) {front 0;rear 0;}else {rear (rear 1) % 10;}A[rear] x;
}void DeQueue() {if (IsEmpty()) {return;}else if (rear front) {front rear -1;}else {front (front 1) % 10;}
}int front1(){return A[front];
} 三用链表实现队列 #include iostream
using namespace std;// 队列节点结构
struct Node {int data;Node* next;Node(int val) : data(val), next(nullptr) {}
};// 链表实现的队列
class Queue {
private:Node* frontNode; // 头指针Node* rearNode; // 尾指针
public:Queue() : frontNode(nullptr), rearNode(nullptr) {}// 判断队列是否为空bool isEmpty() {return frontNode nullptr;}// 入队操作void enqueue(int val) {Node* newNode new Node(val);if (isEmpty()) {frontNode rearNode newNode;} else {rearNode-next newNode;rearNode newNode;}}// 出队操作void dequeue() {if (isEmpty()) {cout Queue is empty! endl;return;}Node* temp frontNode;frontNode frontNode-next;delete temp;if (frontNode nullptr) {rearNode nullptr; // 如果队列为空尾指针也置空}}// 获取队头元素int front() {if (isEmpty()) {cout Queue is empty! endl;return -1; // 返回一个错误值}return frontNode-data;}// 析构函数释放所有节点~Queue() {while (!isEmpty()) {dequeue();}}
};int main() {Queue q;q.enqueue(10);q.enqueue(20);q.enqueue(30);cout Front: q.front() endl; // 输出 10q.dequeue();cout Front after dequeue: q.front() endl; // 输出 20q.dequeue();q.dequeue();q.dequeue(); // 额外出队测试空队列情况return 0;
} 或者头插法与尾插法这个尾插法我们升级一下用这个指针指向尾巴这样就可以让两个时间复杂度都是O(1) 总结
这个队列十分简单真的就是头出尾进罢了
