queue
queue模板類的定義在<queue>頭文件中噪沙。queue是容器適配器的一種次哈，用于執(zhí)行FIFO(first-in first-out)操作螺捐，從隊(duì)列尾部插入元素码秉，頭部移除元素
2-1P913113140553.jpg
queue模板類
template <class T, class Container = deque<T> > class queue;
與stack模板類很相似逮矛，queue模板類也需要兩個模板參數(shù)，一個是元素類型转砖，一個容器類
型须鼎，元素類型是必要的，容器類型是可選的府蔗，默認(rèn)為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; // 默認(rèn)構(gòu)造函數(shù)
~queue() = default; // 默認(rèn)析構(gòu)函數(shù)
// 構(gòu)造函數(shù)
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; // 大小，即元素個數(shù)
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>)
};
實(shí)戰(zhàn)
- 基本操作
#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);
// 隊(duì)列元素個數(shù)
cout << "queue size: "<< myqueue.size()<<endl;
// 隊(duì)列是否為空
while (!myqueue.empty())
{
// 獲取隊(duì)列首元素
sum += myqueue.front();
// 首元素出隊(duì)列
myqueue.pop();
}
// 輸出最后元素
cout << "myqueue.back() is: "<< myqueue.back() <<endl;
// 元素值總合
cout << "total: " << sum << '\n';
return 0;
}
運(yùn)行輸出
queue size: 10
myqueue.back() is: 10
total: 55
- 交換兩個隊(duì)列
#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;
}
運(yùn)行輸出
queue1 = f g h i
queue2 = a b c d e
- 使用數(shù)組實(shí)現(xiàn)queue
#include <iostream>
using namespace std;
class Queue {
public:
int front, rear, size;
unsigned capacity;
int *array;
};
// 創(chuàng)建隊(duì)列
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;
}
// 隊(duì)列是否已滿
int isFull(Queue *queue) {
return queue->size == queue->capacity;
}
// 是否為空
int isEmpty(Queue *queue) {
return queue->size == 0;
}
// 入隊(duì)列
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";
}
// 出隊(duì)列
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;
}
運(yùn)行輸出
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
時間復(fù)雜度：以上操作都是O(1)姓赤，enqueue(), dequeue(), isFull(), isEmpty(), front() 赡译，rear()
- 反轉(zhuǎn)隊(duì)列
#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;
}
運(yùn)行輸出
100 90 80 70 60 50 40 30 20 10
