Stack

stack文档介绍

1. stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作,
2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出,
3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作

• empty：判空操作
• back：获取尾部元素操作
• push_back：尾部插入元素操作
• pop_back：尾部删除元素操作

4.标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque,

stack容器的定义方式:

方式1：使用默认的容器适配器定义 -> 注意:stack的默认容器适配器是deque双端队列

stack<int> st;

方式2：使用特定的容器适配器定义

stack<char, list<char>> st2;//使用list作为容器适配器
stack<int, vector<int>> st3;//使用vector作为容器适配器

接口函数

实例：

int main()
{
	stack<int> st;
	st.push(1);
	st.push(2);
	st.push(3);
	st.push(4);
	st.pop();
	while (!st.empty())
	{
		cout << st.top() << " ";//3 2 1
		st.pop();
	}
	cout << endl;
	return 0;
}

queue

queue文档介绍

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

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

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

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

4. 标准容器类deque和list满足了这些要求,默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque,

queue容器的定义方式

方式1：使用默认的容器适配器定义 -> 注意:queue的默认容器适配器是deque双端队列

queue<int> q1;

方式2：使用特定的容器适配器定义

queue<int, vector<int>> q2;//err 不可以使用vector作为queue的容器适配器
queue<int, list<int>> q3;

接口函数

实例

int main()
{
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.pop();
    cout << q.size() << endl;//2
    q.push(1);
    while (!q.empty())
    {
        cout << q.front() << " ";//2 3 1
        q.pop();
    }
    return 0;
}

栈OJ题目

最小栈

155. 最小栈 - 力扣（LeetCode） (leetcode-cn.com)

不可取方法:用一个变量记录当前最小值

正确方法：使用两个栈,一个栈存储数据,一个辅助栈存储当前的最小值

• 如果当前入栈的值 比 辅助栈的栈顶元素小 || 辅助栈为空
  • 压入当前入栈的值 否则：重复压入当前辅助栈的栈顶元素
• 获取最小值:即获取当前辅助栈的栈顶元素

class MinStack {
public:
    //构造函数和析构函数都不需要我们自己写,因为成员变量stack是自定义类型,会调用它自己的默认构造函数初始化
    MinStack() {
    }
    
    void push(int val) {
        stackPush.push(val);
        //最小栈为空 || 最小栈的栈顶元素>当前入栈数 
        if( stackMin.empty() || stackMin.top() > val)
        {
            stackMin.push(val);//压入当前数
        }
        else
        {
            stackMin.push(stackMin.top());//重复压入最小栈的栈顶元素
        }
    }
    
    void pop() {
        //两个栈都要出栈顶元素
        stackPush.pop();
        stackMin.pop();
    }
    
    int top() {
       return  stackPush.top();
    }
    
    int getMin() {
        return stackMin.top();
    }

    stack<int> stackPush;
    stack<int> stackMin;
}；

优化:不存储大量重复值,

• 压入栈的时候:如果最小栈为空 || 当前压入元素 <=最小栈的栈顶元素

  • 才压入当前元素 (注意:等于的时候也要压入) 其它情况不压入

• 弹出的时候: 如果此时数据栈pop的值和最小栈栈顶的值一样 ->弹出最小栈的栈顶元素

class MinStack {
public:
    //构造函数和析构函数都不需要我们自己写,因为成员变量stack是自定义类型,会调用它自己的默认构造函数初始化
    MinStack() {
    }
    
    void push(int val) {
        stackPush.push(val);
        //最小栈为空 || 当前压入元素<=最小栈的栈顶元素
        if( stackMin.empty() || stackMin.top()>= val)
        {
            stackMin.push(val);
        }
    }
    
    void pop() {
        //数据栈pop的值和最小栈栈顶的值一样
        if(stackPush.top() == stackMin.top())
        {
            stackMin.pop();
        }
        stackPush.pop();
    }
    
    int top() {
       return  stackPush.top();
    }
    
    int getMin() {
        return stackMin.top();
    }

    stack<int> stackPush;
    stack<int> stackMin;
};

栈的压入,弹出序列

栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

