数据结构队列

前言

一，队列的基本知识

二，用数组实现队列

三，用链表实现队列

总结

前言

接下来我们将学习队列的知识，这会让我们了解队列的基本概念和基本的功能

一，队列的基本知识

(Queue)

我们先来研究队列的ADT，ADT这个概念我们再数据结构引论就已经知道ADT是什么东西了，总的来说我们先学习队列操作和特征

队列的特征

队列就跟上面的人排队一样，所以它就有一个自己的简称，First In First Out(先进先出)
所以队列就有一个简称叫FIFO

队列的功能

栈都是再栈顶进行操作的，但是队列是再对头和对尾进行操作的

队列的基本功能：

插入 push or EnQueue
删除 pop or DeQueue
返回头部 front or peek
检查是否为空 IsEmpty
检查是否满员 IsFull

C++中插入和删除为push和pop C#中的插入和删除为EnQueue和DeQueue

队列对于功能的要求

插入队尾进行操作 push=enQueue
删除对头进行操作 pop=DeQueue

这就可以参考上面的图，就是人都是队头出来的，所以队列也是一样的，删除从队列的头删除，当我们要插入的时候，就好比如队伍，我们插入是从对尾来的，所以队列也同理可得

队列的抽象视图

队列的应用

说明

我们往往都会有共享资源，但是对于用这些共享资源，我们需要进行服务请求，对于这个请求，我们可能同时又很多个，所以我们可以运用队列这个数据结构，让这些请求进行排队，每一次处理只可以处理一个请求，这样就会做的十分又条理，先来的先享受服务

实例

计算机的处理器就是一个共享资源，很多很多的程序或者说是进程需要处理器的时间片处理的，处理器每次只可以对一个进程进行服务，处理器用来执行指令，算术，和逻辑运算

补充：处理器的时间片是什么呢？

计算机里面的处理器时间片是把进程里面的每一个东西细分化，就比如：我的电脑是边听歌边打游戏的，我的电脑处理器会把这个进程细分化，比如我游戏角色正在跳跃，我们处理器就会处理游戏的跳跃，然后再取处理音乐，这个时间非常短，所以使用者是感受不到的，这个就是处理器的时间片

二，用数组实现队列

ADT

Feature

Opearations

1，EnQueue 2，DeQueue 3，Front 4，IsEmpty——————————O(1)

数组

Implementation

#include<iostream>
#include<queue>using 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];
}

这里是实现这个队列的，十分的简单，但是这个数组到最后都没了，前面全部都是空的，那我们要利用好前面的，所以我们来一个循环数组

这样的就是循环数组，我们只需这么改

#include<iostream>
#include<queue>using 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+1)%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)