【代码随想录】第7章:栈与队列

简介: 【代码随想录】第7章:栈与队列

第7章 栈与队列


queue有push(),pop()头删,back(),front(),empty(),size()


stack有push(),pop()尾删,top(),empty(),size()


两个特殊应用:单调队列,优先级队列


232. 用栈实现队列【简单】



思路:用栈模拟队列,就是两个栈里面的数据倒来倒去


class MyQueue {
private:
    stack<int>  in_stack, out_stack;    //实现两个倒数的函数
    void in2out() {
        while (!in_stack.empty()) {   //in_stack非空
            out_stack.push(in_stack.top());
            in_stack.pop();
        }
    }
    void out2in() {
        while (!out_stack.empty()) {
            in_stack.push(out_stack.top());
            out_stack.pop();
        }
    }
public:
    MyQueue() {}
    void push(int x) {   //入队
        in_stack.push(x);
    }
    int pop() {                   //出队   即删除第一个入栈元素
        in2out();
        int x = out_stack.top();
        out_stack.pop();          //即删除栈底部的数
        out2in();
        return x;
    }
    int peek() {   //返回队列开头元素   即返回第一个入栈元素
        in2out();
        int x = out_stack.top();
        out2in();
        return x;
    }
    bool empty() {  //判断队是否为空
        return in_stack.empty();
    }
};


优化如下:官方版本


少了一些没必要的操作


