当前位置: 首页> 科技> 互联网 > C++基础知识(STL标准库容器适配器(Stack和Queue))

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

时间:2025/7/9 7:07:35来源:https://blog.csdn.net/LKHzzzzz/article/details/141924512 浏览次数:0次

目录

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先进后出的特性去实现了多功能运算。

关键字:C++基础知识(STL标准库容器适配器(Stack和Queue))

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: