C++中的常见数据结构 --- 队列、栈、列表

这篇具有很好参考价值的文章主要介绍了C++中的常见数据结构 --- 队列、栈、列表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档


前言

队列、栈、列表是其中三个最为基础和常用的数据结构,它们在编程的世界中被广泛应用,为算法和数据处理提供了不可或缺的支持。今天来简单的介绍一下!以及他们在C++中的简单用法!


一、队列(Queue)

队列是一种常见的数据结构,它按照先进先出(FIFO)的原则管理元素。队列通常用于在程序中保存和处理一系列任务或数据。

  • 入队(enqueue): 将元素添加到队列的末尾。
  • 出队(dequeue): 从队列的前端移除元素。

队列的特点是新元素总是在队列的尾部添加,而移除元素总是从队列的头部进行。队列是一个有序的集合,先进入队列的元素会先被处理

队列常常用于解决需要按顺序处理的问题,例如任务调度、广度优先搜索等。

C++标准库中 std::queue :

  • push: 将元素添加到队列的末尾
  • front: 访问队头元素
  • pop: 移除队头元素
  • empty: 检查队列是否为空

例子:

#include <iostream>
#include <queue>

int main() {
    // 创建一个队列
    std::queue<int> myQueue;
    // 入队操作
    myQueue.push(1);  
    myQueue.push(2);
    // 出队操作
    while (!myQueue.empty()) {
        std::cout << myQueue.front() << " "; // 访问队头元素
        myQueue.pop(); // 出队
    }
    return 0;
}

二、栈(Stack)

栈是一种基本的数据结构,具有后进先出(LIFO)的特性。这意味着最后进入栈的元素将首先被移除。栈通常有两个主要操作:压入(Push)和弹出(Pop)。

  • 压入(Push): 将元素添加到栈的顶部。
  • 弹出(Pop): 从栈的顶部移除元素。

栈常常用于解决解密回文,函数调用,深度优先搜索(DFS),回溯算法,括号匹配,递归算法的非递归实现,迷宫求解,编辑器的撤销操作等等。

  • 函数调用: 栈被用来存储函数调用的上下文信息,包括局部变量、返回地址等。函数调用时,局部变量等信息被压入栈,函数执行完成后再从栈中弹出
  • 深度优先搜索(DFS): 在图的深度优先搜索算法中,栈可以用于追踪遍历路径。每次访问一个节点时,将其邻接节点压入栈,然后从栈中弹出下一个节点进行继续深度搜索
  • 回溯算法: 回溯算法通常使用栈来保存当前的状态,并在需要时回退到之前的状态,以搜索所有可能的解空间
    括号匹配: 栈可以用于检查表达式中的括号是否匹配,以及判断表达式的有效性
    递归算法的非递归实现: 栈可以用于模拟递归算法的工作方式,将递归调用转化为循环结构
  • 迷宫求解: 在迷宫求解问题中,栈可以用于保存当前路径,如果当前路径无法到达目标点,则回退到上一个路径
  • 编辑器的撤销操作: 栈可以用于实现编辑器中的撤销和重做操作,存储用户操作的历史记录

C++标准库中 std::stack:

  • push: 将元素压入栈顶
  • pop: 弹出栈顶元素
  • top(): 访问栈顶元素,但不弹出
  • empty(): 检查栈是否为空
  • size(): 返回栈中元素的数量
#include <iostream>
#include <stack>

int main() {
    std::stack<int> myStack;
    // 压入元素
    myStack.push(1);
    myStack.push(2);
    // 弹出元素
    while (!myStack.empty()) {
        std::cout << myStack.top() << " "; // 访问栈顶元素
        myStack.pop(); // 弹出栈顶元素
    }
    return 0;
}

三、列表(List)

列表是一种有序可变的数据结构,用于存储一系列的元素。列表是一种非常灵活和常用的数据类型,它可以包含不同数据类型的元素,甚至可以包含其他列表。

C++标准库中 std::list:

  • push_back(): 在列表末尾插入元素
  • push_front(): 在列表开头插入元素
  • insert(): 在指定位置插入元素
  • remove(): 删除指定值的元素
  • pop_back(): 弹出并删除最后一个元素
  • front(): 访问第一个元素
  • back(): 访问最后一个元素
  • size(): 获取列表大小
  • clear(): 清空列表
  • empty(): 判断列表是否为空
  • for (auto it = myList.begin(); it != myList.end(); ++it): 使用迭代器遍历列表
#include <iostream>
#include <list>

