栈与队列

算法

字数统计: 2k阅读时长: 8 min

 2024/03/06 

Leetcode代码随想录栈与队列专题

[225] 用队列实现栈

题目

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

代码

栈是先进后出，队列先进先出。也就是要把队列最尾巴的元素出队，因此需要把队列前面的所有元素出队然后重新放到队列的后面。所以只需要一个队列即可。

class MyStack {
private:
  queue<int> q;
public:
  MyStack() {

  }
  
  void push(int x) {
    q.push(x);
  }
  
  int pop() {
    int n = q.size();
    while (--n) {
      q.push(q.front());
      q.pop();
    }
    int res = q.front();
    q.pop();
    return res;
  }
  
  int top() {
    // 返回队尾元素
    return q.back();
  }
  
  bool empty() {
    return q.empty();
  }
};

[232] 用栈实现队列

题目

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

代码

push就正常push；pop的话用另外一个栈来接第一个栈的元素，倒一遍就改变了元素的顺序。

class MyQueue {
public:
  stack<int> stIn;
  stack<int> stOut;
  MyQueue() {

  }

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

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

  int peek() {
    int res = pop();
    stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去
    return res;
  }

  bool empty() {
    return stIn.empty() && stOut.empty();
  }
};

[20] 有效的括号

题目

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

代码

设置一个哈希表，左括号作为value，右括号作为key。每次遇到左括号就把左括号入栈，并计数。若遇到右括号，判断其和目前栈顶元素是否相同（当然如果栈为空就直接返回false即可，说明右括号多了），如果相同就弹出并且计数器减1，不同的话就说明没匹配上直接返回false。

最后还要判断一下计数器num是否为0，不为0就说明左括号多了。

class Solution {
public:
  bool isValid(string s) {
    int num = 0;
    stack<char> stk;
    unordered_map<char, char> mp;
    mp[')'] = '(', mp['}'] = '{', mp[']'] = '[';

    for (int i = 0; i < s.size(); i++) {
      if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
        stk.push(s[i]);
        num++;
      } else {
        if (stk.empty())  return false;
        if (mp[s[i]] == stk.top()) {
          stk.pop();
          num--;
        } else {
          return false;
        }
      }
    }
    return num? false: true;
  }
};

[1047] 删除字符串中的所有相邻重复项

题目

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

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

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

代码

class Solution {
public:
  string removeDuplicates(string s) {
    stack<char> st;
    for (int i = 0; i < s.size(); i++) {
      if (st.empty() || s[i] != st.top()) {
        st.push(s[i]);
      } else {
        st.pop();
      }
    }
    string ans;
    while (!st.empty()) {
      ans.push_back(st.top());
      st.pop();
    }
    reverse(ans.begin(), ans.end());
    return ans;
  }
};

[150] 逆波兰表达式求值

题目

给你一个字符串数组 tokens ，表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 '+'、'-'、'*' 和 '/' 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

代码

模拟即可。

class Solution {
public:
  int compute(int a, int b, string c) {
    if (c == "-") return b - a;
    else if (c == "+") return a + b;
    else if (c == "/") return b / a;
    else return a * b;
  }
  int evalRPN(vector<string>& tokens) {
    if (tokens.size() == 1)
      return stoi(tokens[0]);
    stack<int> st;
    int ans;
    for (int i = 0; i < tokens.size(); i++) {
      if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "/" || tokens[i] == "*") {
        int a = st.top(); st.pop();
        int b = st.top(); st.pop();
        ans = compute(a, b, tokens[i]);
        st.push(ans);
      } else {
        st.push(stoi(tokens[i]));
      }
    }
    return ans;
  }
};

[239] 滑动窗口最大值

题目

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

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

代码

对于「最大值」，一种非常合适的数据结构那就是优先队列（堆），其中的大根堆可以帮助我们实时维护一系列元素中的最大值。

对于本题而言，初始时，将数组 $nums$ 的前 $k$ 个元素放入优先队列中。每当我们向右移动窗口时，我们就可以把一个新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中，在这种情况下，这个值在数组 $nums$ 中的位置出现在滑动窗口左边界的左侧。

因此，当后续继续向右移动窗口时，这个值就永远不可能出现在滑动窗口中了，我们可以将其永久地从优先队列中移除。

不断地移除堆顶的元素，直到其确实出现在滑动窗口中。此时，堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系，我们可以在优先队列中存储二元组 $(num,index)$，表示元素 $num$ 在数组中的下标为 $index$。

class Solution {
public:
  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    priority_queue<pair<int, int>> q;
    for (int i = 0; i < k; i++)
      q.push(pair(nums[i], i));
    vector<int> ans = {q.top().first};
    for (int i = k; i < nums.size(); i++) {
      q.push(pair(nums[i], i));
      // 去除不在滑动窗口之内的元素，假设窗口最左边位置是x
      // 目前是i，i-x+1=k，x=i+1-k，x<i+1-k，因此x<=i-k
      while (q.top().second <= i - k)	q.pop();
      ans.push_back(q.top().first);
    }
    return ans;
  }
};

[347] 前K个高频元素

题目

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

代码

先用哈希表统计每个数组出现的频率，然后以出现的<次数, 数字>对的形式存放在优先队列里。最后输出优先队列的前k个元素即可。

class Solution {
public:
  vector<int> topKFrequent(vector<int>& nums, int k) {
    priority_queue<pair<int, int>> q;
    unordered_map<int, int> mp;
    for (int i = 0; i < nums.size(); i++)	mp[nums[i]]++;
    for (auto it = mp.begin(); it != mp.end(); it++) {
      q.push(pair(it->second, it->first));  // 次数+数字
    }
    vector<int> ans;
    cout << q.size() << endl;
    for (int i = 0; i < k; i++) {
      ans.push_back(q.top().second);  // 数字
      q.pop();
    }
    return ans;
  }
};

Next Post

动态规划股票买卖问题
Previous Post

双指针