Xu-Blog

养一猫一狗，猫叫啵啵，狗叫没想好~~

0%

队列&栈-03

发表于 分类于 阅读次数： Valine：
本文字数： 5.2k 阅读时长 ≈ 5 分钟

栈：后入先出的数据结构

在 LIFO 数据结构中，将首先处理添加到队列中的最新元素。

与队列不同，栈是一个 LIFO 数据结构。通常，插入操作在栈中被称作入栈 push。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop，将始终删除队列中相对于它的最后一个元素。

  • 入栈：在栈顶加入一个元素。
  • 退栈：删除栈顶的元素。

栈-实现

栈的实现比队列容易。动态数组足以实现堆栈结构。以下提供一个简单的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
class MyStack {
  private:
    vector<int> data;   // 创建元素
  public:
    /** 将元素插入堆栈 */
    void push(int x) {
      data.push_back(x);
    }
    /** 查看堆栈是否为空 */
    bool isEmpty() {
      return data.empty();
    }
    /** 获取栈顶元素 */
    int top() {
      return data.back();
    }
    /** 删除栈顶元素，成功返回true */
    bool pop() {
      if (isEmpty()) {
        return false;
      }
      data.pop_back();
      return true;
    }
};
int main() {
    MyStack s;
    s.push(1);
    s.push(2);
    s.push(3);
    for (int i = 0; i < 4; ++i) {
        if (!s.isEmpty()) {
            cout << s.top() << endl;
        }
        cout << (s.pop() ? "true" : "false") << endl;
    }
}

栈-用法

大多流行语言都提供了内置的栈库。所以不必重复造轮子。
除了初始化，我们还需要知道如何使用两个最重要的操作：入栈和退栈。除此之外，还应该能够从栈中获得顶部元素。

下面是代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
int main() {
    // 1. Initialize a stack.
    stack<int> s;
    // 2. Push new element.
    s.push(5);
    s.push(13);
    s.push(8);
    s.push(6);
    // 3. Check if stack is empty.
    if (s.empty()) {
        cout << "Stack is empty!" << endl;
        return 0;
    }
    // 4. Pop an element.
    s.pop();
    // 5. Get the top element.
    cout << "The top element is: " << s.top() << endl;
    // 6. Get the size of the stack.
    cout << "The size is: " << s.size() << endl;
}

当你想首先处理最后一个元素的时候，栈将是最合适的数据操作。

题目：最小栈

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

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

官方思路如下

方法一：使用辅助栈

  • 定义一个[数据栈]来支持 push、pop、top 操作
  • 定义一个[辅助栈]其栈顶为当前最小值，以支持常数时间复杂度的 getMin 操作

代码如下(C++)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MinStack {
  stack<int> dataStack,minStack;   // 定义数据栈和最小栈
public:
  /** initialize your data structure here. */
  MinStack() {
    minStack.push(INT_MAX);
  }
  void push(int x) {
    dataStack.push(x);  // 数据栈推入x
    if(minStack.empty() || x <= minStack.top()){  // 如果最小值栈为空或者数据为最小值，推入
      minStack.push(x);
    }
  }
  void pop() {
    if(!dataStack.empty()){
      if(dataStack.top() == minStack.top()){     // 如果当前值为最小值，则删除最小栈栈顶元素
        minStack.pop();              // 删除最小栈栈顶
      }
      dataStack.pop();               // 删除数据栈栈顶
    }
  }
  int top() {
    return dataStack.top();
  }
  int getMin() {
    return minStack.top();
  }
};

时间复杂度 O(1)，空间复杂度 O(n)。

方法二：使用 Stack<Node> 除了保存当前值外，额外保存当前最小值。

方法三：自定义 Stack，以单链表形式自定义栈。

题目：有效的括号

这个题是我觉得比较简单的了。开心。

给定一个只包括’(‘,’)’,’{‘,’}’,’[‘,’]‘的字符串，判断字符串是否有效。
有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

