算法与数据结构学习笔记:栈和队列

本文最后更新于:November 28, 2021 am

简介

栈的特点是后入先出,根据这个特点可以临时保存一些数据,之后用到依次再弹出来,常用于 DFS 深度搜索

队列一般常用于 BFS 广度搜索,类似一层一层的搜索

155. 最小栈

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

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

辅助栈
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
class MinStack {
public:
/** initialize your data structure here. */
stack<int> minStack;
stack<int> dataStack;
MinStack() {
minStack.push(INT_MAX);

}

void push(int x) {
dataStack.push(x);
minStack.push(min(minStack.top(),x));
}

void pop() {
minStack.pop();
dataStack.pop();


}

int top() {
return dataStack.top();

}

int getMin() {
return minStack.top();
}
};

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

150. 逆波兰表达式求值

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

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

思路:通过栈保存原来的元素,遇到表达式弹出运算,再推入结果,重复这个过程

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
44
45
class Solution {
public:
int evalRPN(vector<string>& tokens) {
if(tokens.empty())
return 0;
stack<int> st;
for(int i=0;i<tokens.size();i++)
{
if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/")
{

if(st.size()<2)
return -1;
auto b=st.top();
st.pop();
auto a=st.top();
st.pop();
int res;
switch(tokens[i][0])
{
case '+':
res=a+b;
break;
case '-':
res=a-b;
break;
case '*':
res=a*b;
break;
case '/':
res=a/b;
break;
}
st.push(res);
}
else
{
st.push(atoi(tokens[i].c_str()));

}
}
return st.top();

}
};

394. 字符串解码

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

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
44
45
46
class Solution {
public:
string decodeString(string s) {
stack<int> nums;
stack<string> strs;
string res="";
int num=0;
for(int i=0;i<s.size();i++)
{
char ch=s[i];
if(ch>='0'&&ch<='9')
{
//多位数情况处理
num=num*10+ch-'0';

}else if((ch >= 'a' && ch <= 'z') ||(ch >= 'A' && ch <= 'Z'))
{
res+=ch;

}
else if(ch=='[')
{
nums.push(num);
num=0;
strs.push(res);
res="";
}
else
{
int j=nums.top();
nums.pop();
while(j--)
{
strs.top()+=res;
}
res=strs.top();
//之后若还是字母,就会直接加到res之后,因为它们是同一级的运算
//若是左括号,res会被压入strs栈,作为上一层的运算
strs.pop();
}

}
return res;

}
};

94. 二叉树的中序遍历

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:

vector<int> inorderTraversal(TreeNode* root) {
vector<int>ans;
if(root==NULL)
return ans;
stack<TreeNode*> st;
auto cur=root;
while(cur!=NULL||!st.empty())
{
while(cur!=NULL)
{
st.push(cur);
cur=cur->left;
}
cur=st.top();
st.pop();
ans.push_back(cur->val);
cur=cur->right;

}
return ans;


}
};

133. 克隆图

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。

图中的每个节点都包含它的值 valint) 和其邻居的列表(list[Node])。

1
2
3
4
class Node {
public int val;
public List<Node> neighbors;
}
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
/*
// Definition for a Node.
class Node {
public:
int val;
vector<Node*> neighbors;

Node() {
val = 0;
neighbors = vector<Node*>();
}

Node(int _val) {
val = _val;
neighbors = vector<Node*>();
}

Node(int _val, vector<Node*> _neighbors) {
val = _val;
neighbors = _neighbors;
}
};
*/

class Solution {
public:
unordered_map<Node*,Node*> mp;
Node* cloneGraph(Node* node) {
if(node==NULL)
return node;
if(mp.count(node))
return mp[node];
const auto newnode=new Node(node->val);
mp[node]=newnode;
for(auto n:node->neighbors)
{
mp[node]->neighbors.push_back(cloneGraph(n));
}
return mp[node];

}
};

200. 岛屿数量

给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

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
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[0].size(); j++){
if(grid[i][j] == '1'){
dfs(grid, i, j);
count++;
}
}
}

return count;
}
void dfs(vector<vector<char>>& grid, int i, int j){
if(i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] != '1'){
return;
}

grid[i][j] = '2';
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
};

84. 柱状图中最大的矩形

队列

232. 用栈实现队列

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class MyQueue {
public:
stack<int> s1,s2;
int front;
/** Initialize your data structure here. */
MyQueue() {

}

/** Push element x to the back of queue. */
void push(int x) {
if(s1.empty())
front=x;
s1.push(x);

}

/** Removes the element from in front of queue and returns that element. */
int pop() {
if(s2.empty())
{
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
}
int ret =s2.top();
s2.pop();
return ret;

}

/** Get the front element. */
int peek() {
if(!s2.empty())
{
return s2.top();
}
return front;

}

/** Returns whether the queue is empty. */
bool empty() {
if(s1.empty()&&s2.empty())
{
return true;

}
else
{
return false;
}

}
};

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

102. 二叉树的层序遍历

给你一个二叉树,请你返回其按 层序遍历 得到的节点值。 (即逐层地,从左到右访问所有节点)。

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
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if(root==NULL)
return res;
queue<TreeNode *> q;
q.push(root);
while(!q.empty())
{
int currentLevelSize=q.size();
vector<int> level;
for(int i=0;i<currentLevelSize;i++)
{
auto cur=q.front();
level.push_back(cur->val);
q.pop();
if(cur->left)
q.push(cur->left);
if(cur->right)
q.push(cur->right);
}
res.push_back(level);
}
return res;

}
};

542. 01 矩阵