class MyQueue {
private:
    stack<int> inStack, outStack;
    void in2out() {
        while (!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }
public:
    MyQueue() {}
    void push(int x) {
        inStack.push(x);
    }
    int pop() {
        if (outStack.empty()) {
            in2out();
        }
        int x = outStack.top();
        outStack.pop();
        return x;
    }
    int peek() {
        if (outStack.empty()) {
            in2out();
        }
        return outStack.top();
    }
    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};


225. 用队列实现栈【简单】



想到的方法:


//时间复杂度:删除是O(n),其余是O(1)
//空间复杂度:O(1)
class MyStack {
private:
  queue<int> q_in, q_out;
public:
  MyStack() {}
  void push(int x) {
    q_in.push(x);
  }
  int pop() {
    int temp = -1;
    while (!q_in.empty()) {
      temp = q_in.front();
      q_in.pop();
      if (!q_in.empty()) {
        q_out.push(temp);
      }
    }
    swap(q_in, q_out);
    return temp;
  }
  int top() {
    return q_in.back();
  }
  bool empty() {
    return q_in.empty();
  }
};


官方代码如下:



//时间复杂度:入栈是O(n),其余是O(1)
//空间复杂度:O(n)
class MyStack {
private:
  queue<int> queue1, queue2;
public:
  MyStack() {}
  void push(int x) {
    queue2.push(x);
    while (!queue1.empty()) {
      queue2.push(queue1.front());
      queue1.pop();
    }
    swap(queue1, queue2);   //交换后queue2为空  queue1中倒序
  }
  int pop() {
    int r = queue1.front();
    queue1.pop();
    return r;
  }
  int top() {
    return queue1.front();
  }
  bool empty() {
    return queue1.empty();
  }
};


思路二:使用一个栈


上一个代码的容器优化



class MyStack {
private:
  queue<int> q;
public:
  MyStack() {}
  void push(int x) {              //主要思路是使得队列里面的元素倒序
    int n = q.size();
    q.push(x);
    for (int i = 0; i < n; i++) {
      q.push(q.front());
      q.pop();
    }
  }
  int pop() {
    int r = q.front();
    q.pop();
    return r;
  }
  int top() {
    return q.front();
  }
  bool empty() {
    return q.empty();
  }
};


20. 有效的括号【简单】



思路:单调栈消消乐


时间复杂度:O(n)


空间复杂度:O(n+6);6是哈希表使用的空间;n表示字符串长度


class Solution {
public:
  bool isValid(string s) {
    int n = s.size();      //获取字符串长度
    if (n % 2 == 1) {      //1.字符串长度为奇数肯定错误
      return false;
    }
    stack<char> stk;
    unordered_map<char, char> pairs = {
      {')', '('},
      {']', '['},
      {'}', '{'}
    };   //列表初始化
    for (int i = 0; i < s.size(); ++i) {
      if (s[i] == '(' || s[i] == '[' || s[i] == '{') {  //2.存入左括号
        stk.push(s[i]);
      }
      else {                                            //3.消除右括号
        if (stk.empty() || stk.top() != pairs[s[i]]) {  
          return false;                            //false    空栈  或者 右括号与左括号类型不匹配
        }
        stk.pop();
      }
    }
    return stk.empty();
  }
};


1047. 删除字符串中的所有相邻重复项【简单】



正宗消消乐


注意:不要去写一个stack,string就有,只是用队列和栈的思路做题


class Solution {
public:
  string removeDuplicates(string s) {
    string res;
    for (auto i : s) {
      if (!res.empty() && i == res.back()) {
        res.pop_back();  //尾删
      }
      else {
        res += i;        //尾插
      }
    }
    return res;
  }
};


150. 逆波兰表达式求值【中等】



class Solution {
public:
  int evalRPN(vector<string>& tokens) {
    stack<string> s;
    for (auto i : tokens) {
      if (i == "+" || i == "-" || i == "*" || i == "/") {
        string temp2 = s.top();  s.pop();  int t2 = stoi(temp2);
        string temp1 = s.top();  s.pop();  int t1 = stoi(temp1);
        int res;
        if (i == "+") {
          res = t1 + t2;
        }
        else if (i == "-") {
          res = t1 - t2;
        }
        else if (i == "*") {
          res = t1 * t2;
        }
        else if (i == "/") {
          res = t1 / t2;
        }
        string r = to_string(res);
        s.push(r);
      }
      else{
        s.push(i);
      }
    }
    return stoi(s.top());
  }
};


239. 滑动窗口最大值【困难,单调队列】



思路一:暴力破解


时间复杂度:O(n*k)


时间超时


class Solution {
public:
  //暴力破解
  int find_max(queue<int>q) {
    int q_max = INT_MIN;
    while (!q.empty()) {
      q_max = max(q_max, q.front());
      q.pop();
    }
    return q_max;
  }
  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    queue<int> q;
    vector<int> res;
    //1. 先做成第一个窗口
    for (int i = 0; i < k; i++) {
      q.push(nums[i]);
    }
    res.push_back(find_max(q));
    //2.滑动
    for (int i = k; i < nums.size(); i++) {
      q.push(nums[i]);
      q.pop();
      res.push_back(find_max(q));
    }
    return res;
  }
};


思路二:单调队列


相当于我们需要实现一个队列,这个队列呢,放进去窗口里的元素,然后随着窗口的移动,队列也一进一出,每次移动之后,队列告诉我们里面的最大值是什么。


维护元素单调递减的队列就叫做单调队列


C++中没有直接支持单调队列,需要我们自己来一个单调队列


时间复杂度:O(n)


空间复杂度:O(k)


class Solution {
private:
  class MyQueue { //单调队列(从大到小)
  public:
    deque<int> que; // 使用deque双端数组来实现单调队列
    // 每次弹出的时候,比较当前要弹出的数值是否等于队列出口元素的数值,如果相等则弹出。
    // 同时pop之前判断队列当前是否为空。
    void pop(int value) {
      if (!que.empty() && value == que.front()) {
        que.pop_front();
      }
    }
    // 如果push的数值大于入口元素的数值,那么就将队列后端的数值弹出,直到push的数值小于等于队列入口元素的数值为止。
    // 这样就保持了队列里的数值是单调从大到小的了。
    void push(int value) {
      while (!que.empty() && value > que.back()) {
        que.pop_back();
      }
      que.push_back(value);
    }
    // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。
    int front() {
      return que.front();
    }
  };
public:
  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    MyQueue que;
    vector<int> result;
    for (int i = 0; i < k; i++) {      // 先将前k的元素放进队列
      que.push(nums[i]);
    }
    result.push_back(que.front());     // result 记录前k的元素的最大值
    for (int i = k; i < nums.size(); i++) {
      que.pop(nums[i - k]);          // 滑动窗口移除最前面元素
      que.push(nums[i]);             // 滑动窗口前加入最后面的元素
      result.push_back(que.front()); // 记录对应的最大值
    }
    return result;
  }
};


