【C++】stack和queue

embedded/2024/10/18 23:29:38/

📢博客主页：https://blog.csdn.net/2301_779549673
📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！
📢本文由 JohnKi 原创，首发于 CSDN🙉
📢未来很长，值得我们全力奔赴更美好的生活✨

在这里插入图片描述

在这里插入图片描述

文章目录

  • 🏳️‍🌈1.stack的介绍和使用
    • ❤️最小栈的实现
    • 🧡栈的弹出压入序列
    • 💛stack的模拟实现
  • 🏳️‍🌈2.queue的介绍和使用
    • ❤️用队列实现栈
    • 🧡queue的模拟实现
  • 👥总结

🏳️‍🌈1.stack的介绍和使用

栈是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出（Last In First Out，LIFO）的原则存储数据。打个比方，栈就像一摞盘子，只能从最上面取盘子（删除）或者往最上面放盘子（插入）。
在这里插入图片描述
在这里插入图片描述

❤️最小栈的实现

在这里插入图片描述

class MinStack
{public :void push(int x){// 只要是压栈，先将元素保存到_elem中_elem.push(x);// 如果x小于_min中栈顶的元素，将x再压入_min中if (_min.empty() || x <= _min.top())_min.push(x);} v	oid pop(){// 如果_min栈顶的元素等于出栈的元素，_min顶的元素要移除if (_min.top() == _elem.top())_min.pop();_elem.pop();} int top() { return _elem.top(); }int getMin() { return _min.top(); }
private:// 保存栈中的元素std::stack<int> _elem;// 保存栈的最小值std::stack<int> _min;
};

一、整体结构
这段代码定义了一个名为MinStack的类，用于实现一个具有获取最小元素功能的栈。这个类使用了 C++ 标准库中的std::stack容器来存储栈中的元素和最小元素。

二、成员函数分析
push(int x)函数：
首先，无论什么情况，将元素x压入_elem栈中，这个栈用于存储所有的元素。
接着，判断_min栈是否为空或者x是否小于等于_min栈顶元素。如果满足条件，说明x可能是当前栈中的最小元素，将x压入_min栈中。这样，_min栈始终保持着当前栈中最小元素在栈顶的状态。

pop()函数：
当执行出栈操作时，先判断_min栈顶元素是否等于_elem栈顶元素。如果相等，说明当前要出栈的元素就是当前栈中的最小元素，那么同时将_min栈顶元素也出栈。
最后，无论什么情况，都将_elem栈顶元素出栈。

top()函数：
这个函数很简单，直接返回_elem栈的栈顶元素，用于获取当前栈顶的元素值。

getMin()函数：
返回_min栈的栈顶元素，由于_min栈始终保持着最小元素在栈顶，所以这个函数可以快速获取当前栈中的最小元素。

🧡栈的弹出压入序列

在这里插入图片描述

class Solution {
public:bool IsPopOrder(vector<int> pushV, vector<int> popV) {//入栈和出栈的元素个数必须相同if (pushV.size() != popV.size())return false;// 用s来模拟入栈与出栈的过程int outIdx = 0;int inIdx = 0;stack<int> s;while (outIdx < popV.size()){// 如果s是空，或者栈顶元素与出栈的元素不相等，就入栈while (s.empty() || s.top() != popV[outIdx]){if (inIdx < pushV.size())s.push(pushV[inIdx++]);elsereturn false;} /	/ 栈顶元素与出栈的元素相等，出栈s.pop();outIdx++;} return true;}
};

一、整体功能
这段 C++ 代码的目的是判断给定的两个整数向量pushV和popV是否可能是一个栈的入栈和出栈序列。

二、函数分析
首先检查两个输入向量的大小是否相等，如果不相等则直接返回false，因为入栈和出栈的元素个数必须相同。

然后使用一个while循环来模拟入栈和出栈的过程：

  1. 内部又有一个while循环，当栈s为空或者栈顶元素与当前要出栈的元素（popV[outIdx]）不相等时，进行入栈操作。
  2. 只要入栈索引inIdx小于pushV的大小，就将pushV[inIdx]入栈，并将inIdx递增。
  3. 如果入栈索引已经超出pushV的范围，说明无法再进行入栈操作但仍然没有找到与出栈序列匹配的元素，此时返回false。
  4. 当栈顶元素与当前要出栈的元素相等时，将栈顶元素出栈，并将出栈索引outIdx递增。
    如果整个循环顺利执行完毕，说明输入的两个序列可能是一个栈的入栈和出栈序列，返回true。

💛stack的模拟实现

从栈的接口中可以看出，栈实际是一种特殊的vector，因此使用vector完全可以模拟实现stack。

#include<vector>
namespace bite
{template<class T>class stack{public:stack() {}void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_back(); }T& top() { return _c.back(); }const T& top()const { return _c.back(); }size_t size()const { return _c.size(); }bool empty()const { return _c.empty(); }private:std::vector<T> _c;};
}

🏳️‍🌈2.queue的介绍和使用

  1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。

  2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供-组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。

  3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