使用栈的入栈和出栈来模拟这个出栈顺序,如果能模拟出来,就说明是合法的,否则就是非法的!

方法：

• 1.先把push数组中的值进栈
• 2.pop数组的值依次和栈里面的数据比较
  • 如果相等,则pop数组往后走,然后出栈顶数据
  • 如果栈顶数据和此时pop数组指向数据不相等 或者 栈为空–>重复第一步
    • 注意此时用的是&&结构,只要有一个不满足就重复第一步
• 循环结束条件: push数组走完了
• 是否匹配:
  • 如果pop数组也走完了 -> 匹配
  • 如果pop数组没有走完 ->不匹配

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        stack<int> st;
        int i =0;
        int j = 0;
        //循环结束条件: push数组走完了 
        while(i<pushV.size())
        {
            st.push(pushV[i]);//先把push数组中的值进栈
            ++i;
            //如果数据不相等&&栈为空-->第一步
            while(!st.empty() &&st.top()==popV[j])
            {
                j++;
                st.pop();
            }
        }
        //是否匹配
        return j == popV.size();
    }
};

写法2:

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV)
    {
        //先做特殊性判定
        if(pushV.empty() || popV.empty() || popV.size() != pushV.size())
        {
            return false;
        }
        //遍历入栈序列
        stack<int> st;
        int j = 0;
        for(int i = 0;i<pushV.size();i++)
        {
            st.push(pushV[i]);//把当前入栈序列元素入栈
            //模拟栈的入栈和出栈序列
            //如果栈不为空 && 当前栈顶元素==出栈元素,就一直往后比较出栈序列的元素
            //如果该条件不满足,就要一直入栈
            //如果该条件满足,就要一直出栈
            //pushV代表对应的入栈逻辑,popV代表对应的出栈逻辑
            while(!st.empty() && st.top() == popV[j])
            {
                j++;
                st.pop();//去掉栈顶元素,比较下一个元素
            }
        }
        //如果最后栈为空,说明第二个序列是该栈的弹出顺序
        return st.empty();
    }
};

逆波兰表达式求值(后缀表达式)

150. 逆波兰表达式求值 - 力扣（LeetCode） (leetcode-cn.com)

思路:

遍历整个字符串:

1.遇到操作数 ->入栈

2.遇到操作符 ->拿栈顶的两个数据出来运算, 然后把运算结果放到栈中

• 要注意弹出顺序,先拿到的是右操作数,然后才是左操作数 因为栈的特性:先进后出

Bug代码：switch(str)

因为容器tokens存放的是字符串集合, str:字符串 str[0] :字符串的第一个字符

• switch(str[0])->OK char类型也是整形家族的一个成员

做法:

判断每个字符串到底是操作数还是操作符 如果是操作符就拿到两个操作数,然后根据该操作符是什么,进行计算,然后压到栈中

C语言的atoi == C++中的stoi函数 将字符串转为整数 to_string函数:将各种类型转为字符串

class Solution {
public:
    //得到两个操作数  left和right是引用 栈也是引用
    void  getNum(stack<int>&st,int& left,int& right)
    {
        //先出的是右操作数 
        right = st.top();
        st.pop();
        left = st.top();
        st.pop();
    }
    int evalRPN(vector<string>& tokens) {
        stack<int> st;//存放结果
        for(auto& str: tokens)//遍历字符串
        {
            int left,right;
            switch(str[0])
            {
                case '+':
                    getNum(st,left,right);
                    st.push(left+right);
                    break;
                case '-':
                    getNum(st,left,right);
                    st.push(left-right);
                    break; 
                case '*':
                    getNum(st,left,right);
                    st.push(left*right);
                    break; 
                case '/':
                    getNum(st,left,right);
                    st.push(left/right);
                    break; 
                default:
                    st.push(stoi(str)); 
                    break;
            }
        }
        return st.top();
    }
};

不能通过判断字符串的第一个字符是+ - * / 来判断这个是操作数还是操作符, 因为可能存在负数,被误判成操作符

修改：对 -操作符进行特判：到底是操作数还是操作符, 如果此时字符串只有一个字符->说明就是操作符,否则就是操作数

