当前位置: 首页 > article >正文

std::stack和std::queue

目录

stack

stack模拟实现

构造函数

push和pop

返回栈顶元素

栈中元素个数及判空

queue

queue模拟实现

构造函数

push和pop

返回头尾元素

返回队列元素个数及判空

补充deque

补充练习

栈的压入和弹出

最小栈问题

逆波兰表达式求值


stack

stack是C++中的一个容器栈,stack要满足LIFO context (last-in first-out),先进后出的原则,先进入的元素后出来,后进入的元素先出来。就好像一个碗,先装进去的饭最后才能吃到,而后装进去的能先吃到。

因为stack要满足先进后出的原则,所以stack没有头插尾插,头删尾删,其只有插入和删除。

stack - C++ Referencehttps://legacy.cplusplus.com/reference/stack/stack/?kw=stackstack实际上并不是容器,而是一个容器适配器,就是stack能直接用其他容器来实现栈的效果,而不需要本身创建一个容器。

stack是容器适配器,那stack使用哪一个容器呢???实际上使用哪一个容器是不固定的,可以使用vector也可以使用list,看用户自己的需求,但没有指定容器的话,默认用deque容器,关于deque容器结尾会进行讲解。能使用不同的容器就意味着需要对stack增加一个模板参数来实现。


stack模拟实现

关于stack的模拟实现是比较简单的,因为stack是容器适配器所以再模拟实现各个功能的时候可直接调用容器中的成员函数来实现。

构造函数

关于构造函数,此处仅实现无参构造。因为stack的成员自定义类型回去调用自定义类型的默认构造,所以此处不需要实现默认构造。

//模拟实现stack
template<class T ,class Container=deque<T>>  //container是容器的模板,默认是deque
class stack
{
public:
	_con()
	{
	}

private:
	Container _con;
};

push和pop

void push(const T& val)
{
	_con.push_back(val);
}
void pop()
{
	_con.pop_back();
}

返回栈顶元素

//非const版本
T& top()
{
	return _con[_con.size()-1];
}
//const版本
const T& top()const
{
	return _con[_con.size() - 1];
}

栈中元素个数及判空

//返回栈中个数
size_t size()
{
	return _con.size();
}
//判断栈是否为空
bool empty()
{
	return _con.empty();
}

queue

queue和stack相同,只是规则不一样,queue队列是FIFO context (first-in first-out),要满足先进先出的原则。


queue模拟实现

构造函数

template<class T, class Container = deque<T>>
class queue
{
public:
	queue()
	{

	}


private:
	Container _con;
};

push和pop

//插入
void push(const T& val)
{
	_con.push_back(val);
}
//删除
void pop()
{
	_con.pop_front();
}

返回头尾元素

//非const类
//返回头部元素
T& front()
{
	return _con[0];
}
//返回尾部元素
T& back()
{
	return _con[_con.size() - 1];
}

//const类
const T& front()const 
{
	return _con[0];
}
//返回尾部元素
const T& back()const
{
	return _con[_con.size() - 1];
}

返回队列元素个数及判空

//返回元素个数
size_t size()
{
	return _con.size();
}
//判空
bool empty()
{
	return _con.empty();
}

补充deque

deque是stack和queue容器适配器的默认容器。deque即有push_back,push_front和pop_back和pop_front,又能对下标解引用,deque相当于list和vector的结合体。

deque的实现是有一个中控指针数组来实现的,这个中控数组存放一个个的指针指向存储数据的数组中去。

指针数组在使用的时候,先使用中间的空间,当头插的时候向前使用空间,当尾插的时候向后使用空间,来实现头插和尾插及删除。

每一个buffer的元素个数是相同的,所以同个计算可以找到指定的下标。

但是因为deque既想要list的下标解引用又要有list的头插尾插的效率导致最后相比原来两者的效率大大降低了。

1)与vector相比deque有头插和头删的高效,但是deque的下标解引用没有vector的纯粹和高效,deque要计算访问的元素在哪一个buffer,在这个buffer的哪一个位置,而vector连续空间直接访问;

