C++-阿南达文事网

C++

队列

一种操作受限制的线性表

一、基本概念：

队列是一种线性储存数据结构，数据元素遵循“先进先出”（First in First out （FIFO））的原则
添加元素在队尾（只允许添加元素）实现，删除元素在对头（只允许删除元素）实现

适用条件

排队挂号消息队列广度优先搜索等符合队列特点的操作

二、队列的操作：

queue<int> q;	//以int型为例
int x;
q.empty()               如果队列为空返回true，否则返回false
q.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++ 队列