什么是queue
- 队列是一种容器适配器，专门用于在
FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。 - 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，
queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。 - 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
- 标准容器类
deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。
queue的使用
1.queue构造函数
initialize (1)：使用已存在的容器初始化队列。
explicit queue(const container_type& ctnr);
这个构造函数接受一个已存在的容器 ctnr，并使用其内容初始化队列。
示例：
std::deque<int> myDeque = {1, 2, 3}; std::queue<int> myQueue(myDeque); // 使用已存在的 deque 初始化队列
move-initialize (2)：使用已存在的容器初始化队列，并在初始化后将原容器置为空。
explicit queue(container_type&& ctnr = container_type());
这个构造函数接受一个右值引用的容器 ctnr，将其用于初始化队列，并在初始化后清空 ctnr。
示例：
std::deque<int> myDeque = {1, 2, 3}; std::queue<int> myQueue(std::move(myDeque)); // 使用已存在的 deque 初始化队列，并清空 myDeque
allocator (3)：使用自定义分配器 Alloc 初始化队列。
template <class Alloc> explicit queue(const Alloc& alloc);
这个构造函数接受一个自定义分配器类型 Alloc，用于在初始化时分配内存。
示例：
std::allocator<int> myAllocator; std::queue<int> myQueue(myAllocator); // 使用自定义分配器初始化队列
init + allocator (4)：使用已存在的容器和自定义分配器初始化队列。
template <class Alloc> queue(const container_type& ctnr, const Alloc& alloc);
这个构造函数接受已存在的容器 ctnr 和自定义分配器 alloc，用于在初始化时指定底层容器和分配器。
示例：
std::deque<int> myDeque = {1, 2, 3}; std::allocator<int> myAllocator; std::queue<int> myQueue(myDeque, myAllocator); // 使用已存在的 deque 和自定义分配器初始化队列
move-init + allocator (5)：使用已存在的容器和自定义分配器初始化队列，并在初始化后将原容器置为空。
template <class Alloc> queue(container_type&& ctnr, const Alloc& alloc);
类似于 (2)，这个构造函数接受右值引用的容器 ctnr 和自定义分配器 alloc，用于初始化队列，并在初始化后清空 ctnr。
示例：
std::deque<int> myDeque = {1, 2, 3}; std::allocator<int> myAllocator; std::queue<int> myQueue(std::move(myDeque), myAllocator); // 使用已存在的 deque 和自定义分配器初始化队列，并清空 myDeque
copy + allocator (6)：复制已存在队列，并使用自定义分配器初始化新队列。
template <class Alloc> queue(const queue& x, const Alloc& alloc);
这个构造函数接受一个已存在的队列 x 和自定义分配器 alloc，用于在初始化时复制 x 中的元素到新的队列。
示例：
std::queue<int> originalQueue; // 添加一些元素到 originalQueue std::allocator<int> myAllocator; std::queue<int> myQueue(originalQueue, myAllocator); // 复制已存在队列并使用自定义分配器初始化新队列
move + allocator (7)：移动已存在队列，并使用自定义分配器初始化新队列。
template <class Alloc> queue(queue&& x, const Alloc& alloc);
类似于 (5)，这个构造函数接受右值引用的队列 x 和自定义分配器 alloc，用于初始化新队列并从 x 移动元素。
示例：
std::queue<int> originalQueue; // 添加一些元素到 originalQueue std::allocator<int> myAllocator; std::queue<int> myQueue(std::move(originalQueue), myAllocator); // 移动已存在队列并使用自定义分配器初始化新队列
2.empty()
bool empty() const 是 std::queue 类的成员函数之一，用于判断队列是否为空。这个函数不会修改队列的内容，因此被声明为 const，表示它不会对对象进行修改。
返回值：
如果队列为空，返回 true。
如果队列不为空，返回 false。
使用示例：
#include <iostream> #include <queue> int main() { std::queue<int> myQueue; if (myQueue.empty()) { std::cout << "Queue is empty." << std::endl; } else { std::cout << "Queue is not empty." << std::endl; } myQueue.push(42); if (myQueue.empty()) { std::cout << "Queue is empty." << std::endl; } else { std::cout << "Queue is not empty." << std::endl; } return 0; }
在这个示例中，首先创建了一个空队列 myQueue，然后通过 empty() 函数判断队列是否为空。在添加一个元素后，再次调用 empty() 函数来验证队列的状态。根据输出，你可以看到队列在没有元素时为空，在添加元素后不为空。
3.size()
size_type size() const 是 std::queue 类的成员函数之一，用于获取队列中元素的数量。这个函数不会修改队列的内容，因此被声明为 const，表示它不会对对象进行修改。
返回值：
返回队列中当前的元素数量（大小）。
使用示例：
#include <iostream> #include <queue> int main() { std::queue<int> myQueue; std::cout << "Initial size: " << myQueue.size() << std::endl; myQueue.push(42); myQueue.push(20); myQueue.push(10); std::cout << "Updated size: " << myQueue.size() << std::endl; return 0; }
在这个示例中，首先创建一个空队列 myQueue，然后使用 size() 函数获取队列的初始大小。接着添加三个元素到队列中，并再次调用 size() 函数来获取更新后的队列大小。根据输出，你可以看到队列在添加元素后大小发生了变化。
4.front()
reference& front() 和 const_reference& front() const 是 std::queue 类的成员函数之一，用于访问队列的前（头）元素。这些函数不会修改队列的内容，因此被声明为 const 或者返回常量引用，表示它们不会对对象进行修改。
reference 和 const_reference 是模板参数 T 的引用类型和常量引用类型，分别用于表示队列中元素的类型和常量引用类型。返回的引用允许你访问队列的第一个元素。
使用示例：
#include <iostream> #include <queue> int main() { std::queue<int> myQueue; myQueue.push(42); myQueue.push(20); int& firstElement = myQueue.front(); const int& constFirstElement = myQueue.front(); std::cout << "First element: " << firstElement << std::endl; std::cout << "Constant first element: " << constFirstElement << std::endl; return 0; }
在这个示例中，首先创建一个队列 myQueue，然后添加两个元素。通过 front() 函数获取队列的第一个元素，并将其存储到一个非常量引用 firstElement 和一个常量引用 constFirstElement 中。根据输出，你可以看到两种引用都可以访问队列的第一个元素的值。
5.back();
reference& back() 和 const_reference& back() const 是 std::queue 类的成员函数之一，用于访问队列的后（尾）元素。这些函数不会修改队列的内容，因此被声明为 const 或者返回常量引用，表示它们不会对对象进行修改。
reference 和 const_reference 是模板参数 T 的引用类型和常量引用类型，分别用于表示队列中元素的类型和常量引用类型。返回的引用允许你访问队列的最后一个元素。
使用示例：
#include <iostream> #include <queue> int main() { std::queue<int> myQueue; myQueue.push(42); myQueue.push(20); int& lastElement = myQueue.back(); const int& constLastElement = myQueue.back(); std::cout << "Last element: " << lastElement << std::endl; std::cout << "Constant last element: " << constLastElement << std::endl; return 0; }
在这个示例中，首先创建一个队列 myQueue，然后添加两个元素。通过 back() 函数获取队列的最后一个元素，并将其存储到一个非常量引用 lastElement 和一个常量引用 constLastElement 中。根据输出，你可以看到两种引用都可以访问队列的最后一个元素的值。
6.push
void push (const value_type& val) 和 void push (value_type&& val) 是 std::queue 类的成员函数之一，用于将元素添加到队列的末尾。
const value_type& val 是一个常量引用，用于传递需要添加到队列的元素。
value_type&& val 是一个右值引用，用于传递需要添加到队列的元素，通常用于支持移动语义。
使用示例：
#include <iostream> #include <queue> int main() { std::queue<int> myQueue; myQueue.push(42); // 使用右值 int value = 20; myQueue.push(value); // 使用左值 return 0; }
在这个示例中，首先创建一个队列 myQueue，然后使用 push() 函数将两个不同类型的值添加到队列中。第一个 push() 使用右值 42，第二个 push() 使用左值变量 value。队列将会按照元素添加的顺序保持它们。
7.emplace
template <class... Args> void emplace (Args&&... args) 是 std::queue 类的成员函数之一，用于通过构造函数参数列表直接在队列的末尾构造一个新元素。
Args... args 是模板参数包，表示传递给构造函数的参数列表。
使用 emplace() 函数可以避免额外的对象复制或移动操作，直接在容器内部构造对象。
使用示例：
#include <iostream> #include <queue> class MyObject { public: MyObject(int value) : m_value(value) { std::cout << "Constructed: " << m_value << std::endl; } ~MyObject() { std::cout << "Destructed: " << m_value << std::endl; } private: int m_value; }; int main() { std::queue<MyObject> myQueue; myQueue.emplace(42); // 使用右值参数构造 myQueue.emplace(20); // 使用右值参数构造 return 0; }
在这个示例中，首先创建一个队列 myQueue，然后使用 emplace() 函数通过右值参数直接在队列末尾构造两个 MyObject 对象。由于使用了 emplace()，对象将在队列中直接构造，而不会发生额外的复制或移动操作。
8.pop()
void pop() 是 std::queue 类的成员函数之一，用于从队列中移除队列头部的元素。
调用 pop() 函数会删除队列中的第一个元素，并将队列中的其余元素向前移动，以填补被移除的元素的位置。
使用示例：
#include <iostream> #include <queue> int main() { std::queue<int> myQueue; myQueue.push(42); myQueue.push(20); myQueue.push(10); std::cout << "Size before pop: " << myQueue.size() << std::endl; myQueue.pop(); std::cout << "Size after pop: " << myQueue.size() << std::endl; return 0; }
在这个示例中，首先创建一个队列 myQueue，然后使用 push() 函数添加三个元素到队列中。通过调用 pop() 函数，将队列头部的元素 42 移除。根据输出，你可以看到在调用 pop() 后，队列的大小减少了。
9.swap
void swap(queue& x) noexcept 是 std::queue 类的成员函数之一，用于交换当前队列与另一个队列 x 的内容。
x：一个要与当前队列进行交换的另一个队列。
noexcept：这个函数被声明为不会抛出异常，表示在交换过程中不会引发异常。
使用示例：
#include <iostream> #include <queue> int main() { std::queue<int> queue1; std::queue<int> queue2; queue1.push(42); queue1.push(20); queue2.push(10); std::cout << "Before swap:" << std::endl; std::cout << "Queue 1 front: " << queue1.front() << std::endl; std::cout << "Queue 2 front: " << queue2.front() << std::endl; queue1.swap(queue2); std::cout << "After swap:" << std::endl; std::cout << "Queue 1 front: " << queue1.front() << std::endl; std::cout << "Queue 2 front: " << queue2.front() << std::endl; return 0; }
在这个示例中，首先创建两个队列 queue1 和 queue2，并分别添加元素到它们中。通过调用 swap() 函数，交换了队列的内容。根据输出，你可以看到在交换后，队列的内容也发生了交换。
queue模拟实现
#pragma once #include <deque> namespace xzq { template<class T, class Container = deque<T>> class queue { public: void push(const T& x) { _con.push_back(x); } void pop() { _con.pop_front(); } T& back() { return _con.back(); } T& front() { return _con.front(); } const T& back() const { return _con.back(); } const T& front() const { return _con.front(); } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: Container _con; }; }
首先，这个队列类使用了一个名为 Container 的模板参数，默认值为 std::deque<T>。这允许你在创建队列对象时指定底层容器类型，如果不指定，默认使用 std::deque。
push(const T& x) 函数用于将元素 x 添加到队列的末尾，它实际上调用了底层容器的 push_back() 方法。
pop() 函数用于移除队列头部的元素，它实际上调用了底层容器的 pop_front() 方法。
back() 函数返回队列中的最后一个元素的引用，它可以用于访问队列的末尾元素。
front() 函数返回队列中的第一个元素的引用，用于访问队列的头部元素。
empty() 函数用于检查队列是否为空，它实际上调用了底层容器的 empty() 方法。
size() 函数用于获取队列中元素的数量，它实际上调用了底层容器的 size() 方法。
私有成员 _con 是底层容器对象，用于存储队列的元素。
使用这个模拟队列类，你可以选择不同的底层容器类型（默认为 std::deque），并调用类的方法来模拟队列的基本操作，如添加元素、移除元素、访问元素、判断是否为空等。这种实现方式允许你通过模板来适应不同的数据类型和底层容器，从而更加灵活地使用队列。