class Solution {
public:
    //得到两个操作数
    void  getNum(stack<int>&st,int& left,int& right)
    {
        right = st.top(); //先出的是右操作数
        st.pop();
        left = st.top();
        st.pop();
    }
    int evalRPN(vector<string>& tokens) {
        stack<int> st;//存放结果
        for(auto& str: tokens)//遍历字符串
        {
            int left,right;
            switch(str[0])
            {
                case '+':
                    getNum(st,left,right);//得到两个操作数
                    st.push(left+right);//把计算结果压到栈中
                    break;
                case '-':
                    //操作符
                    if(str.size() == 1)
                    {
                        getNum(st,left,right);//得到两个操作数
                        st.push(left-right);//把计算结果压到栈中
                        break; 
                    }
                    //操作数
                    else
                    {
                        st.push(stoi(str));//转为整数压到栈中
                        break;
                    }
                case '*':
                    getNum(st,left,right);//得到两个操作数//得到两个操作数
                    st.push(left*right);
                    break; 
                case '/':
                    getNum(st,left,right);//得到两个操作数
                    st.push(left/right);//把计算结果压到栈中
                    break; 
                default: //普通的数字
                    st.push(stoi(str));//转为整数压到栈中
                    break;
            }
        }
        return st.top();//返回栈顶数据就是最后的结果
    }
};

修改办法2:取字符串的最后一个字符判断是操作数还是操作符 string中的back函数获取的就是最后一个字符或者 用size()-1也是最后一个字符

switch(str.back())  //switch(str.size()-1)

中缀表达式->后缀表达式

用两个栈实现队列

232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)

class MyQueue {
public:
    //构造函数和析构函数都不需要我们自己写,因为成员变量stack是自定义类型,会调用它自己的默认构造函数初始化
    MyQueue() {
    }
    
    void push(int x) {
        stackPush.push(x);//只往push栈入数据
    }
    
    int pop() {
        //如果pop栈为空,就把push栈内容导过来
        if(stackPop.empty())
        {
            while(!stackPush.empty())
            {
                stackPop.push(stackPush.top());
                stackPush.pop();
            }
        }

        int tmp = stackPop.top();
        stackPop.pop();
        return tmp;
    }
    
    int peek() {
        //如果pop栈为空,就把push栈内容导过来
        if(stackPop.empty())
        {
            while(!stackPush.empty())
            {
                stackPop.push(stackPush.top());
                stackPush.pop();
            }
        }

        int tmp = stackPop.top();
        return tmp;
    }
    
    bool empty() {
       return  stackPop.empty() && stackPush.empty();
    }
    stack<int> stackPush;// 用于push数据
    stack<int> stackPop;// 用于pop数据
};

队列OJ题

用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode） (leetcode-cn.com)

• 入数据:往不为空的队列入数据

• 出数据:假设一个队列不为空,然后判断该队列是不是真的不为空,否则另一个队列不为空 ,然后把不为空队列的数据导到空队列,直到不为空的队列只剩一个数据,然后pop这个数据

所以不需要进行判空

使用两个队列实现栈

class MyStack {
public:
    //构造函数和析构函数都不需要我们自己写,因为成员变量stack是自定义类型,会调用它自己的默认构造函数初始化
    MyStack() {
    }
    
    void push(int x) {
        //往不为空的队列中入数据
        if(!q1.empty())
        {
            q1.push(x);
        }
        else
        {
            q2.push(x);
        }
    }
    
    int pop() {
        queue<int>* emptyQ = &q1;//emptyQ指向空队列
        queue<int>* noemptyQ = &q2;
        if(!q1.empty())
        {
            swap(emptyQ,noemptyQ);//交换两个指针
        }
        //把不空队列的数据导入到空队列,直到剩一个数据
        while(noemptyQ->size() > 1)
        {
                emptyQ->push(noemptyQ->front());
                noemptyQ->pop();
        }
        //返回不空队列的仅剩一个元素
        int tmp = noemptyQ->front();
        noemptyQ->pop();
        return tmp;
    }
    
    int top() {
        //哪个队列不为空,就返回哪个队列的队尾元素
        if(!q1.empty())
           return  q1.back();
        else
            return q2.back();
    }
    
