简介
栈的特点是后入先出
根据这个特点可以临时保存一些数据，之后用到依次再弹出来，常用于 DFS 深度搜索
队列一般常用于 BFS 广度搜索，类似一层一层的搜索
Stack 栈
最小栈
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
思路：用两个栈实现，一个最小栈始终保证最小值在顶部
public class MinStack
{
Stack<int> stack;
Stack<int> minStack;
public MinStack()
{
stack = new Stack<int>();
minStack = new Stack<int>();
}
public void Push(int val)
{
stack.Push(val);
if (minStack.Count == 0 || val <= minStack.Peek())
{
minStack.Push(val);
}
}
public void Pop()
{
int val = stack.Pop();
if (minStack.Peek() == val)
{
minStack.Pop();
}
}
public int Top()
{
return stack.Peek();
}
public int GetMin()
{
return minStack.Peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.Push(val);
* obj.Pop();
* int param_3 = obj.Top();
* int param_4 = obj.GetMin();
*/
逆波兰表达式求值
150. 逆波兰表达式求值
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
思路：通过栈保存原来的元素，遇到表达式弹出运算，再推入结果，重复这个过程
public int EvalRPN(string[] tokens)
{
Stack<int> stack = new Stack<int>();
int length = tokens.Length;
for (int i = 0; i < length; i++)
{
string token = tokens[i];
if (IsNumber(token))
{
stack.Push(int.Parse(token));
}
else
{
int num2 = stack.Pop();
int num1 = stack.Pop();
switch (token)
{
case "+":
stack.Push(num1 + num2);
break;
case "-":
stack.Push(num1 - num2);
break;
case "*":
stack.Push(num1 * num2);
break;
case "/":
stack.Push(num1 / num2);
break;
}
}
}
return stack.Pop();
}
public bool IsNumber(string token)
{
return char.IsDigit(token[^1]);
}
字符串解码
394. 字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
思路：通过栈辅助进行操作
public string DecodeString(string s)
{
StringBuilder sb = new StringBuilder();
Stack<int> stack = new Stack<int>();
int num = 0;
int length = s.Length;
for (int i = 0; i < length; i++)
{
char c = s[i];
if (char.IsDigit(c))
{
num = num * 10 + c - '0';
}
else if (char.IsLetter(c))
{
sb.Append(c);
}
else if (c == '[')
{
stack.Push(num);
num = 0;
sb.Append(c);
}
else
{
int top = sb.Length - 1;
StringBuilder temp = new StringBuilder();
while (sb[top] != '[')
{
temp.Append(sb[top]);
sb.Length = top;
top--;
}
sb.Length = top;
StringBuilder temp2 = new StringBuilder();
for (int j = temp.Length - 1; j >= 0; j--)
{
temp2.Append(temp[j]);
}
int k = stack.Pop();
for (int j = 0; j < k; j++)
{
sb.Append(temp2);
}
}
}
return sb.ToString();
}
二叉树的中序遍历
094. 二叉树的中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
// 思路：通过stack 保存已经访问的元素，用于原路返回
public IList<int?> InorderTraversal(TreeNode root)
{
IList<int?> traversal = new List<int?>();
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = root;
while (stack.Count > 0 || node != null)
{
while (node != null)
{
stack.Push(node);
node = node.left;
}
node = stack.Pop();
traversal.Add(node.val);
node = node.right;
}
return traversal;
}
柱状图中最大的矩形
084. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
思路：求以当前柱子为高度的面积，即转化为寻找小于当前值的左右两边值
用栈保存小于当前值的左的元素
public int LargestRectangleArea(int[] heights)
{
int length = heights.Length;
int[] left = new int[length];
int[] right = new int[length];
Array.Fill(left, -1);
Array.Fill(right, length);
Stack<int> stack = new Stack<int>();
for (int i = 0; i < length; i++)
{
int height = heights[i];
while (stack.Count > 0 && heights[stack.Peek()] >= height)
{
right[stack.Pop()] = i;
}
if (stack.Count > 0)
{
left[i] = stack.Peek();
}
stack.Push(i);
}
int area = 0;
for (int i = 0; i < length; i++)
{
area = Math.Max(area, (right[i] - left[i] - 1) * heights[i]);
}
return area;
}
接雨水
42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
public int Trap(int[] height)
{
int amount = 0;
Stack<int> stack = new Stack<int>();
int n = height.Length;
for (int i = 0; i < n; i++) {
while (stack.Count > 0 && height[stack.Peek()] <= height[i]) {
int curr = stack.Pop();
if (stack.Count == 0) {
break;
}
int prev = stack.Peek();
int currWidth = i - prev - 1;
int currHeight = Math.Min(height[prev], height[i]) - height[curr];
amount += currWidth * currHeight;
}
stack.Push(i);
}
return amount;
}
Queue 队列
常用于 BFS 宽度优先搜索
用栈实现队列
232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
/**
* 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();
*/
public class MyQueue
{
Stack<int> inStack;
Stack<int> outStack;
public MyQueue()
{
inStack = new Stack<int>();
outStack = new Stack<int>();
}
public void Push(int x)
{
inStack.Push(x);
}
public int Pop()
{
if (outStack.Count == 0)
{
In2Out();
}
return outStack.Pop();
}
public int Peek()
{
if (outStack.Count == 0)
{
In2Out();
}
return outStack.Peek();
}
public bool Empty()
{
return inStack.Count == 0 && outStack.Count == 0;
}
private void In2Out()
{
while (inStack.Count > 0)
{
outStack.Push(inStack.Pop());
}
}
}
岛屿数量
200. 岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
思路：通过深度搜索遍历可能性（注意标记已访问元素）
int[][] dirs = { new[] { -1, 0 }, new[] { 1, 0 }, new[] { 0, -1 }, new[] { 0, 1 } };
public int NumIslands(char[][] grid)
{
int islands = 0;
int m = grid.Length, n = grid[0].Length;
bool[][] visited = new bool[m][];
for (int i = 0; i < m; i++)
{
visited[i] = new bool[n];
}
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j] == '0' || visited[i][j])
{
continue;
}
islands++;
visited[i][j] = true;
Queue<int[]> queue = new Queue<int[]>();
queue.Enqueue(new int[] { i, j });
while (queue.Count > 0)
{
int[] cell = queue.Dequeue();
int row = cell[0], col = cell[1];
foreach (int[] dir in dirs)
{
int newRow = row + dir[0], newCol = col + dir[1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && grid[newRow][newCol] == '1' && !visited[newRow][newCol])
{
visited[newRow][newCol] = true;
queue.Enqueue(new int[] { newRow, newCol });
}
}
}
}
}
return islands;
}
01矩阵
542. 01矩阵
给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
int[][] dirs = { new[] { -1, 0 }, new[] { 1, 0 }, new[] { 0, -1 }, new[] { 0, 1 } };
const int INFINITY = int.MaxValue / 2;
public int[][] UpdateMatrix(int[][] mat)
{
int m = mat.Length, n = mat[0].Length;
int[][] distances = new int[m][];
for (int i = 0; i < m; i++)
{
distances[i] = new int[n];
}
Queue<int[]> queue = new Queue<int[]>();
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (mat[i][j] == 0)
{
queue.Enqueue(new int[] { i, j });
}
else
{
distances[i][j] = INFINITY;
}
}
}
while (queue.Count > 0)
{
int[] cell = queue.Dequeue();
int row = cell[0], col = cell[1];
foreach (int[] dir in dirs)
{
int newRow = row + dir[0], newCol = col + dir[1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && distances[newRow][newCol] == INFINITY)
{
distances[newRow][newCol] = distances[row][col] + 1;
queue.Enqueue(new[] { newRow, newCol });
}
}
}
return distances;
}
克隆图
133. 克隆图
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
class Node {
public int val;
public List neighbors;
}
public Node CloneGraph(Node node)
{
if (node == null)
{
return null;
}
IDictionary<Node, Node> cloneDictionary = new Dictionary<Node, Node>();
cloneDictionary.Add(node, new Node(node.val));
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(node);
while (queue.Count > 0)
{
Node original = queue.Dequeue();
Node cloned = cloneDictionary[original];
IList<Node> originalNeighbors = original.neighbors;
IList<Node> clonedNeighbors = cloned.neighbors;
foreach (Node originalNeighbor in originalNeighbors)
{
if (!cloneDictionary.ContainsKey(originalNeighbor))
{
cloneDictionary.Add(originalNeighbor, new Node(originalNeighbor.val));
queue.Enqueue(originalNeighbor);
}
clonedNeighbors.Add(cloneDictionary[originalNeighbor]);
}
}
return cloneDictionary[node];
}
总结
练习