代码实现如下(C++)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
  bool isValid(string s) {
    stack<char> st;   // 定义栈
    for(auto x:s){    // 遍历s
      if (x == '(' || x == '[' || x == '{') st.push(x);   // 如果有左括号，推入栈中
      else{
        if(st.empty()) return false;// 如果栈空了，说明没有左括号但是还有右括号，gg
        if((x == ')' && st.top() == '(') || (x == ']' && st.top() == '[') || (x == '}' && st.top() == '{')) st.pop(); // 如果有下一个是右括号，但是栈顶是左括号，则推出
        else return false;          // 否则说明错位，gg
      }
    }
    if(st.empty()) return true;     // 遍历万事，刚好空了，正确。
    else return false;              // 左括号多了，gg
  }
};

算法过程：初始化栈。

  • 一次处理表达式的每个括号。
  • 如果遇到开括号，我们只需将其推到栈上即可。这意味着我们将稍后处理它，让我们简单地转到前面的 子表达式。
  • 如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号，那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效。
  • 如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。

题目：每日温度

请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures=[73,74,75,71,69,72,76,73]，你的输出应该是[1,1,4,2,1,1,0,0]。
提示：气温列表长度的范围是[1,30000]。每个气温的值的均为华氏度，都是在[30,100]范围内的整数。

代码如下(C++)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
  vector<int> dailyTemperatures(vector<int>& T) {
  int n = T.size();   // 获取温度数量
  vector<int> ans(n); // 输出
  stack<int> s;     // 定义栈
  for (int i = 0; i < n; i++)
  {
    while (!s.empty() && T[i] > T[s.top()])   // 栈为空，或者下个温度，比栈顶（栈顶也是索引）索引的温度高，就把栈顶的索引给previous，然后结果就是两者差，然后把栈顶推出去。
    {
    int previousIndex = s.top();      // 把栈顶的索引给pre
    ans[previousIndex] = i - previousIndex; // 差值即为最终要输出的结果
    s.pop();  // 栈顶没用了，推出
    }
    s.push(i);  // 这个索引，把之前的都对比过了，然后把这个索引推进去。
  }
  return ans;   //返回结果
  }
};

逆波兰表达式求值

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

说明：

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

示例 1：

1
2
3
输入：["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2+1)*3)=9

代码如下(C++)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
  int ans;  // 结果
  int evalRPN(vector<string>& tokens) {
  stack<int> st;        // 定义栈
  int ans_1,ans_2;      // 定义俩数当缓存
  for(auto v_mate : tokens){  // 遍历输入 tokens
    if(v_mate == "+"){    // 如果遇到 运算符号
    ans_1 = st.top();     // 推出之前的两个数字
    st.pop();
    ans_2 = st.top();
    st.pop();
    st.push(ans_2 + ans_1); // 进行运算，注意，先推出的在前
    }
    else if(v_mate == "-"){   // 减法类似
    ans_1 = st.top();
    st.pop();
    ans_2 = st.top();
    st.pop();
    st.push(ans_2 - ans_1); // 注意是 ans_2 - ans_1
    }
    else if(v_mate == "*"){
    ans_1 = st.top();
    st.pop();
    ans_2 = st.top();
    st.pop();
    st.push(ans_2 * ans_1);
    }
    else if(v_mate == "/"){
    ans_1 = st.top();
    st.pop();
    ans_2 = st.top();
    st.pop();
    st.push(ans_2 / ans_1);
    }
    else{     // 如果不是运算符，就把字符串数字转为整型数字推入栈中
    st.push(atoi(v_mate.c_str()));
    }
  }
  ans = st.top(); // 栈中最后推入的就是结果
  return ans;
  }
};

具体解释见注释。

声明：本文为学习记录，参考之处较多，如果有侵权内容，请联系我立即删除。

End~~请支持原创撒花=￣ω￣=花撒
如果您读文章后有收获，可以打赏我喝咖啡哦～