跳到主要内容

栈与队列

232. 用栈实现队列​

使用栈实现队列的下列操作：

  • push(x) -- 将一个元素放入队列的尾部。
  • pop() -- 从队列首部移除元素。
  • peek() -- 返回队列首部的元素。
  • empty() -- 返回队列是否为空。
class MyQueue {
public:
    MyQueue() {

    }

    void push(int x) {
        in_stack.push(x);
    }

    int pop() {
        if (out_stack.empty()) {
            while (!in_stack.empty()) {
                out_stack.push(in_stack.top());
                in_stack.pop();
            }
        }
        int result = out_stack.top();
        out_stack.pop();
        return result;
    }

    int peek() {
        int result = this->pop();
        out_stack.push(result);
        return result;
    }

    bool empty() {
        return in_stack.empty() && out_stack.empty();
    }

private:
    stack<int> in_stack;
    stack<int> out_stack;
};

/**
 * 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();
 */

225. 用队列实现栈​

力扣题目链接(opens new window)

使用队列实现栈的下列操作：

  • push(x) -- 元素 x 入栈
  • pop() -- 移除栈顶元素
  • top() -- 获取栈顶元素
  • empty() -- 返回栈是否为空
class MyStack {
public:
    MyStack() {

    }

    void push(int x) {
        q.push(x);
    }

    int pop() {
        int size = q.size();
        while (size > 1) {
            q.push(q.front());
            q.pop();
            size--;
        }

        int result = q.front();
        q.pop();
        return result;
    }

    int top() {
        return q.back();
    }

    bool empty() {
        return q.empty();
    }

private:
    queue<int> q;
};

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

20. 有效的括号​

力扣题目链接(opens new window)

给定一个只包括 '('，')'，'{'，'}'，'['，']'  的字符串，判断字符串是否有效。

有效字符串需满足：

  • 左括号必须用相同类型的右括号闭合。
  • 左括号必须以正确的顺序闭合。
  • 注意空字符串可被认为是有效字符串。
class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) {
            return false;
        }
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                st.push(')');
            } else if (s[i] == '{') {
                st.push('}');
            } else if (s[i] == '[') {
                st.push(']');
            } else if (st.empty() || st.top() != s[i]) {
                return false;
            } else {
                st.pop();
            }
        }
        return st.empty();
    }
};

1047. 删除字符串中的所有相邻重复项​

力扣题目链接(opens new window)

给出由小写字母组成的字符串  S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

class Solution {
public:
    string removeDuplicates(string s) {
        string result;
        for (char c : s) {
            if (result.empty() || result.back() != c) {
                result.push_back(c);
            }  else {
                result.pop_back();
            }
        }
        return result;
    }
};

150. 逆波兰表达式求值​

力扣题目链接(opens new window)

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

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

说明：

整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

Reverse Polish Expression

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long> st;
        for (string s : tokens) {
            if (s == "+" || s == "-" || s == "*" || s == "/") {
                long long n2 = st.top();
                st.pop();
                long long n1 = st.top();
                st.pop();
                if (s == "+") {
                    st.push(n1 + n2);
                } else if (s == "-") {
                    st.push(n1 - n2);
                } else if (s == "*") {
                    st.push(n1 * n2);
                } else if (s == "/") {
                    st.push(n1 / n2);
                }
            } else {
                st.push(stoll(s));
            }
        }

        return st.top();
    }
};

239. 滑动窗口最大值​

力扣题目链接(opens new window)

给定一个数组 nums，有一个大小为  k  的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k  个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for (int i = 0; i < k; i++) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
        }

        vector<int> ans = {nums[q.front()]};
        for (int i = k; i < n; i++) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            while (q.front() <= i - k) {
                q.pop_front();
            }
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

347. 前 K 个高频元素​

力扣题目链接(opens new window)

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        auto comp = [](const pair<int, int> & a, const pair<int, int> & b){
            return a.second > b.second;
        };
        unordered_map<int, int> counts;
        for (int num : nums) {
            counts[num]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> pri_que(comp);

        for (auto count : counts) {
            pri_que.push(count);
            if (pri_que.size() > k) {
                pri_que.pop();
            }
        }

        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};