Aelous-Blog

养一猫一狗,猫叫夜宵,狗叫宵夜

0%

队列&栈-03

栈:后入先出的数据结构

在 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~~ 撒花= ̄ω ̄=花撒
如果您读文章后有收获,可以打赏我喝咖啡哦~