2)与list相比,deque有list无法实现的下标解引用[ ],也有list的头插和尾插,但是deque的中间位置插入删除效率取极低,因为不能改变buffer长度导致,对中间元素进行处理的时候需要大量移动数据,使得效率降低。

因为则两个原因一般不会直接使用deque作为我们代码编写是的使用容器。而是选择vector或list的一个长处作为容器使用。


补充练习

栈的压入和弹出

栈的压入、弹出序列_牛客题霸_牛客网https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

给定一个序列B判断序列B是否可以由序列A栈弹出。

此题的关键在于模仿栈的压入和弹出情况,通过模拟栈的压入和弹出来判断是否满足情况。

解法:用栈来实现,先让指针指向目标B,再让A依次入栈,如果A的栈顶元素和指针指向B的元素相同A出栈,B指针向后走,如果不同就继续入栈,直到序列中的最后一个元素入栈后出栈,如果最终的栈是空则满足题意。

//栈的压入和弹出
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
    stack<int> ans;
    int pushi = 0;  //用pushi和popi来记录两个顺序表指向的位置
    int popi = 0;
    while (pushi < pushV.size())
    {
        //让第一个元素入栈
        ans.push(pushV[pushi]);
        ++pushi;

        //判断是否出栈之前要保证栈不为空
        while (!ans.empty() && ans.top() == popV[popi]) 
        {
            ans.pop();
            ++popi;
        }
    }
    return ans.empty();  //如果栈为空则满足题意
}

最小栈问题

155. 最小栈 - 力扣(LeetCode)https://leetcode.cn/problems/min-stack/submissions/606067751/

 设置一个类MinStack要求其能返回堆栈中最小的元素。注意:此题要求在参数时间类返回最小元素,即getMin()的时间复杂度是O(1)。

此题要求在参数时间内返回最小的元素,则用一个栈是行不通的。

思考:能否用一个变量来保存栈中的最小元素???

实际上是不行的,因为当最小元素被pop后,再调用getMin()函数的时候怎么办??所以不仅仅保留最小的元素,还需要保留倒数第二个,倒数第三个....

解法:创建一个额外的栈来专门存放“最小”元素,将第一个压入栈的元素作为最小元素,当后面一个元素比他小或等于的时候才入栈,比他打的时候就不入栈,这样就能保证这个栈顶始终存放的是最小值,当原栈中的最小值被pop时,额外栈才pop。

class MinStack {
public:
    MinStack() {
    }  //类的成员都是自定义类型所以这里不需要写构造函数

    void push(int val) {
        origin.push(val);
        if (min.empty()||val<=min.top()) //如果栈min是空或者val小于等于最小元素就入栈
        {
            min.push(val);
        }
    }
    void pop() {
        //如果要pop的元素就是最小元素就需要对min栈pop
        if (!min.empty() && min.top() == origin.top())
        {
            min.pop();
        }
        origin.pop();
    }

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

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

private:
    stack<int> origin;  //用来储存原有栈的元素
    stack<int> min;     //储存最小元素
};

逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣(LeetCode)150. 逆波兰表达式求值 - 给你一个字符串数组 tokens ,表示一个根据 逆波兰表示法 [https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437] 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。注意: * 有效的算符为 '+'、'-'、'*' 和 '/' 。 * 每个操作数(运算对象)都可以是一个整数或者另一个表达式。 * 两个整数之间的除法总是 向零截断 。 * 表达式中不含除零运算。 * 输入是一个根据逆波兰表示法表示的算术表达式。 * 答案及所有中间计算结果可以用 32 位 整数表示。 示例 1:输入:tokens = ["2","1","+","3","*"]输出:9解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9示例 2:输入:tokens = ["4","13","5","/","+"]输出:6解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6示例 3:输入:tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]输出:22解释:该算式转化为常见的中缀算术表达式为: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5= ((10 * (6 / (12 * -11))) + 17) + 5= ((10 * (6 / -132)) + 17) + 5= ((10 * 0) + 17) + 5= (0 + 17) + 5= 17 + 5= 22 提示: * 1 <= tokens.length <= 104 * tokens[i] 是一个算符("+"、"-"、"*" 或 "/"),或是在范围 [-200, 200] 内的一个整数 逆波兰表达式:逆波兰表达式是一种后缀表达式,所谓后缀就是指算符写在后面。 * 平常使用的算式则是一种中缀表达式,如 ( 1 + 2 ) * ( 3 + 4 ) 。 * 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。逆波兰表达式主要有以下两个优点: * 去掉括号后表达式无歧义,上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。 * 适合用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中https://leetcode.cn/problems/evaluate-reverse-polish-notation/

