C++实现列表与双端队列操作转换示例

本篇代码示例展示了在C++中利用`list`和`deque`这两种标准库中的线性容器实现列表队列（一种先进先出或后进先出的数据结构）的应用。列表队列通常不直接由这些容器提供，但可以通过它们的特性来模拟。 首先，我们引入了必要的头文件`<iostream>`、`<list>`和`<deque>`，并使用`std`命名空间。`#include`指令包含了这些库，用于处理输入输出操作以及容器的定义。 **1. deque的应用** `deque`（双端队列）是一个动态数组，支持在两端进行高效的插入和删除操作。在`main()`函数中，创建了一个`deque<int>`类型的变量`s`，然后通过`push_front()`方法将用户输入的整数依次添加到队列的前端，这体现了其先进先出（FIFO）的特点。`printContainer`函数被用来打印容器的内容。 ```cpp deque<int> s; for (int i = 0; i < 10; i++) { int x; cin >> x; s.push_front(x); } printContainer("deque at first", s); ``` **2. list的应用** `list`是一个双向链表，插入和删除元素的时间复杂度较低，但在两端操作效率不如`deque`。这里，我们将`deque`的内容转换为`list`，使用`rbegin()`和`rend()`获取逆序迭代器，实现了从`deque`的尾部开始遍历，并使用`erase()`删除元素，然后将删除的元素插入到下一个位置，模拟了后进先出（LIFO）的行为。 ```cpp list<int> l(s.rbegin(), s.rend()); printContainer("List at first", l); list<int>::iterator iter = l.begin(); while (iter != l.end()) { int v = *iter; iter = l.erase(iter); l.insert(++iter, v); } printContainer("list at last", l); ``` **3. 从list回填deque** 最后，将处理后的`list`的内容重新赋值给`deque`，这样`deque`就具有了`list`的最后一个元素在最前面的新状态，完成了列表队列的构建。 ```cpp s.assign(l.begin(), l.end()); printContainer("deque at last", s); ``` 总结来说，这段代码展示了如何通过C++的`deque`和`list`容器实现一个简单的列表队列，通过前后端操作模拟了先进先出和后进先出的特性。在实际应用中，根据性能需求和数据访问模式，可以选择合适的数据结构。