思路三:优先队列


//优先队列
//时间复杂度:O(nlogn)   大根堆的删除头元素
//空间复杂度:O(n)
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.emplace(nums[i], i);
    }
    vector<int> ans = { q.top().first };
    for (int i = k; i < nums.size(); ++i) {
      q.emplace(nums[i], i);
      while (q.top().second <= i - k) {   //头元素索引不在滑动窗口内
        q.pop();
      }
      ans.push_back(q.top().first);
    }
    return ans;
  }
};


347. 前 K 个高频元素【中等,优先级队列】



思路一:小根堆


涉及到优先级队列priority_queue,学完再来看


// 时间复杂度:O(nlogk)
// 空间复杂度:O(n)
class Solution {
public:
    // 小顶堆
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        //  1. 要统计元素出现频率
        unordered_map<int, int> map; 
        for (auto i : nums) {
            map[i]++;
        }
        // 2. 对频率排序
        // 定义一个小顶堆,大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
        // 3. 用固定大小为k的小顶堆,扫面所有频率的数值
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) { //频率低的排在前面
                pri_que.pop();        //头删
            }
        }
        // 4. 找出前K个高频元素,因为小顶堆先弹出的是最小的,所以倒叙来输出到数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;
    }
};


思路二:自写sort排序;依据对组的second排序


下面写的sort有问题,学完排序再来补充,思路没问题


class Solution {
public:
    bool cmp2(pair<int, int>&a, pair<int, int>&b) {
        return a.second > b.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        //1. 计数
        unordered_map<int, int> map;
        for (auto& v : nums) {
            map[v]++;
        }
        //2. 换容器
        vector<pair<int, int>> values;
        for (auto& kv : map) {
            values.push_back(kv);
        }
        //3.排序
        sort(values.begin(), values.end(), cmp2);
        //4.输出
        vector<int> res;
        for (int i = 0; i < k; i++) {
            res.push_back(values[i].first);
        }
        return res;
    }
};


71. 简化路径【中等】



思路:



时间复杂度:O(n)


空间复杂度:O(n)


class Solution {
public:
  string simplifyPath(string path) {
    vector<string> stk;         //vector模拟栈
    int n = path.size(), i = 0;
    string str = "";            //合成每个路径名
    while (i < n) {
      if (path[i] == '/') {    // 我们不处理/
        ++i;
      }
      else {
        for (i; i < n && path[i] != '/'; ++i) {  //合成文件名
          str += path[i];
        }
        if (str == ".") {                 //当前目录,什么都不做
        }
        else if (str == "..") {           //返回上级目录
          if (!stk.empty()) {
            stk.pop_back();
          }
        }
        else {                            //压入文件名
          stk.push_back(str);
        }
        str = "";                         //str置空
      }
    }
    if (stk.empty()) //栈为空表示仍在根目录
        return "/";
    string ans = "";
    for (auto& s : stk)
      ans += ('/' + s);   //注意补'/'
    return ans;
  }
};
目录
相关文章
|
25天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
24 1
|
12天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
30 5
|
28天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
50 4
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
137 9
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
39 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
初步认识栈和队列
初步认识栈和队列
61 10
|
2月前
数据结构(栈与列队)
数据结构(栈与列队)
22 1