算法与数据结构学习笔记：栈和队列
简介
栈的特点是后入先出，根据这个特点可以临时保存一些数据，之后用到依次再弹出来，常用于 DFS 深度搜索
队列一般常用于 BFS 广度搜索，类似一层一层的搜索
栈
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
辅助栈
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. 逆波兰表达式求值
根据 逆波兰表示法，求表达式的值。
有效的运算符包括
+,-,*,/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
思路：通过栈保存原来的元素，遇到表达式弹出运算，再推入结果，重复这个过程
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] 的输入。
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. 二叉树的中序遍历
/**
* 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. 克隆图
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值
val（int） 和其邻居的列表（list[Node]）。class Node { public int val; public List<Node> neighbors; }
/*
// 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’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
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. 用栈实现队列
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. 二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
/**
* 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 矩阵
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 陈子琦的博客！
评论