queue
queue模板类的定义在<queue>头文件中。queue是容器适配器的一种，用于执行FIFO(first-in first-out)操作，从队列尾部插入元素，头部移除元素
2-1P913113140553.jpg
queue模板类
template <class T, class Container = deque<T> > class queue;
与stack模板类很相似，queue模板类也需要两个模板参数，一个是元素类型，一个容器类
型，元素类型是必要的，容器类型是可选的，默认为deque类型。
namespace std
{
template <class T, class Container = deque<T>>
class queue
{
public:
typedef Container container_type;
typedef typename container_type::value_type value_type;
typedef typename container_type::reference reference;
typedef typename container_type::const_reference const_reference;
typedef typename container_type::size_type size_type;
protected:
container_type c;
public:
queue() = default; // 默认构造函数
~queue() = default; // 默认析构函数
// 构造函数
queue(const queue& q) = default;
queue(queue&& q) = default;
queue& operator=(const queue& q) = default;
queue& operator=(queue&& q) = default;
explicit queue(const container_type& c);
explicit queue(container_type&& c)
template <class Alloc>
explicit queue(const Alloc& a);
template <class Alloc>
queue(const container_type& c, const Alloc& a);
template <class Alloc>
queue(container_type&& c, const Alloc& a);
template <class Alloc>
queue(const queue& q, const Alloc& a);
template <class Alloc>
queue(queue&& q, const Alloc& a);
bool empty() const; // 是否为空
size_type size() const; // 大小，即元素个数
reference front(); // 头部元素
const_reference front() const;
reference back(); // 尾部元素
const_reference back() const;
void push(const value_type& v); // 插入元素
void push(value_type&& v);
template <class... Args> reference emplace(Args&&... args); // reference in C++17
void pop(); // 移除元素
// 交换两个queue
void swap(queue& q) noexcept(is_nothrow_swappable_v<Container>)
};
实战
- 基本操作
#include <iostream>
#include <queue>
using namespace std;
int main ()
{
queue<int> myqueue;
int sum = 0;
// 插入元素
for (int i=1 ;i<=10; i++)
myqueue.push(i);
// 队列元素个数
cout << "queue size: "<< myqueue.size()<<endl;
// 队列是否为空
while (!myqueue.empty())
{
// 获取队列首元素
sum += myqueue.front();
// 首元素出队列
myqueue.pop();
}
// 输出最后元素
cout << "myqueue.back() is: "<< myqueue.back() <<endl;
// 元素值总合
cout << "total: " << sum << '\n';
return 0;
}
运行输出
queue size: 10
myqueue.back() is: 10
total: 55
- 交换两个队列
#include <iostream>
#include <queue>
using namespace std;
int main()
{
// Take any two queues
queue<char> queue1, queue2;
int v = 96;
for (int i = 0; i < 5; i++) {
queue1.push(v + 1);
v++;
}
for (int i = 0; i < 4; i++) {
queue2.push(v + 1);
v++;
}
// Swap elements of queues
queue1.swap(queue2);
// Print the first queue
cout << "queue1 = ";
while (!queue1.empty()) {
cout << queue1.front() << " ";
queue1.pop();
}
// Print the second set
cout << endl << "queue2 = ";
while (!queue2.empty()) {
cout << queue2.front() << " ";
queue2.pop();
}
return 0;
}
运行输出
queue1 = f g h i
queue2 = a b c d e
- 使用数组实现queue
#include <iostream>
using namespace std;
class Queue {
public:
int front, rear, size;
unsigned capacity;
int *array;
};
// 创建队列
Queue* createQueue(unsigned capacity) {
Queue *queue = new Queue();
queue->capacity = capacity;
queue->front = queue->size = 0;
queue->rear = capacity - 1;
queue->array = new int [queue->capacity * sizeof(int)];
return queue;
}
// 队列是否已满
int isFull(Queue *queue) {
return queue->size == queue->capacity;
}
// 是否为空
int isEmpty(Queue *queue) {
return queue->size == 0;
}
// 入队列
void enqueue(Queue *queue, int item) {
if (isFull(queue))
return;
queue->rear = (queue->rear + 1) % queue->capacity;
queue->array[queue->rear] = item;
queue->size = queue->size + 1;
cout << item << " enqueue to queue\n";
}
// 出队列
int dequeue(Queue *queue) {
if (isEmpty(queue))
return INT_MIN;
int item = queue->array[queue->front];
queue->front = (queue->front + 1) % queue->capacity;
queue->size = queue->size - 1;
return item;
}
// 首元素
int front(Queue *queue) {
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->front];
}
// 尾元素
int rear(Queue *queue) {
if (isEmpty(queue))
return INT_MIN;
return queue->array[queue->rear];
}
int main()
{
Queue* queue = createQueue(100);
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
enqueue(queue, 40);
cout<<dequeue(queue)<<" dequeued from queue\n";
cout << "Front item is " << front(queue) << endl;
cout << "Rear item is " << rear(queue) << endl;
return 0;
}
运行输出
10 enqueue to queue
20 enqueue to queue
30 enqueue to queue
40 enqueue to queue
10 dequeued from queue
Front item is 20
Rear item is 40
时间复杂度：以上操作都是O(1)，enqueue(), dequeue(), isFull(), isEmpty(), front() ，rear()
- 反转队列
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
void Print(queue<int>& Queue)
{
while (!Queue.empty()) {
cout << Queue.front() << " ";
Queue.pop();
}
}
// Function to reverse the queue
void reverseQueue(queue<int>& Queue)
{
stack<int> Stack;
while (!Queue.empty()) {
Stack.push(Queue.front());
Queue.pop();
}
while (!Stack.empty()) {
Queue.push(Stack.top());
Stack.pop();
}
}
int main()
{
queue<int> Queue;
Queue.push(10);
Queue.push(20);
Queue.push(30);
Queue.push(40);
Queue.push(50);
Queue.push(60);
Queue.push(70);
Queue.push(80);
Queue.push(90);
Queue.push(100);
reverseQueue(Queue);
Print(Queue);
return 0;
}
运行输出
100 90 80 70 60 50 40 30 20 10
网友评论