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

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

目录

前言

一、栈(stack)是什么？

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

2.1 引入头文件：

2.2 stack容器适配器的创建 

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

三、用栈处理的题目

3.1 有效括号序列

3.2 栈模板 

总结

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

#include

• 创建一个不包含任何元素的 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);

题目描述：

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

解题思路：

遍历字符串，将字符串中的‘(’、‘[’、'{'进行入栈操作，当遇到‘)’、‘]’、‘}’的时候检查栈是否为空或者栈定元素是否匹配，如果是就返回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

#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;
}