【数据结构】队列

一、介绍

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

二、队列的实现方法

1、队列的数组实现

1.在实例化队列时确定数组大小并初始化数组。

2.队列功能：

① 插入元素（元素在队尾入队）push(int num)

② 删除元素（在队头元素出队）pop()

③ 查看队头元素（只查看，不删除）front()

④ 判空 isEmpty()

⑤ 判满 isFull()

⑥ 查看队列长度 length()

⑦ 清空队列 clear()

3.代码实现

（1）定长数组实现

#include <iostream>
#include <string>
using namespace std;class Myqueue
{
private:int head,tail;//队头指针，对尾指针int count;//记录队列元素数量int size;//队列容量（数组初始化大小）int* data;//数组
public:Myqueue(int capacity);~Myqueue();void push(int num);void front();void pop();bool isEmpty();bool isFull();int length();
};Myqueue::Myqueue(int capacity)
{head=0,tail=0;count=0;size=capacity;data=new int[capacity];}Myqueue::~Myqueue()
{delete []data;
}void Myqueue::push(int num)
{if(isFull()){std::cout<<"error"<<std::endl;return;}data[tail]=num;tail=(tail+1)%size;count++;}void Myqueue::front()
{if(isEmpty()){std::cout<<"error"<<std::endl;}else{std::cout<<data[head]<<std::endl;}}void Myqueue::pop()
{if(isEmpty()){std::cout<<"error"<<std::endl;}else{std::cout<<data[head]<<std::endl;head=(head+1)%size;count--;}
}bool Myqueue::isEmpty()
{return count==0;
}bool Myqueue::isFull()
{return count==size;
}bool Myqueue::length()
{return count;
}void Myqueue::clear()
{while(head!=tail){pop();}
}

（2）环形数组实现

#include <iostream>
#include <vector>
using namespace std;/* 基于环形数组实现的队列 */
class ArrayQueue {
public:ArrayQueue(int capacity);~ArrayQueue();int capacity();//获取队列容量int size();//获取队列长度bool isEmpty();  //队列判空void push(int num);//元素入队int peek();     //返回队首元素int pop();      //元素出队vector<int> toVector();private:int* nums;       // 用于存储队列元素的数组int front;       // 队首指针，指向队首元素int queSize;     // 队列长度int queCapacity; // 队列容量};ArrayQueue::ArrayQueue(int capacity):queCapacity(capacity),queSize(0),front(0),nums(new int[capacity])
{
}ArrayQueue::~ArrayQueue()
{delete[] nums;
}/* 获取队列的容量 */
int ArrayQueue::capacity()
{return queCapacity;
}/* 获取队列的长度 */
int ArrayQueue::size()
{return queSize;
}/* 判断队列是否为空 */
bool ArrayQueue::isEmpty()
{return queSize == 0;
}/* 入队 */
void ArrayQueue::push(int num)
{if (queSize == queCapacity){std::cout << "队列已满" << std::endl;return;}//计算队尾指针，指向队尾索引+1//这是一个环形数组，通过取余操作实现rear越过数组尾部后回到头部int rear = (front + queSize) % queCapacity;nums[rear] = num;queSize++;}/* 访问队首元素 */
int ArrayQueue::peek()
{if (isEmpty()){throw out_of_range("队列为空");}return nums[front];
}/* 出队 */
int ArrayQueue::pop()
{int num = peek();//队首指针向后移动一位，若越过尾部，则返回到数组头部front = (front + 1) % queCapacity;--queSize;return num;
}/* 将数组转化为 Vector 并返回 */
vector<int> ArrayQueue::toVector()
{vector<int> arr(queSize);//仅转换有效长度范围内的列表元素for (int i = 0, j = front; i < queSize; i++, j++){arr[i] = nums[j % queCapacity];}return arr;
}

2、队列的链表实现

#include <iostream>
#include <vector>
using namespace std;/* 链表节点结构体 */
struct ListNode
{int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}  // 构造函数
};class LinkedListQueue {
private:ListNode* front, *rear; // 头节点 front ，尾节点 rearint queSize;
public:LinkedListQueue();~LinkedListQueue();int size();			//获取队列长度bool isEmpty();		//判断队列是否为空void push(int num);	//入队int pop();			//出队int peek();			//访问队首元素vector<int> toVector(); //链表转换为vector
};LinkedListQueue::LinkedListQueue():front(nullptr),rear(nullptr),queSize(0)
{}LinkedListQueue::~LinkedListQueue()
{// 遍历链表删除节点，释放内存while (front != nullptr){ListNode* tmp = front;front = front->next;delete tmp;}
}int LinkedListQueue::size()
{return queSize;
}bool LinkedListQueue::isEmpty()
{return size() == 0;
}/*尾插法*/
void LinkedListQueue::push(int num)
{ListNode* node = new ListNode(num);//如果队列为空，则令头、尾节点都指向该节点if (front == nullptr){front = node;rear = node;}else//队列不为空，则将该节点添加到尾节点后{rear->next = node;rear = node;}++queSize;
}int LinkedListQueue::peek()
{if (size() == 0){throw out_of_range("队列为空");}	return front->val;
}//队头出队
int LinkedListQueue::pop()
{//获取队首元素int num = peek();ListNode* tmp = front;front = front->next;//释放内存delete tmp;--queSize;return num;
}vector<int> LinkedListQueue::toVector()
{vector<int> nums;ListNode* node = front;while (node != nullptr){nums.push_back(node->val);node = node->next;}return nums;
}