数据结构——栈：基础-创新互联

前言

在之前的学习中，小荔枝没有系统的学过数据结构噢，所以自己感觉还是欠缺了很多。如果想要走远点而不是浮于表面，学好数据结构和算法真的很重要呐。从今天开始，小荔枝要开始学习和整理算法知识了，打算整理后写一个系列的文章当我的学习笔记了，有需要的小伙伴自取噢~~~

创新互联公司网络公司拥有十载的成都网站开发建设经验，1000多家客户的共同信赖。提供成都网站设计、成都做网站、网站开发、网站定制、买友情链接、建网站、网站搭建、成都响应式网站建设公司、网页设计师打造企业风格，提供周到的售前咨询和贴心的售后服务

目录

前言

一、栈(stack)是什么？

二、C++对栈的定义和使用方法

2.1 引入头文件：

2.2 stack容器适配器的创建 

2.3 stack容器适配器支持的成员函数

三、用栈处理的题目

3.1 有效括号序列

3.2 栈模板 

总结

一、栈(stack)是什么？

栈作为一种数据结构，规定只能在一端执行插入和弹出的操作，它是一种只能在一端进行插入和删除操作的特殊线性表，这一端通常被称为栈顶，另一端被称为栈底，遵循“先入后出”的原则进行存储。通俗一点地去理解“先入后出”：其实栈就相当于一个竹筒，一端封底，另一端开口。当你需要插入或者取出某个元素时，就像是在竹筒中加水，你只能从竹筒顶端往里面注水、从竹筒的顶端往外倒水。而先进去的水往往最后出来(这里先忽略流动性嘛)，这就是“先入后出”。 

二、C++对栈的定义和使用方法 2.1 引入头文件：
#include
2.2 stack容器适配器的创建 
  • 创建一个不包含任何元素的 stack 适配器，并采用默认的 deque 基础容器：
std::stack values;
  • 可以通过指定第二个模板类型参数，使用除 deque 容器外的其它序列式容器。通常情况下stack容器适配器可以适配vector、deque和list这三个容器。
std::stack>values;
  • 可以用一个基础容器来初始化 stack 适配器，只要该容器的类型和 stack 底层使用的基础容器类型相同即可
std::listvalues {1, 2, 3};
std::stack>my_stack (values);
  • 还可以用一个 stack 适配器来初始化另一个 stack 适配器，只要它们存储的元素类型以及底层采用的基础容器类型相同即可。
std::listvalues{ 1, 2, 3 };
std::stack>my_stack1(values);
std::stack>my_stack=my_stack1;
//std::stack>my_stack(my_stack1);
2.3 stack容器适配器支持的成员函数

三、用栈处理的题目 3.1 有效括号序列

题目描述：

给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。

解题思路：

遍历字符串，将字符串中的‘(’、‘[’、'{'进行入栈操作，当遇到‘)’、‘]’、‘}’的时候检查栈是否为空或者栈定元素是否匹配，如果是就返回true；不是就返回false。

核心代码：

bool isValid(string s) {
        // write code here
        stackstk;
        for(int i=0;i

在这里你会发现有些实例跑不过，其实这里是因为‘||’这个运算符只有在左边条件为false的时候才会判断右边的条件的正确与失误。

所以代码应该改一下：

bool isValid(string s) {
        // write code here
        stackstk;
        for(int i=0;i

这里还有另一个思路：其实可以将右括号进行入栈的操作，代码会相对比较简洁一点。

bool isValid(string s) {
        // write code here
        stackstk;
        for(int i=0;i
3.2 栈模板 

题目描述：

描述

请你实现一个栈。

操作：

push x：将 加x\x 入栈，保证 x\x 为 int 型整数。

pop：输出栈顶，并让栈顶出栈

top：输出栈顶，栈顶不出栈

输入描述：

第一行为一个正整数 n\n ，代表操作次数。(1 \leq n \leq 100000)(1≤n≤100000)

接下来的 n\n ，每行为一个字符串，代表一个操作。保证操作是题目描述中三种中的一种。

输出描述：

如果操作为push，则不输出任何东西。

如果为另外两种，若栈为空，则输出 "error“

否则按对应操作输出。

示例1

输入：

6
push 1
pop
top
push 2
push 3
pop

输出：

1
error
3

利用C++的数组或者是vector容器来实现栈的操作,我这里给出的是使用vector容器来写的思路：

#include#includeusing namespace std;

class M_stack{
    private:
        vectors;
        vector::reverse_iterator i;
        
    public:
        void push(int x){
            s.push_back(x);
            
        }
        void pop(){
            i=s.rbegin();
            if(s.size()>0){
                cout<<*i<0){
                i = s.rbegin();
                cout<<*i<>n;
    for(int i=0;i>order;
        if(order=="push"){
            int inputs;
            cin>>inputs;
            s.push(inputs);
        }else if(order=="pop"){
            s.pop();
        }else if(order=="top"){
            s.top();
        }
    }
    return 0;
}
总结

在这篇文章中，小荔枝主要是整理了C++STL库中有关栈的操作，同时小荔枝也给出了栈的个人理解和用vector向量容器写的一个栈，总之其实栈并不难，学会灵活运用才是最重要的哈哈哈。这篇文章我其实拖了一个多月才腾出手写个结尾，夜深咯，该休息啦，明天再努力哈哈哈。

今朝已然成为过去，明日依然向往未来！我是小荔枝，在技术成长的路上与你相伴，码文不易，麻烦举起小爪爪点个赞吧哈哈哈。

谢谢大家的支持嘻嘻嘻~~~ 

比心心♥~~~

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享标题：数据结构——栈：基础-创新互联
标题路径：https://www.cdcxhl.com/article38/iocpp.html

成都网站建设公司_创新互联，为您提供网站改版、网站营销、网站制作、电子商务、建站公司、App开发

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

营销型网站建设

响应式网站知识

分类信息网