作者：whisper

链接：http://proprogrammar.com:443/article/613

声明：请尊重原作者的劳动，如需转载请注明出处

    在前面的章节中，我们介绍了两个数据结构：队列和栈

    1. 队列

    队列是一种 FIFO 式的数据结构：第一个元素将被首先处理。有两个重要操作：入队和出队。我们可以使用带有两个指针的动态数组来实现队列。

    我们可以使用广度优先搜索（BFS）。

    队列还有一些重要的扩展，例如：

• 双端队列
• 优先队列

    我们在后面的卡片中介绍这些结构。

    2. 栈

    栈是一种 LIFO 式的数据结构：最后一个元素将被首先处理。有两个重要操作：push 和 pop。栈的实现非常简单，使用动态数组就足以实现栈。

    当满足 LIFO 原则时，我们使用栈。深度优先搜索（DFS）是栈的一个重要应用。

    3. 总结

    总之，你应该能够理解和比较以下几组概念：

• FIFO 和 LIFO；
• 队列 和 栈；
• BFS 和 DFS。

    要熟练掌握这个主题，最好的办法就是训练。本章节中，我们为你提供了更多练习。

    算法-用栈实现队列

使用栈实现队列的下列操作：

• push(x) -- 将一个元素放入队列的尾部。
• pop() -- 从队列首部移除元素。
• peek() -- 返回队列首部的元素。
• empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

• 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

class MyQueue {
    Stack<Integer> data, temp;

    /** Initialize your data structure here. */
    public MyQueue() {
        data = new Stack<>();
        temp = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        data.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        
        while(!data.isEmpty()){
            temp.push(data.pop());
        }
        
        int m = temp.pop();
        
        while(!temp.isEmpty()){
            data.push(temp.pop());
        }
        
        return m;
    }
    
    /** Get the front element. */
    public int peek() {
        while(!data.isEmpty()){
            temp.push(data.pop());
        }
        
        int m = temp.peek();
        
        while(!temp.isEmpty()){
            data.push(temp.pop());
        }
        
        return m;
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return data.isEmpty();
    }
}

/**
 * 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();
 * boolean param_4 = obj.empty();
 */

        因为栈是先入后出的，而队列是先入先出的，所以代码中用了两个栈，其中一个临时的栈用来中转数据

       再看一种比较复杂同时效率较高的算法

import java.util.NoSuchElementException;

class MyQueue {

    private Stack<Integer> stack;
    private int[] buffer;
    private int size;

    /** Initialize your data structure here. */
    public MyQueue() {
        stack = new Stack<>();
        buffer = new int[16];
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stack.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (empty()) {
            throw new NoSuchElementException();
        }
        if (size > 0) {
            return buffer[--size];
        }
        while (stack.size() != 1) {
            if (size >= buffer.length) {
                grow();
            }
            buffer[size++] = stack.pop();
        }
        return stack.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        if (empty()) {
            throw new NoSuchElementException();
        }
        if (size > 0) {
            return buffer[size - 1];
        }
        while (!stack.isEmpty()) {
            if (size >= buffer.length) {
                grow();
            }
            buffer[size++] = stack.pop();
        }
        return buffer[size - 1];
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack.isEmpty() && size == 0;
    }

    private void grow() {
        int[] newBuffer = new int[buffer.length << 1];
        System.arraycopy(buffer, 0, newBuffer, 0, buffer.length);
        buffer = newBuffer;
    }
}

/**
 * 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();
 * boolean param_4 = obj.empty();
 */

    这里在用到栈的同时还用到了一个数组，每次入队时入栈，出队时将栈中的元素放入数组，这样队列中的元素被分成了两部分，一部分在栈中，一部分在数组中，队头部的元素在数组中，尾部的元素在栈中，当peek或pop时，操作数组就可以了，当push时，操作栈就可以了，当数组中没有元素时，再从栈中取元素到数组中，而且会自动增加数组的长度

    算法-用队列实现栈

