C++基础知识（STL标准库容器适配器（Stack和Queue））

目录

Stack

什么是容器适配器？

容器适配器的特点

基本概念

特点：

常用函数

示例代码

以List作为Stack的底层容器

Queue

基本概念

特点

常用成员函数

示例代码

以List作为Queue的底层容器

总结：

---

Stack

 在C++标准模板库（STL）中，stack是一个容器适配器，它提供了一种基于后进先出（Last In First Out, LIFO）原则的数据结构。这意味着最后一个插入到栈中的元素将是第一个被移除的元素。栈通常用于解决需要追踪回溯路径的问题，比如深度优先搜索算法，或者用于解析嵌套结构如括号匹配问题等。

什么是容器适配器？

        可能很多人在初期都没有了解过或者听过这个概念，只知道STL里面有多个容器，以及一些算法和迭代器。容器适配器的概念就是他并不是一个独立的结构，而是起来与其他的容器进行存储的，所以他叫”适配“嘛。

容器适配器的特点

容器适配器的主要特点包括：

• 封装：容器适配器封装了底层容器的功能，只暴露特定的数据结构所需的方法。
• 通用性：可以使用不同的底层容器来实现同样的数据结构。
• 简化接口：容器适配器通常提供一组简化的方法集，使得特定数据结构的操作更加方便。
• 重用：通过适配器模式，可以重用现有容器类的功能，而不必重新实现所有功能。

基本概念

栈内部实现通常是通过一个向量（vector）或一个列表（deque）来完成的，但这对使用者来说是透明的。你只需要知道栈的基本操作即可。

特点：

• 先进后出：如图所见，stack只有一个出口，后进去的元素会覆盖之前的元素。
• 无法被遍历：由于我们只能取得最顶端的元素，没有其他任何办法去存取stack的其他元素，所以stack是无法被便利的。
• 不具有迭代器：

常用函数

以下是stack的一些基本成员函数：

• push(val)：将元素val添加到栈顶。
• pop()：删除栈顶元素。
• top()：返回栈顶元素，但不删除它。
• empty()：如果栈为空则返回true，否则返回false。
• size()：返回栈中的元素数量。

示例代码

#include <iostream>
#include <stack>int main() {std::stack<int> intStack; // 创建一个空的整数栈// 向栈中压入一些元素intStack.push(1);intStack.push(2);intStack.push(3);// 输出栈顶元素std::cout << "Top element is: " << intStack.top() << std::endl;// 弹出栈顶元素intStack.pop();// 再次输出栈顶元素std::cout << "New top element is: " << intStack.top() << std::endl;// 检查栈是否为空if (intStack.empty()) {std::cout << "Stack is empty." << std::endl;} else {std::cout << "Stack is not empty." << std::endl;}// 输出栈中剩余元素的数量std::cout << "Size of stack: " << intStack.size() << std::endl;return 0;
}

在这个例子中，我们创建了一个std::stack<int>类型的栈，然后向其中添加了一些元素，并展示了如何使用top(), pop(), empty(), 和 size()方法来操作这个栈。

以List作为Stack的底层容器

        

Queue

在C++标准模板库（STL）中，queue也是一个容器适配器，它提供了一种基于先进先出（First In First Out, FIFO）原则的数据结构。这意味着最先插入到队列中的元素也将是最先被移除的元素。队列通常用于需要按顺序处理元素的场景，例如任务调度、消息队列等。

基本概念

队列是一种线性数据结构，其中元素的添加和删除发生在队列的两端：一端称为队尾（rear），另一端称为队头（front）。元素在队尾插入，在队头移除。

特点

队列的主要特点如下：

• 先进先出（FIFO）：队列中的元素按照它们被插入的顺序被移除。
• 单端操作：队列仅允许在队尾插入元素，在队头移除元素。
• 封装：队列封装了底层容器的功能，只暴露特定的数据结构所需的方法。
• 通用性：可以使用不同的底层容器来实现队列。
• 简化接口：队列提供了一组简化的方法集，使得特定数据结构的操作更加方便。
• 重用：通过适配器模式，可以重用现有容器类的功能，而不必重新实现所有功能。

常用成员函数

std::queue提供了一系列基本成员函数，用于管理和操作队列中的元素：

1. push(val)：

   • 描述：将元素val添加到队尾。
   • 参数：val 是要添加到队尾的值。
   • 返回值：无返回值。

2. pop()：

   • 描述：删除队头元素。
   • 参数：无参数。
   • 返回值：无返回值。

3. front()：

   • 描述：返回队头元素，但不删除它。
   • 参数：无参数。
   • 返回值：返回队头元素的引用或常量引用。

4. back()：

   • 描述：返回队尾元素，但不删除它。
   • 参数：无参数。
   • 返回值：返回队尾元素的引用或常量引用。

5. empty()：

   • 描述：检查队列是否为空。
   • 参数：无参数。
   • 返回值：如果队列为空，则返回true；否则返回false。

6. size()：

   • 描述：返回队列中的元素数量。
   • 参数：无参数。
   • 返回值：返回队列中元素的数量。

示例代码

#include <iostream>
#include <queue>int main() {std::queue<int> intQueue; // 创建一个空的整数队列// 向队列中添加一些元素intQueue.push(1);intQueue.push(2);intQueue.push(3);// 输出队头元素std::cout << "Front element is: " << intQueue.front() << std::endl;// 输出队尾元素std::cout << "Back element is: " << intQueue.back() << std::endl;// 弹出队头元素intQueue.pop();// 再次输出队头元素std::cout << "New front element is: " << intQueue.front() << std::endl;// 检查队列是否为空if (intQueue.empty()) {std::cout << "Queue is empty." << std::endl;} else {std::cout << "Queue is not empty." << std::endl;}// 输出队列中剩余元素的数量std::cout << "Size of queue: " << intQueue.size() << std::endl;return 0;
}

以List作为Queue的底层容器

总结：

        虽然Stack和Queue的功能相比于其他标准容器的确有些少，但是其中的特点还是可以被作用于一些特定的场景。例如之前在写一个计算的时候，就是用的stack先进后出的特性去实现了多功能运算。