    bool empty() {
        return q1.empty() && q2.empty();//两个队列都为空才是空
    }
    queue<int> q1;
    queue<int> q2;
};

emptyQ和noemptyQ是队列指针, q1和q2是队列对象

指针->方法 (通过->解引用,调用指针指向对象的方法) 对象.方法 (调用对象的方法) 方法:函数接口

使用一个队列实现栈

相当于围成一个循环圈! –size  : 循环size-1次   size-- : 循环size次

class MyStack {
public:
    MyStack() {
    }
    
    void push(int x) {
        q.push(x);
    }
    
    int pop() {
        int size = q.size();//记录此时的元素个数
        //把前size-1个元素重复压入到队列之后,  一边压一边出数据
        while(--size)
        {
            q.push(q.front());
            q.pop();
        }
        //此时的队头就是要弹出的元素
        int tmp = q.front();
        q.pop();
        return tmp;
    }
    
    int top() {
        return q.back();
    }
    
    bool empty() {
        return q.empty();
    }
    queue<int> q;
};

二叉树的层序遍历I

102. 二叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com)

核心思路：当根节点进入队列时,会把左右孩子都带进队列(有左右孩子时), 当这一层的结点出完了之后,下一层的结点都进队列了

这一层有多少个结点,就循环多少次,就出多少个结点, 每一层的数据都放到一个容器vector中

当循环结束时,把这个vector放到另一个vector中存放,相当于(二维数组), 然后再求下一层有多少个结点,再次进入循环就循环多少次

外层循环结束条件:队列为空

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;//队列存放二叉树结点指针
        int leverSize = 0;//每一层的结点个数
        //如果不是空树
        if(root)
        {
            q.push(root);
            leverSize = 1;//根节点这一层只有一个结点
        }
        vector<vector<int>> vv;//最终返回结果
        //层序遍历的思路
        while(!q.empty())
        {
            vector<int> v;//记录这一层遍历的值
            //这一层右多少个结点,遍历多少次
            for(int i = 0;i<leverSize;i++)
            {
                TreeNode* front = q.front();//得到此时结点
                q.pop();//在队列中弹出此时结点
                v.push_back(front->val);//此时结点的值放到容器
                //如果有左孩子/右孩子就放进队列
                if(front->left)
                {
                    q.push(front->left);
                }
                if(front->right)
                {
                    q.push(front->right);
                }
            }

   			 //for循环结束->上一层结点都出完了->下一层的结点都被带进队列了
            //记录此时下一层有多少个结点->即此时队列的大小
            leverSize = q.size();
            vv.push_back(v);//把这一层的得到的值放到vv中
        }
        return vv;
    }
};

二叉树的层序遍历II

107. 二叉树的层序遍历 II - 力扣（LeetCode） (leetcode-cn.com)

方法和上面的题目一致,只不过是从最后一层存放数据 -> 最后一步把保存节点的容器vv进行逆置即可

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
            queue<TreeNode*> q;
        int leverSize = 0;//每一层的结点个数
        if(root)
        {
            q.push(root);
            leverSize = 1;//根节点这一层只有一个结点
        }
        vector<vector<int>> vv;//最终返回结果
        //层序遍历的思路
        while(!q.empty())
        {
            vector<int> v;//记录这一层遍历的值
            //这一层右多少个结点,遍历多少次
            for(int i = 0;i<leverSize;i++)
            {
                TreeNode* front = q.front();//得到此时结点
                q.pop();//在队列中弹出此时结点
                v.push_back(front->val);//此时结点的值放到容器
                //如果有左孩子/右孩子进队列
                if(front->left)
                {
                    q.push(front->left);
                }
                if(front->right)
                {
                    q.push(front->right);
                }
            }

    //上一层出完了,下一层的结点都被带进队列了,记录下一层有多少个结点->即此时队列的大小
            leverSize = q.size();
            vv.push_back(v);//把这一层的得到的值放到vv中
        }
        reverse(vv.begin(),vv.end());//使用迭代器区间,把vv的内容逆置
        return vv;
    }
};