int main() {
    // 创建一个空列表
    std::list<int> myList;
    // 在列表末尾插入元素
    myList.push_back(1);
    myList.push_back(2);
    myList.push_back(3);
    // 在列表开头插入元素
    myList.push_front(0);
    std::cout << "List elements: ";// 使用迭代器遍历列表并打印元素
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";
    }
    // 在指定位置插入元素
    auto insertPos = std::next(myList.begin(), 2);
    myList.insert(insertPos, 99);  
    myList.remove(2);// 删除指定值的元素    
    myList.pop_front();// 弹出并删除第一个元素
    myList.pop_back();// 弹出并删除最后一个元素
    // 访问第一个元素和最后一个元素
    std::cout << "First element: " << myList.front() << std::endl;
    std::cout << "Last element: " << myList.back() << std::endl;
    std::cout << "List size: " << myList.size() << std::endl; // 获取列表大小
    myList.clear();// 清空列表
    if (myList.empty()) {// 判断列表是否为空
        std::cout << "List is empty." << std::endl;
    }
    return 0;
}


总结

本节介绍了队列、栈、列表是其中三个最为基础和常用的数据结构,唐怡佳继续加油~文章来源地址https://www.toymoban.com/news/detail-815665.html

到了这里,关于C++中的常见数据结构 --- 队列、栈、列表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构——队列(C++实现)

    目录 队列的概念及结构  队列的实现 队列的代码实现 完整的源文件代码 总结 推荐题目巩固知识 队列:只允许在一端进行插入数据操作,在另一端进行删除操作的特殊线性表,队列最重要的特性是 先进先出 (First In First Out) 入队列:进行插入操作的一端称为 队尾 出队列

    2024年02月07日
    浏览(40)
  • 九、数据结构——顺序队列中的循环队列

    一、循环队列的定义 二、循环队列的实现 三、循环队列的基本操作 ①初始化 ②判空 ③判满 ④入队 ⑤出队 ⑥获取长度 ⑦打印 四、循环队列的应用 五、全部代码 在数据结构中,队列(Queue)是一种常见的线性数据结构,遵循先进先出(First In First Out,FIFO)的原则。循环队

    2024年02月15日
    浏览(47)
  • C++数据结构之队列详解

    队头填充进四个元素 此时思考一个问题,当删除元素时(元素出队列时)会出现假饱和的情况,如上图m_data[0]和m_data[1]再进行出队列操作之后,这两个位置可以容纳新的元素,但m_rear没有回到原本的m_data[0]位置,因此需要引入一个新的队列结构,环形队列,m_rear这个位置可以

    2024年02月05日
    浏览(41)
  • 数据结构——优先队列c++详解

    百度百科定义 优先队列是0个或多个元素的集合,每个元素都有一个优先权或值,对优先队列执行的操作有1) 查找;2) 插入一个新元素;3) 删除.在最小优先队列(min priority queue)中,查找操作用来搜索优先权最小的元素,删除操作用来删除该元素;对于最大优先队列(max priority queue),查找操

    2024年02月09日
    浏览(39)
  • 【数据结构(C++版)】哈希表(散列表)

    目录   1. 散列表的概念 2. 散列函数的构造方法 2.1 直接定址法 2.2 除留余数法 2.3 数字分析法 2.4 平方取中法 3. 处理冲突的方法 3.1 开放定址法 3.1.1 线性探测法 3.1.2 平方探测法 3.1.3 双散列法 3.1.4 伪随机序列法 3.2 拉链法(链接法) 4. 散列查找及性能分析 5. 哈希的应用 5.1 位

    2024年02月15日
    浏览(45)
  • 在JavaScript中的数据结构(队列)

    当我们在浏览器中打开新标签时,就会创建一个 任务队列 。这是因为每个标签都是单线程处 理所有的任务,它被称为 事件循环 。浏览器要负责多个任务,如渲染HTML,执行JavaScript代码,处理用户交互(用户输入、鼠标点击等),执行和处理异步请求。 队列(Queue) 是一种具有

    2024年02月09日
    浏览(39)
  • 【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】五、线性表中的栈(C语言 -- 顺序表实现栈)_高高的胖子的博客-CSDN博客  

    2024年02月08日
    浏览(41)
  • 数据结构-散列表的含义与C++实现

    目录 一、散列表的概念 二、散列函数的作用 三、散列表的查找技术 1. 直接寻址表 2. 线性探测法 3. 平方探测法 4. 双散列法 四、散列表的优缺点 五、总结 散列表(Hash Table)是一种数据结构,它通过散列函数将映射到散列表中的一个位置,从而实现快速的查找、插入

    2024年02月08日
    浏览(44)
  • C++数据结构与算法——栈与队列

    C++第二阶段——数据结构和算法,之前学过一点点数据结构,当时是基于Python来学习的,现在基于C++查漏补缺,尤其是树的部分。这一部分计划一个月,主要利用代码随想录来学习,刷题使用力扣网站,不定时更新,欢迎关注! 请你仅使用两个栈实现先入先出队列。队列应当

    2024年02月20日
    浏览(43)
  • c++实现数据结构栈和队列

    1、栈 头文件 源文件 主函数 2、循环队列 头文件 源文件 主函数 3、思维导图

    2024年02月08日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包