It has been 1576 days since the last update, the content of the article may be outdated.

简介

栈的特点是后入先出,根据这个特点可以临时保存一些数据,之后用到依次再弹出来,常用于 DFS 深度搜索

队列一般常用于 BFS 广度搜索,类似一层一层的搜索

155. 最小栈

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

辅助栈
cpp
class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> minStack;
    stack<int> dataStack;
    MinStack() {
       minStack.push(INT_MAX);
        
    }
    
    void push(int x) {
        dataStack.push(x);
        minStack.push(min(minStack.top(),x));
    }
    
    void pop() {
        minStack.pop();
        dataStack.pop();
        
        
    }
    
    int top() {
        return dataStack.top();
        
    }
    
    int getMin() {
        return minStack.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

150. 逆波兰表达式求值

根据 逆波兰表示法,求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

思路:通过栈保存原来的元素,遇到表达式弹出运算,再推入结果,重复这个过程

cpp
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        if(tokens.empty())
            return 0;
        stack<int> st;
        for(int i=0;i<tokens.size();i++)
        {
            if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/")
                {
                  
                    if(st.size()<2)
                        return -1;
                    auto b=st.top();
                    st.pop();
                    auto a=st.top();
                    st.pop();
                    int res;
                    switch(tokens[i][0])
                    {
                        case '+':
                            res=a+b;                           
                            break;
                        case '-':
                            res=a-b;
                            break;
                        case '*':
                            res=a*b;
                            break;
                        case '/':
                            res=a/b;
                            break;
                    }
                    st.push(res);
                }
            else
            {
                st.push(atoi(tokens[i].c_str()));

            }
        }
        return st.top();

    }
};

394. 字符串解码

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

cpp
class Solution {
public:
    string decodeString(string s) {
        stack<int> nums;
        stack<string> strs;
        string res="";
        int num=0;
        for(int i=0;i<s.size();i++)
        {
            char ch=s[i];
            if(ch>='0'&&ch<='9')
            {
                //多位数情况处理
                num=num*10+ch-'0';

            }else if((ch >= 'a' && ch <= 'z') ||(ch >= 'A' && ch <= 'Z'))
            {
                res+=ch;

            }
            else if(ch=='[')
            {
                nums.push(num);
                num=0;
                strs.push(res);
                res="";
            }
            else
            {
                int j=nums.top();
                nums.pop();
                while(j--)
                {
                    strs.top()+=res;
                }
                res=strs.top();
                //之后若还是字母,就会直接加到res之后,因为它们是同一级的运算
                //若是左括号,res会被压入strs栈,作为上一层的运算
                strs.pop();
            }
            
        }
        return res;

    }
};

94. 二叉树的中序遍历

cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:   
   
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>ans;
        if(root==NULL)
            return ans;       
        stack<TreeNode*> st;
        auto cur=root;
        while(cur!=NULL||!st.empty())
        {
            while(cur!=NULL)
            {
                st.push(cur);
                cur=cur->left;
            }
            cur=st.top();
            st.pop();
            ans.push_back(cur->val);
            cur=cur->right;

        }
        return ans;
         
       
    }
};

133. 克隆图

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。

图中的每个节点都包含它的值 valint) 和其邻居的列表(list[Node])。

cpp
class Node {
 public int val;
 public List<Node> neighbors;
}
cpp
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;
    
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    unordered_map<Node*,Node*> mp;
    Node* cloneGraph(Node* node) {
        if(node==NULL)
            return node;
        if(mp.count(node))
            return mp[node];
        const auto newnode=new Node(node->val);
        mp[node]=newnode;
        for(auto n:node->neighbors)
        {
            mp[node]->neighbors.push_back(cloneGraph(n));
        }
        return mp[node];
        
    }
};

200. 岛屿数量

给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

cpp
class Solution {
public:
  int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                if(grid[i][j] == '1'){
                    dfs(grid, i, j);
                    count++;
                }
            }
        }

        return count;
   }
   void dfs(vector<vector<char>>& grid, int i, int j){
       if(i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != '1'){
           return;
       }

       grid[i][j] = '2';
       dfs(grid, i + 1, j);
       dfs(grid, i - 1, j);
       dfs(grid, i, j + 1);
       dfs(grid, i, j - 1);
   }
};

84. 柱状图中最大的矩形

队列

232. 用栈实现队列

cpp
class MyQueue {
public:
    stack<int> s1,s2;
    int front;
    /** Initialize your data structure here. */
    MyQueue() {

    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        if(s1.empty())
            front=x;
        s1.push(x);

    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if(s2.empty())
        {
            while(!s1.empty())
            {
                s2.push(s1.top());
                s1.pop();
            }
        }
        int ret =s2.top();
        s2.pop();
        return ret;

    }
    
    /** Get the front element. */
    int peek() {
        if(!s2.empty())
        {
            return s2.top();
        }
        return front;

    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        if(s1.empty()&&s2.empty())
        {
            return true;

        }
        else
        {
            return false;
        }

    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

102. 二叉树的层序遍历

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。

cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root==NULL)
            return res;
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty())
        {
           int currentLevelSize=q.size();
           vector<int> level;
           for(int i=0;i<currentLevelSize;i++)
           {
                auto cur=q.front();
                level.push_back(cur->val);
                q.pop();
                if(cur->left)
                    q.push(cur->left);
                if(cur->right)
                    q.push(cur->right);               
           }
           res.push_back(level);
        }
        return res;
        
    }
};

542. 01 矩阵