  • empty:检测队列是否为空
  • size:返回队列中有效元素的个数
  • front:返回队头元素的引用
  • back:返回队尾元素的引用
  • push back:在队列尾部入队列
  • pop front:在队列头部出队列

4.标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。
在这里插入图片描述
在这里插入图片描述

❤️用队列实现栈

在这里插入图片描述

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}
//销毁
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}// 队尾插入
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc newnode fail");}newnode->val = x;newnode->next = NULL;if (pq->ptail == NULL){pq->phead = newnode;pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;}
// 队头删除
void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);if (pq->size == 1){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}// 取队头和队尾的数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}elseQueuePush(&obj->q2,x);
}int myStackPop(MyStack* obj) {Queue* empty = &obj->q1;Queue* notempty = &obj->q2;if(!QueueEmpty(&obj->q1)){empty = &obj->q2;notempty = &obj->q1;}while(QueueSize(notempty) > 1){QueuePush(empty, QueueFront(notempty));QueuePop(notempty);}int top = QueueFront(notempty);QueuePop(notempty);return top;
}int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {return (QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2));
}void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

🧡queue的模拟实现

因为queue的接口中存在头删和尾插，因此使用vector来封装效率太低，故可以借助list来模拟实
现queue，具体如下:

#include <list>
namespace bite
{template<class T>class queue{public:queue() {}void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_front(); }T& back() { return _c.back(); }const T& back()const { return _c.back(); }T& front() { return _c.front(); }const T& front()const { return _c.front(); }size_t size()const { return _c.size(); }bool empty()const { return _c.empty(); }private:std::list<T> _c;};
}

👥总结

本篇博文对 stack和queue 做了一个较为详细的介绍，不知道对你有没有帮助呢

觉得博主写得还不错的三连支持下吧！会继续努力的~

请添加图片描述


http://www.ppmy.cn/embedded/98131.html

相关文章

vue3中引入插件报ts报错Could not find a declaration file for module

vue3中引入插件报ts报错Could not find a declaration file for module

引入第三方组件时&#xff0c;下载了组件还是报ts错误Could not find a declaration file for module 解决办法 1. 下载这个插件的ts库&#xff08;有的没有ts库就用下面这种方式&#xff09; 2. 在src下创建一个shims-vue.d.ts文件&#xff08;简单直接&#xff0c;我用的这种…
阅读更多...
密码学之AES算法

密码学之AES算法

文章目录 1. AES简介1.1 AES算法的历史背景1.2 AES算法的应用领域 2. AES加解密流程图2. AES算法原理2.1 AES加密过程2.2 AES解密过程 1. AES简介 1.1 AES算法的历史背景 AES算法&#xff0c;全称为Advanced Encryption Standard&#xff08;高级加密标准&#xff09;&#x…
阅读更多...
【开源分享】CommLite 跨平台文本UI串口调试助手

【开源分享】CommLite 跨平台文本UI串口调试助手

文章目录 1. 简介2. 编译3. 使用4. 借鉴&思考参考 1. 简介 CommLite是一款基于CSerialPort的文本UI串口调试助手。 gitee仓库 2. 编译 编译非常简单&#xff0c;按照文档操作即可&#xff1a; $ git clone --depth1 https://github.com/itas109/CommLite.git $ cd Comm…
阅读更多...
二分查找-69.x的平方根

二分查找-69.x的平方根

题目描述 给你一个非负整数 x &#xff0c;计算并返回 x 的 算术平方根 。 由于返回类型是整数&#xff0c;结果只保留 整数部分 &#xff0c;小数部分将被 舍去 。 注意&#xff1a;不允许使用任何内置指数函数和算符&#xff0c;例如 pow(x, 0.5) 或者 x ** 0.5 。 69. x …
阅读更多...
全球最强AI程序员 “Genie” 横空出世

全球最强AI程序员 “Genie” 横空出世

全球最强AI程序员 “Genie” 横空出世 Genie 是什么Genie not just a copilot那么如何训练一名AI工程师呢Genie启动 World’s best AI Software Engineer. Genie is the best AI software engineer in the world by far - achieving a 30% eval score on the industry standard…
阅读更多...
浅谈JVM

浅谈JVM

JVM&#xff08;Java Virtual Machine&#xff0c;Java虚拟机&#xff09; JVM是Java程序能够跨平台运行的关键所在。 JVM是一个虚拟的计算机&#xff0c;它模拟了真实计算机的各种硬件功能。其主要作用是加载.class字节码文件&#xff0c;并执行其中的指令。 以下是JVM的一…
阅读更多...
【stm32项目】多功能智能家居室内灯光控制系统设计与实现（完整工程资料源码）

【stm32项目】多功能智能家居室内灯光控制系统设计与实现（完整工程资料源码）

多功能智能家居室内灯光控制系统设计与实现 目录&#xff1a; 目录&#xff1a; 前言&#xff1a; 一、项目背景与目标 二、国内外研究现状&#xff1a; 2.1 国内研究现状&#xff1a; 2.2 国外研究现状&#xff1a; 2.3 发展趋势 三、硬件电路设计 3.1 总体概述 3.2 硬件连接总…
阅读更多...
Scrapy入门教程

Scrapy入门教程

Scrapy入门教程&#xff1a;打造高效爬虫的第一步 1. 引言 在当今的网络世界中&#xff0c;信息是无价的资源。而爬虫工具则是获取这些资源的有力武器。Scrapy 是 Python 生态系统中最强大的爬虫框架之一&#xff0c;它不仅功能强大&#xff0c;而且易于扩展&#xff0c;适用…
阅读更多...
最新文章

Copyright @ 2022~2023