首页 > 编程语言 >C++STL~~stack&queue

C++STL~~stack&queue

时间：2024-09-14 15:25:58浏览次数：3  
标签：std 压入 STL 元素 pop queue int push stack

文章目录

stack&queue的概念

stack（栈）
概念和特点
栈是一种后进先出（Last In First Out，LIFO）的数据结构。就像一叠盘子，最后放上去的盘子最先被拿走。
在这里插入图片描述

queue（队列）
概念和特点
队列是一种先进先出（First In First Out，FIFO）的数据结构。类似于排队买东西，先到的人先得到服务。
在这里插入图片描述

stack&queue的使用

stack的使用
在这里插入图片描述

例如：

#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    // 向栈中压入一些元素
    s.push(10);
    s.push(20);
    s.push(30);

    // 输出栈的大小
    std::cout << "初始栈的大小为：" << s.size() << std::endl;

    // 检查栈是否为空
    if (!s.empty()) {
        std::cout << "栈不为空。" << std::endl;
    }

    // 获取栈顶元素并输出
    std::cout << "栈顶元素为：" << s.top() << std::endl;

    // 弹出栈顶元素
    s.pop();

    // 再次输出栈顶元素和栈的大小
    std::cout << "弹出一个元素后，栈顶元素为：" << s.top() << std::endl;
    std::cout << "此时栈的大小为：" << s.size() << std::endl;

    // 继续弹出元素直到栈为空
    while (!s.empty()) {
        s.pop();
    }

    // 检查栈是否为空
    if (s.empty()) {
        std::cout << "栈已为空。" << std::endl;
    }

    return 0;
}
}

首先向栈中压入一些元素，然后展示了如何使用size获取栈的大小，empty判断栈是否为空，top获取栈顶元素，以及pop弹出栈顶元素。
queue的使用
在这里插入图片描述

#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    // 检查初始时队列是否为空
    std::cout << "初始时队列是否为空：" << (q.empty()? "是" : "否") << std::endl;
    std::cout << "初始队列大小：" << q.size() << std::endl;

    // 向队列中添加元素
    q.push(10);
    q.push(20);
    q.push(30);

    // 输出队列的大小和队首、队尾元素
    std::cout << "添加元素后队列大小：" << q.size() << std::endl;
    std::cout << "队首元素（front）：" << q.front() << std::endl;
    std::cout << "队尾元素（back）：" << q.back() << std::endl;

    // 弹出一个元素
    q.pop();

    // 再次输出队列的大小和队首、队尾元素
    std::cout << "弹出一个元素后队列大小：" << q.size() << std::endl;
    std::cout << "队首元素（front）：" << q.front() << std::endl;
    std::cout << "队尾元素（back）：" << q.back() << std::endl;

    // 检查队列是否为空
    std::cout << "此时队列是否为空：" << (q.empty()? "是" : "否") << std::endl;

    return 0;
}

首先展示了初始时队列的空状态和大小，然后添加元素后展示了队列的大小、队首和队尾元素，接着弹出一个元素后再次展示相关信息，最后检查队列是否为空。需要注意的是，queue中没有top函数，因为queue的特点决定了只能从队首和队尾进行操作。

stack&queue的练习

1.最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void
pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。