通常情况下一个表达式:2+1*3;

其中缀表达式是:2   +   1     *    3

后缀表达书是:    2   1   +    3    *

中缀表达式不用说就是一个整式的正常顺序,那莫后缀表达式是什么呢???

后缀表达式是中缀表达式将其操作数不变,将其操作符按照优先级顺序进行重排。

后缀表达式的计算方法:按照上面显示的当遇到操作符的时候,将其前两个数字按在当前操作符进行运算,结果放回。

解法:将数字依次入栈,当遇到操作符时停止入栈,取出操作符进行运算,将运算结果再入栈。

//逆波兰表达式求值
class Solution {
public:

    void sum(stack<int>& num, char c)
    {
        //取出栈顶两个元素求和,将结果再入栈
        int a = num.top();  //右操作数
        num.pop();
        int b = num.top();  //左操作数
        num.pop();

        switch (c)
        {
        case '+':
            num.push(b + a);
            break;
        case '-':
            num.push(b - a);
            break;
        case '*':
            num.push(b * a);
            break;
        case '/':
            num.push(b / a);
            break;
        }
    }

    int evalRPN(vector<string>& tokens) {
        stack<int> num;
        int i = 0;
        while (i < tokens.size())
        {
            //判断是不是操作符
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")
            {
                sum(num, tokens[i][0]); //用tokens[i][0]来传运算符,传过去字符
                ++i;
            }
            else
            {
                //是数字就入栈
                num.push(stoi(tokens[i]));  //此处使用stoi将字符串转化为数字
                ++i;
            }
        }
        //返回栈顶元素
        return num.top();
    }
};

补充:怎么将中缀表达式转化为后缀表达式呢????

在将中缀表达式转化为后缀表达式的时候我们需要考虑运算符的优先级问题。数字还是依次插入,当出现运算符的时候是否插入要看前两个数是不是先计算,eg:2+8*6:插入2 8之后是否插入+,可以看到这里是不会插入的,因为要想计算8*6,因此时2  8  6  *  +。


http://www.kler.cn/a/585808.html

相关文章:

  • iOS OC匹配多个文字修改颜色和字号
  • Language Models are Few-Shot Learners,GPT-3详细讲解
  • 【最后203篇系列】014 AI机器人-2
  • E2PRAM
  • 二叉树的所有路径
  • Python 与 JavaScript 交互及 Web 逆向分析全解析
  • 手机遥控开关技术解析与应用指南
  • C 语言分支与循环:构建程序逻辑的基石
  • 字符串哈希
  • 【硬件测试】基于FPGA的16PSK+帧同步系统开发与硬件片内测试,包含高斯信道,误码统计,可设置SNR
  • 数学建模之数学模型-3:动态规划
  • C# 集合
  • 卷积神经网络(CNN)之 EfficientNet
  • 【RTSP】客户端(三) 音频相关
  • 计算机视觉算法实战——花卉识别(主页有源码)
  • Spring框架详解(IOC容器-上)
  • JVM 如何保证 Java 程序的安全性?
  • TypeScript 高级类型 vs JavaScript:用“杂交水稻”理解类型编程
  • 【redis】set 类型:基本命令
  • 遥感数据获取、处理、分析到模型搭建全流程学习!DeepSeek、Python、OpenCV驱动空天地遥感数据分析