使用队列实现栈的下列操作：

• push(x) -- 元素 x 入栈
• pop() -- 移除栈顶元素
• top() -- 获取栈顶元素
• empty() -- 返回栈是否为空

注意:

• 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
• 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
• 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

class MyStack {
    LinkedList<Integer> data, temp;

    /** Initialize your data structure here. */
    public MyStack() {
        data = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        data.offer(x);
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int m = -1, i = 0, n;
        temp = new LinkedList<>();
        while(!data.isEmpty()){
            m = data.poll();
            temp.offer(m);
        }
        
        n = temp.size() - 1;
        while(i < n){
            data.offer(temp.poll());
            i++;
        }
        
        return m;
    }
    
    /** Get the top element. */
    public int top() {
        int m = -1;
        temp = new LinkedList<>();
        while(!data.isEmpty()){
            m = data.poll();
            temp.offer(m);
        }
        
        while(!temp.isEmpty()){
            data.offer(temp.poll());
        }
        
        return m;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return data.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

    同栈实现队列类似，这里用了两个队列，一个临时队列用于保存中间数据

    下面看另一种解法

class MyStack {
    Queue<Integer> queue;
    /** Initialize your data structure here. */
    public MyStack() {
        queue=new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.add(x);
        int size=queue.size();
        while(size-->1){
            queue.add(queue.poll());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.remove();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

    这里只用了一个队列，关键在push，入栈的时候将队列中原有元素都入放新入栈元素的后面，同时保持原有的顺序，即相当于将新入栈的元素由原来放入队列的尾部改为放入队列的头部

    算法-字符串解码

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

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

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

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

示例:

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

// 想法：其中的一部分与整体的处理相同，可能会想到用递归，整体到局部的思想，动态规划
    public String decodeString(String s) {
        StringBuilder sb = new StringBuilder();
        char[] sArr = s.toCharArray();
        int i = s.indexOf('['), j, k = 1, times = 0;
        String tempStr;
        
        if(i == -1){
            sb.append(s);
        }else if(i > 0){
            for(int m = i - 1; m >=0; m--){
                if(sArr[m] <= '9' && sArr[m] >= '0'){
                    times = times + (sArr[m] - '0') * k;
                    k *= 10;
                }else{
                    sb.append(s.substring(0, m + 1));
                    break;
                }
            }
        }
        
        if(i != -1){
            j = rightIndex(s.substring(i));
            tempStr = decodeString(s.substring(i + 1, j + i));
            for(k = 0; k < times; k++){
                sb.append(tempStr);
            }
            
            if(s.length() > j + i + 1){
                sb.append(decodeString(s.substring(j+i+1)));
             }
        }
        
        return sb.toString();
    }
    
    private int rightIndex(String s){
        char[] arr = s.toCharArray();
        int sum = 1;
        
        for(int i = 1; i < arr.length; i++){
            if(arr[i] == '[')
                sum++;
            else if(arr[i] == ']')
                sum--;
            
            if(sum == 0){
                return i;
            }
        }
        
        return -1;
    }

     部分与整体类似的问题，可能会想到用递归，分治，整体到局部的思想，或者动态规划，部分到整体的思想，而这里用到括号，又可能想到用栈，上面是一种递归分治的方法（同时用到递归也会想到栈）

    下面看一种使用栈的情况

public String decodeString(String s) {
        
   Stack<String> stack=new Stack<String>();
	for(int i=0;i<s.length();i++) {
		if(s.charAt(i)==']') {
			String string="";
			while(!stack.peek().equals("[")) {
				string=stack.pop()+string;
			}
			stack.pop();
			
			String countString="";
			while((!stack.isEmpty())&&(stack.peek().charAt(0)>='0'&&stack.peek().charAt(0)<='9')) {
				countString=stack.pop()+countString;
			}
			int count=Integer.parseInt(countString);
			
			String retString="";
			for(int j=0;j<count;j++) {
				retString=retString+string;
			}
			stack.push(retString);
		}
		else {
				String str=""+s.charAt(i);
				stack.push(str);
			}
		}
	
	String aaa="";
	while(!stack.isEmpty()) {
		aaa=stack.pop()+aaa;
	}
	return aaa;
}

    这里使用栈来处理，当处理到']'时，找到前一个'['及前面的数字，转化成字符串，因为外层的[]包裹里层的[]，肯定是先找到里层的[]，这样处理里也是从内到外，结果是正确的

    算法-图像渲染

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

示例 1:

输入: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。

注意:

• image 和 image[0] 的长度在范围 [1, 50] 内。
• 给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
• image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。

// 想法：用递归
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if(image.length == 0 || image[sr][sc] == newColor){
            return image;
        }
        
        floodFill(image, sr, sc, image[sr][sc], newColor);
        
        return image;
    }
    
    public void floodFill(int[][] image, int sr, int sc, int originColor, int newColor) {
        if(sr >= 0 && sr < image.length && sc >= 0 && sc < image[0].length && image[sr][sc] == originColor){
            image[sr][sc] = newColor;
            floodFill(image, sr - 1, sc, originColor, newColor);
            floodFill(image, sr + 1, sc, originColor, newColor);
            floodFill(image, sr, sc - 1, originColor, newColor);
            floodFill(image, sr, sc + 1, originColor, newColor);
        }
    }

    简单的向四个方向递归做染色就可以了

    再看不用递归用栈的情况

public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        Stack<int[]> s = new Stack<>();
        int m = image.length, n = image[0].length;
        int curColor = image[sr][sc];
        if(curColor == newColor)
            return image;
        image[sr][sc] = newColor;
        int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        s.push(new int[]{sr, sc});
        while(!s.isEmpty()){
            int[] top = s.pop();
            for(int i=0; i<4; i++){
                int x = top[0]+dir[i][0], y = top[1]+dir[i][1];
                if(x>=0 && x<m && y>=0 && y<n && image[x][y]==curColor){
                    image[x][y] = newColor;
                    s.push(new int[]{x, y});
                }
            }
        }
        return image;
    }

    这里先规定四个方向，要处理的颜色点入栈，不断处理，直到相邻没有要处理的颜色，这里也可以用队列来处理，不同之处在于一个是深度优先处理，一个是广度优先处理

    算法-01 矩阵

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1:

输入:
0 0 0
0 1 0
0 0 0

输出:
0 0 0
0 1 0
0 0 0

示例 2:

输入:
0 0 0
0 1 0
1 1 1

输出:
0 0 0
0 1 0
1 2 1

注意:

1. 给定矩阵的元素个数不超过 10000。
2. 给定矩阵中至少有一个元素是 0。
3. 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

// 想法：先找0（距离为0），1（距离设为无穷大），更新距离为1，2，3。。。的1的距离
   public int[][] updateMatrix(int[][] matrix) {
        int[][] minDis = new int[matrix.length][matrix[0].length];
        List<Integer> index = new ArrayList<>();
        int min = 0, i, j;
        
        for(i = 0; i < minDis.length; i++){
            for(j = 0; j < minDis[0].length; j++){
                if(matrix[i][j] == 0){
                    minDis[i][j] = 0;
                }else{
                    minDis[i][j] = Integer.MAX_VALUE;
                    index.add((i<<16) + j);
                }
            }
        }
        
        while(index.size() > 0) {
        	min++;
	        for(int k = index.size() - 1; k >= 0; k--){
	            j = index.get(k) & 0xffff;
	            i = (index.get(k) >> 16) & 0xffff;
	            if(min == minDis(minDis, i, j) + 1){
	                    minDis[i][j] = min;
	                    index.remove(k);
	            }
	        }
        }
        
        return minDis;
    }
    
    private int minDis(int[][] minDis, int i, int j){
        int d1 = Integer.MAX_VALUE, d2 = Integer.MAX_VALUE, d3 = Integer.MAX_VALUE, d4 = Integer.MAX_VALUE;
        if(i > 0){
            d1 = minDis[i - 1][j];
        }
        if(i < minDis.length - 1){
            d2 = minDis[i+1][j];
        }
        if(j > 0){
            d3 = minDis[i][j - 1];
        }
        if(j < minDis[0].length - 1){
            d4 = minDis[i][j + 1];
        }
        
        return Math.min(Math.min(d1, d2), Math.min(d3, d4));
    }

    先找0（距离为0），1（距离设为无穷大），更新距离0的距离为1，2，3。。。的1的距离，根据1四周的点最小距离来更新，核心是当前1与0的最近距离为四周最近距离加1

    下面看另一种解法

public int[][] updateMatrix(int[][] matrix) {
        int rows = matrix.length;
        if (rows == 0) 
            return matrix;
        int cols = matrix[0].length;
        //int [][] dist = new int[][]{rows, cols};
        
        for (int i = 0; i < rows; i++){
            for (int j = 0; j < cols; j++){
                int l = 10001, t = 10001;
                if (matrix[i][j] != 0){
                    if (i > 0){
                        l = matrix[i-1][j];
                    }
                    if (j > 0){
                        t = matrix[i][j-1];
                    }
                    matrix[i][j] = Math.min(l, t) + 1;
                }
            }
        }
        
        for (int i = rows-1; i >= 0; i--){
            for (int j = cols-1; j >= 0; j--){
                int r = 10001, b = 10001;
                if (matrix[i][j] != 0) {
                    if (i < rows-1){
                        r = matrix[i+1][j];
                    }
                    if (j < cols-1){
                        b = matrix[i][j+1];
                    }
                    matrix[i][j] = Math.min(matrix[i][j], Math.min(r, b) + 1);
                }
            }
        }
        return matrix;
    }

    上面的思路就是最小距离是左上的最小距离加1或者右下的最小距离加1，即上下左右的最小距离加1，注意处理上的技巧，是一种动态规划的思想，由局部不断扩大范围，并使用之前的结果

    算法-钥匙和房间

有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初，除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true，否则返回 false。

示例 1：

输入: [[1],[2],[3],[]]
输出: true
解释:  
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

示例 2：

输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

提示：

1. 1 <= rooms.length <= 1000
2. 0 <= rooms[i].length <= 1000
3. 所有房间中的钥匙数量总计不超过 3000。

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        Set<Integer> handledRooms = new HashSet<>();
        Queue<Integer> enterRooms = new LinkedList<>();
        int room;
        List<Integer> keys;
        
        enterRooms.add(0);
        handledRooms.add(0);
        
        while(!enterRooms.isEmpty()){
            room = enterRooms.poll();
            keys = rooms.get(room);
            
            for(Integer k: keys){
                while(!handledRooms.contains(k)){
                    enterRooms.offer(k);
                    handledRooms.add(k);
                }
            }
            
        }
        
        return handledRooms.size() == rooms.size();
    }

    对0号房间能到的房间，这些房间能到的房间也是符合题意的，不断重复这个过程，注意保存已处理（已进入）的房间，如果最后已进入的房间的数量等于原有房间的数量，那么返回true，即所有房间都可以进入

    看另一种做法

    public void dfs(List<List<Integer>> rooms,int now,boolean [] flag){
        if(flag[now]) return;
        flag[now]=true;
        for(int x:rooms.get(now)){
            dfs(rooms,x,flag);
        }
    }
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean [] flag=new boolean[rooms.size()];
        dfs(rooms,0,flag);
        for(int i=0;i<flag.length;i++){
            if(!flag[i]) return  false;
        }
        return true;
    }

    思想都是类似的，由当前房间进入其它房间，再由其它房间进入另外的房间，不断重复，深度优先处理，这里设置flag数组，能进入则flag[i]=true，搜索结束后如果所有的flag都是true，即全部房间都能进入，那么返回true

亲爱的读者：有时间可以点赞评论一下