输入： [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出： [null,null,null,null,-3,null,0,-2]

思路：

  • 1.首先，使用一个普通的栈来存储元素，这个栈用于实现push、pop和top操作。
  • 2.为了能够在常数时间内获取最小元素，再使用另一个栈来存储当前的最小元素。每当向主栈中压入一个元素时，如果这个元素小于等于辅助栈的栈顶元素（或者辅助栈为空时），就将这个元素也压入辅助栈。这样，辅助栈的栈顶始终是当前主栈中的最小元素。
  • 3.当执行pop操作时，如果弹出的元素等于辅助栈的栈顶元素，那么也从辅助栈中弹出这个元素，以保证辅助栈的栈顶始终是当前主栈中的最小元素。
#include <iostream>
#include <stack>

class MinStack {
private:
    std::stack<int> mainStack;
    std::stack<int> minStack;
public:
    MinStack() {}

    void push(int val) {
        mainStack.push(val);
        if (minStack.empty() || val <= minStack.top()) {
            minStack.push(val);
        }
    }

    void pop() {
        if (mainStack.top() == minStack.top()) {
            minStack.pop();
        }
        mainStack.pop();
    }

    int top() {
        return mainStack.top();
    }

    int getMin() {
        return minStack.top();
    }
};

使用以下方式测试这个类

int main() {
    MinStack minStack;
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    std::cout << minStack.getMin() << std::endl;
    minStack.pop();
    std::cout << minStack.top() << std::endl;
    std::cout << minStack.getMin() << std::endl;
    return 0;
}

2.栈的弹出压入序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

  1. 0<=pushV.length == popV.length <=1000
  2. -1000<=pushV[i]<=1000
  3. pushV 的所有数字均不相同

示例1 输入： [1,2,3,4,5],[4,5,3,2,1] 返回值：true 说明：
可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop() 这样的顺序得到[4,5,3,2,1]这个序列，返回true
示例2
输入：[1,2,3,4,5],[4,3,5,1,2]
返回值：false
说明：
由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false

思路：

  • 1.使用一个辅助栈来模拟入栈和出栈的过程。
  • 2.遍历压入序列pushV，将元素依次压入辅助栈。
  • 3.同时，遍历弹出序列popV，检查辅助栈的栈顶元素是否与当前要弹出的元素相等。如果相等，则从辅助栈弹出该元素，继续检查下一个弹出元素；如果不相等，则继续从压入序列中压入元素到辅助栈，直到辅助栈的栈顶元素与当前要弹出的元素相等或者压入序列遍历完。
  • 4.如果最终辅助栈为空，说明弹出序列是可能的，否则不可能。
#include <iostream>
#include <vector>
#include <stack>

class Solution {
public:
    bool isPopOrder(std::vector<int> pushV, std::vector<int> popV) {
        std::stack<int> s;
        int i = 0, j = 0;
        while (i < pushV.size()) {
            s.push(pushV[i++]);
            while (!s.empty() && s.top() == popV[j]) {
                s.pop();
                j++;
            }
        }
        return s.empty();
    }
};

使用以下方式测试这个函数

int main() {
    Solution solution;
    std::vector<int> pushV = {1, 2, 3, 4, 5};
    std::vector<int> popV = {4, 5, 3, 2, 1};
    bool result = solution.isPopOrder(pushV, popV);
    std::cout << (result? "true" : "false") << std::endl;
    return 0;
}

3.二叉树的分层遍历**
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 (即逐层地，从左到右访问所有节点）。
在这里插入图片描述
思路

  • 1.使用一个队列来实现层序遍历。首先将根节点入队。
  • 2.不断循环，当队列不为空时：
    • 记录当前队列的大小size，这个大小表示当前层的节点个数。
    • 遍历当前层的所有节点，对于每个节点：
    • 取出节点的值，将其加入到结果列表中。
    • 如果该节点有左子节点，将左子节点入队。
    • 如果该节点有右子节点，将右子节点入队。
  • 3.循环结束后，就得到了二叉树的层序遍历结果。
#include <iostream>
#include <vector>
#include <queue>

// 定义二叉树节点结构体
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    std::vector<std::vector<int>> levelOrder(TreeNode* root) {
        std::vector<std::vector<int>> result;
        if (!root) return result;
        std::queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int size = q.size();
            std::vector<int> level;
            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(level);
        }
        return result;
    }
};

使用以下方式测试这个函数

int main() {
    // 构建二叉树
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);

    Solution solution;
    std::vector<std::vector<int>> result = solution.levelOrder(root);
    for (const auto& level : result) {
        for (int val : level) {
            std::cout << val << " ";
        }
        std::cout << std::endl;
    }

    // 释放内存
    delete root->right->right;
    delete root->right->left;
    delete root->right;
    delete root->left;
    delete root;

    return 0;
}

总结

