队列
一种操作受限制的线性表
一、基本概念：
队列是一种线性储存数据结构，数据元素遵循“先进先出”（First in First out （FIFO））的原则添加元素在队尾（只允许添加元素）实现，删除元素在对头（只允许删除元素）实现适用条件
排队 挂号消息队列广度优先搜索等符合队列特点的操作
二、队列的操作：
queue<int> q;//以int型为例int x;q.empty()如果队列为空返回true，否则返回falseq.size()返回队列中元素的个数q.pop() 删除队列首元素但不返回其值q.front()返回队首元素的值，但不删除该元素q.push(x)在队尾压入新元素q.back()返回队列尾元素的值，但不删除该元素
三、 队列的分类;
基于数组的循环队列（循环队列）基于链表的队列（链表队列）四、基于数组的循环队列
数组存储的缺点：
入队操作：在数组的末尾添加元素，时间复杂度为O（1）
出队操作：数组头部元素出队之后，头部之后的元素均需要往前移动一个位置，时间复杂度为O（n）
循环队列
为了降低时间复杂度，将数组当作一个首尾相连的圆环，分别用两个标志front、rear代表队列的头部和尾部。删除元素时，队首标志往后移，添加元素时，若队尾没有空间，考虑数组的头部空间若还有，则在队头添加元素，防止数组内存空间的流失。
判断满或空的方法：
方法一：
设置一个标志变量flag，同时满足front=rear且flag=1时为满队列
方法二:
空一个元素，保持为空
1.空队列：队首标志与队尾重合
2.满队列：队尾标志+1=队首标志
C++实现：
#include<iostream>using namespace std;//队列的抽象类template <class T>class queue{public:virtual ~queue() {};virtual bool empty() const=0; virtual int size() const=0; virtual T& front() = 0;virtual void pop() = 0;virtual void push(const T& theElement) = 0;};//队列的数组类实现template<class T>class arrayQueue :public queue<T>{arrayQueue(int initialCapacity = 10);~arrayQueue() { delete[]queue; }bool empty()const{if (queuefront == queuerear)return true;return false;}int size() const{return (queuerear - queuefront + capacity) % capacity;}T& front(){if (queuefront == queuerear){cout << "The queue is empty!" << endl;return false;}return queue[queuefront];}void pop(){if (queuefront == queuerear)cout << "The queue is empty!" << endl;queue[queuefront].~T;queuefront = (queuefront + 1) % capacity;}void push(const T& theElement);private:int capacity;int queuefront;int queuerear;T* queue;};template<class T>arrayQueue<T>::arrayQueue(int initialCapacity){if (initialCapacity < 1)cout << "InitialCapacity must >0!" << endl;capacity = initialCapacity;queue = new T[capacity];queuefront = 0;queuerear = 0;}template<class T>void arrayQueue<T>::push(const T& theElement){if ((queuerear + 1) % capacity == queuefront){T* temp = new T[2 * capacity];//没有形成环if (queuefront == 0)copy(queuefront, queuerear, temp);else{copy(queuefront, queue + capacity, temp);copy(queue, queuerear, temp + queue + capacity - queuefront);}queuefront = 0;queuerear = capacity-1;delete[]queue;queue = temp;}queue[queuerear] = theElement;queuerear = (queuerear + 1) % capacity;}
五、基于链表的队列
特点：
以结构体节点为单位，不存在元素移动复杂度问题以及内存的浪费问题。
链表头为队列头部，链表尾为队列尾部。
设计两个变量queueFront、queueBack记录队列的两端变化
指针queueFront为标志头指针，指针queueBack指向最后一个元素
C++实现
#include<iostream>using namespace std;//队列节点结构体template<class T>struct QueueNode{T element; //存储元素QueueNode<T>* next; //记录下一个队列节点QueueNode(T a, QueueNode<T>* b=nullptr){this->element = a;this->next = b;}};template<class T>class ChainQueue{public:ChainQueue();~ChainQueue();bool Empty()const;int size() const;void pop();void push(T theElement);T& top();private:QueueNode<T>* front; //指向头部前一位的空指针QueueNode<T>* back; //指向队列尾部的指针int count;};//队列的具体实现template<class T>ChainQueue<T>::ChainQueue(){front = new QueueNode<T>(NULL);back = front;count = 0;}template<class T>ChainQueue<T>::~ChainQueue(){while (front->next!= nullptr){QueueNode<T> *temp = front->next;front->next = front->next->next;delete temp;}}template<class T>bool ChainQueue<T>::Empty()const{if (front==back)return true;return false;}template<class T>int ChainQueue<T>::size() const{return count;}template<class T>void ChainQueue<T>::pop(){if (count == 0)cout << "The ChainQueue is empty!" << endl;QueueNode<T>* temp = front->next;front->next = front->next->next;delete temp;count--;}template<class T>void ChainQueue<T>::push(T theElement){QueueNode<T>* temp = new QueueNode<T>(theElement);back->next = temp;back = temp;count++;}template<class T>T& ChainQueue<T>::top(){if (count == 0)cout<<"The ChainQueue is empty!"<<endl;return front->next->element;}int main(){ChainQueue<int> cq;cout << "Empty? " <<cq.Empty() <<endl;cq.push(10);cq.push(20);cout << "The top element is" << cq.top() << endl;cout << "The size is " << cq.size() << endl;cq.push(30);cq.push(40);cq.pop();cout << "The top element is" << cq.top() << endl;cout << "The size is " << cq.size() << endl;cq.pop();cq.pop();cout << "The top element is" << cq.top() << endl;cout << "The size is " << cq.size() << endl;system("pause");return 0;}
C++队列_Potato_10的博客-CSDN博客_c++ 队列
C++队列详解_T_Y_F666的博客-CSDN博客_c++ 队列
如果觉得《C++-queue：queue基本用法【q.push(x) q.front() q.back() q.pop() q.size() q.empty()】》对你有帮助，请点赞、收藏，并留下你的观点哦！