关于数据结构版本的stack&queue：数据结构~~栈和队列
栈（Stack）

  1. 后进先出原则。

  2. 主要操作包括入栈（push）和出栈（pop）。

  3. 常用于函数调用、表达式求值、括号匹配等场景。

队列（Queue）

  1. 先进先出原则。

  2. 主要操作包括入队（enqueue）和出队（dequeue）。

  3. 常用于任务调度、排队系统、广度优先搜索等。

两者都是基本的数据结构，具有不同的特点和适用场景，在程序设计中发挥着重要作用。

标签：std,压入,STL,元素,pop,queue,int,push,stack
From： https://blog.csdn.net/2301_78029441/article/details/142258654

相关文章

  • 使用脚本部署openstack平台
    一、案例分析1.部署架构一台控制节点和一台计算节点组成简单架构OpenStack平台，控制节点安装MySQL、Keystone、Glance、Nova、Neutron、Dashboard等服务，主要作为认证、镜像管理节点，以及提供Nova和Neutron服务的管理节点。提供Dashboard界面服务。计算节点主要安装nova-comput......
  • Team Queue（队列）
    #include<bits/stdc++.h>usingnamespacestd;#definexfirst#defineysecondtypedefpair<int,int>PII;typedeflonglongll;typedefunsignedlonglongull;typedefunsignedintuint;typedefvector<string>VS;typedefvector<int>......
  • 科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）
    介绍R语言的扩展物种堆积图是一种数据可视化工具，它不仅展示了物种的堆积结果，还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异，为研究者提供了一种有效的数据解读方式。加载R包knitr::opts_chunk$set(warning......
  • 栈Stack——递归替身？
     对于Stack这个集合类，由类继承关系可知是Vector的子类，根据push入栈方法跟踪代码，可知Vector是一个线程安全的类（高并发场景下使用，那可能不是一个好的选择）  看到这里，显然可以得知Stack入栈出栈的大致原理，就是Vector的elementData对象数组，用来储存数据，入栈时依次存放，出栈时......
  • C++模拟实现stack和queue(容器适配器)
    适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。简单理解，将模板参数给成容器，就是容器适配器，写成参数的容器的各种接口，均满足需要。#include<list>#includ......
  • 并发编程 - NSOperation&NSOperationQueue（多线程）
    ​​​​​​​并发编程-概述-CSDN博客并发编程-GCD的任务和队列-CSDN博客并发编程-NSOperation&NSOperationQueue（多线程）-CSDN博客并发编程-NSThread-CSDN博客引言在上篇博客中我们首先介绍了GCD的多线程方案，NSOperation和NSOperationQueue是Apple为我们提供的......
  • 为什么Java已经不推荐使用Stack了？
    为什么不推荐使用StackJava已不推荐使用Stack，而是推荐使用更高效的ArrayDeque为什么不推荐使用性能低：是因为Stack继承自Vector，而Vector在每个方法中都加了锁。由于需要兼容老的项目，很难在原有的基础上进行优化，因此Vector就被淘汰掉了，使用ArrayList和CopyOnWriteAr......
  • Java集合——Queue详解
    Queue详解基本概念功能分类主要方法普通队列双端队列阻塞队列使用示例总结基本概念Java中的Queue接口表示一种先进先出（FIFO,FirstInFirstOut）的数据结构，但实际上它也支持其他插入和删除策略。Queue是Java集合框架的一部分，它继承自Collection接口，并且定义......
  • STL01——手写简单版本的vector
    STL01——手写简单版本的vector设计一个名为MyVector的Vector类，该类应具备以下功能和特性：1、基础成员函数：构造函数：初始化Vector实例析构函数：清理资源，确保无内存泄露拷贝构造函数：允许通过现有的MyVector实例来创建一个新实例拷贝赋值操作符：实现MyVector......
  • C++中STL容器的使用
    容器一些基本操作语法vector初始化操作vector<int>a;//声明向量vector<int>a(10);//声明一个初始大小为10的向量vector<int>a(10,1);//初始大小为10，且值都为1的向量vector<int>b(a);//声明并用向量a初始化向量bvector<int>b(a.begin(),a.begin()+3);//将......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99