队列和栈

一、队列
二、栈
三、BFS模板
- 1.如果不需要确定当前遍历到了哪一层，BFS 模板如下
- 2.如果需要确定，如下

FIFO：first in first out 先进先出 ——> 队列首先处理数据结构的第一个元素
LIFO: last in first out 后进先出 ——>栈首先处理数据结构中的最后一个元素

一、队列

1.关于队列的一些要点：

新元素总是添加在队列的末尾。
移除元素总是移除队列的第一个元素。
2.基本队列的实现示例及其缺点：
1.用动态数组和指向头部的索引实现（Java）：
```java // “static void main” must be defined in a public class.

class MyQueue { // store elements private List data;
// a pointer to indicate the start position private int p_start;
public MyQueue() { data = new ArrayList(); p_start = 0; } / Insert an element into the queue. Return true if the operation is successful. */ public boolean enQueue(int x) { data.add(x); return true; };
/ Delete an element from the queue. Return true if the operation is successful. / public boolean deQueue() { if (isEmpty() == true) { return false; } p_start++; return true; } /** Get the front item from the queue. / public int Front() { return data.get(p_start); } /* Checks whether the queue is empty or not. / public boolean isEmpty() { return p_start >= data.size(); }
};

public class Main { public static void main(String[] args) { MyQueue q = new MyQueue(); q.enQueue(5); q.enQueue(3); if (q.isEmpty() == false) { System.out.println(q.Front()); } q.deQueue(); if (q.isEmpty() == false) { System.out.println(q.Front()); } q.deQueue(); if (q.isEmpty() == false) { System.out.println(q.Front()); } } }

<a name="yN66v"></a>
##### 2.缺点：
随着起始指针的移动，浪费了越来越多的空间。
<a name="AQSVr"></a>
##### 3.解决方案：
循环队列。
<a name="cv4Xu"></a>
#### 3.循环队列的实现：
<a name="A740B"></a>
##### 1.链表法实现：
```java
class Node {
  public int value;
  public Node nextNode;
  public Node(int value) {
    this.value = value;
    this.nextNode = null;
  }
}
class MyCircularQueue {
  private Node head, tail;
  private int count;
  private int capacity;
  /** Initialize your data structure here. Set the size of the queue to be k. */
  public MyCircularQueue(int k) {
    this.capacity = k;
  }
  /** Insert an element into the circular queue. Return true if the operation is successful. */
  public boolean enQueue(int value) {
    if (this.count == this.capacity)
      return false;
    Node newNode = new Node(value);
    if (this.count == 0) {
      head = tail = newNode;
    } else {
      tail.nextNode = newNode;
      tail = newNode;
    }
    this.count += 1;
    return true;
  }
  /** Delete an element from the circular queue. Return true if the operation is successful. */
  public boolean deQueue() {
    if (this.count == 0)
      return false;
    this.head = this.head.nextNode;
    this.count -= 1;
    return true;
  }
  /** Get the front item from the queue. */
  public int Front() {
    if (this.count == 0)
      return -1;
    else
      return this.head.value;
  }
  /** Get the last item from the queue. */
  public int Rear() {
    if (this.count == 0)
      return -1;
    else
      return this.tail.value;
  }
  /** Checks whether the circular queue is empty or not. */
  public boolean isEmpty() {
    return (this.count == 0);
  }
  /** Checks whether the circular queue is full or not. */
  public boolean isFull() {
    return (this.count == this.capacity);
  }
}

2.数组法实现：

class MyCircularQueue {
  private int[] queue;
  private int headIndex;
  private int count;
  private int capacity;
  /** Initialize your data structure here. Set the size of the queue to be k. */
  public MyCircularQueue(int k) {
    this.capacity = k;
    this.queue = new int[k];
    this.headIndex = 0;
    this.count = 0;
  }
  /** Insert an element into the circular queue. Return true if the operation is successful. */
  public boolean enQueue(int value) {
    if (this.count == this.capacity)
      return false;
    this.queue[(this.headIndex + this.count) % this.capacity] = value;
    this.count += 1;
    return true;
  }
  /** Delete an element from the circular queue. Return true if the operation is successful. */
  public boolean deQueue() {
    if (this.count == 0)
      return false;
    this.headIndex = (this.headIndex + 1) % this.capacity;
    this.count -= 1;
    return true;
  }
  /** Get the front item from the queue. */
  public int Front() {
    if (this.count == 0)
      return -1;
    return this.queue[this.headIndex];
  }
  /** Get the last item from the queue. */
  public int Rear() {
    if (this.count == 0)
      return -1;
    int tailIndex = (this.headIndex + this.count - 1) % this.capacity;
    return this.queue[tailIndex];
  }
  /** Checks whether the circular queue is empty or not. */
  public boolean isEmpty() {
    return (this.count == 0);
  }
  /** Checks whether the circular queue is full or not. */
  public boolean isFull() {
    return (this.count == this.capacity);
  }
}

4.Java内置库的队列：

1.初始化：

Queue<Integer> queue=new LinkedList<>();
Deque<Integer> deque=new LinkedList<>();

2.常用方法：

queue.push(1);
int i=queue.peek();//i=1
int j=queue.poll();//j=1
boolean b=queue.isEmpty();//b=true
deque.addLast(1);
int i1=deque.getFirst();//i1=1
int j1=deque.removeFirst();//j1=1;
boolean bo=deque.isEmpty();//bo=true

5.队列的高级应用：广度优先搜索（BFS）

1.BFS : Breadth First Search

2.BFS的解释：

首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。

3.BFS的应用：

最短路径

4.BFS的优化：

广度搜索的判断重复如果直接判断十分耗时，我们一般借助哈希表来优化时间复杂度。

5.BFS一般框架实现代码（伪代码）：

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路
    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数
    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

6.经典题举例：

（1）leetcode279 完全平方数：

class Solution {
    public int numSquares(int n) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        queue.add(0);
        visited.add(0);
        int distance = 0;
        while (!queue.isEmpty()) {
            distance++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();
                for (int j = 1; j * j + curr <= n; j++) {
                    int next = j * j + curr;
                    if (next == n) return distance;
                    if (next < n && !visited.contains(next)) {
                        queue.add(next);
                        visited.add(next);
                    }
                }
            }
        }
        return distance;
    }
}

（2）leetcode200 岛屿数量：

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                    bfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void bfs(char[][] grid, int i, int j){
        Queue<int[]> list = new LinkedList<>();
        list.add(new int[] { i, j });
        while(!list.isEmpty()){
            int[] cur = list.remove();
            i = cur[0]; j = cur[1];
            if(0 <= i && i < grid.length && 0 <= j && j < grid[0].length && grid[i][j] == '1') {
                grid[i][j] = '0';
                list.add(new int[] { i + 1, j });
                list.add(new int[] { i - 1, j });
                list.add(new int[] { i, j + 1 });
                list.add(new int[] { i, j - 1 });
            }
        }
    }
}

6.BFS升级：双向BFS

思想：从起始点和终点同时开始搜索，相遇时停止。

二、栈

1.关于栈的一些要点：

在栈这种数据结构中，我们首先处理的是最新元素。
删除时首先删除最新元素。
插入时也直接插到末尾。
2.基本栈的实现示例：
```java // “static void main” must be defined in a public class. class MyStack { private List
data; // store elements public MyStack() {
```
  data = new ArrayList<>();
```
} /* Insert an element into the stack. / public void push(int x) {
```
  data.add(x);
```
} /* Checks whether the queue is empty or not. / public boolean isEmpty() {
```
  return data.isEmpty();
```
} /* Get the top item from the queue. / public int top() {
```
  return data.get(data.size() - 1);
```
} /* Delete an element from the queue. Return true if the operation is successful. / public boolean pop() {
```
  if (isEmpty()) {
      return false;
  }
  data.remove(data.size() - 1);
  return true;
```
} };

public class Main { public static void main(String[] args) { MyStack s = new MyStack(); s.push(1); s.push(2); s.push(3); for (int i = 0; i < 4; ++i) { if (!s.isEmpty()) { System.out.println(s.top()); } System.out.println(s.pop()); } } }

<a name="at0fv"></a>
#### 3.Java内置库的栈：
<a name="NPi3o"></a>
##### 1.初始化：
```java
Stack<Integer> stack1=new LinkedList<>();
Deque<Integer> stack2=new LinkedList<>();

2.常用方法：

stack1.push(1);
stack2.addFirst(1);
int i=stack1.peek();//i=1
int j=stack2.getFirst();//j=1
int k=stack1.poll();//k=1
int l=stack2.removeFirst();//l=1
stack1.peek();//null
stack2.getFirst();//null

4.栈的高级应用：深度优先搜索（DFS）

1.DFS：Depth First Search

2.DFS解释：

（1）访问顶点v；
（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

3.DFS应用：

全排列，迷宫问题，n皇后问题，可行路径问题

4.DFS的缺点：

DFS找到的结果不一定是最优结果。

5.DFS一般框架实现代码（伪代码）：

（递归方案）

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

（显式栈方案）

/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(int root, int target) {
    Set<Node> visited;
    Stack<Node> s;
    add root to s;
    while (s is not empty) {
        Node cur = the top element in s;
        return true if cur is target;
        for (Node next : the neighbors of cur) {
            if (next is not in visited) {
                add next to s;
                add next to visited;
            }
        }
        remove cur from s;
    }
    return false;
}

6.经典题举例：

leetcode 200 岛屿数量：

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == '1'){
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    private void dfs(char[][] grid, int i, int j){
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return;
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
    }
}

leetcode 133 克隆图（图的深拷贝）

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/
class Solution {
    public Node cloneGraph(Node node) {
        Map<Node, Node> lookup = new HashMap<>();
        return dfs(node, lookup);
    }
    private Node dfs(Node node, Map<Node,Node> lookup) {
        if (node == null) return null;
        if (lookup.containsKey(node)) return lookup.get(node);
        Node clone = new Node(node.val, new ArrayList<>());
        lookup.put(node, clone);
        for (Node n : node.neighbors)clone.neighbors.add(dfs(n,lookup));
        return clone;
    }
}

leetcode 494 目标和：

class Solution {
    int count = 0;
    public int findTargetSumWays(int[] nums, int S) {
        dfs(nums,0,0,S);
        return count;
    }
    public void dfs(int[] nums,int i,int sum,int S){
        if(i==nums.length){
            if(sum==S){
                count++;
            }
        }else {
            dfs(nums,i+1,sum+nums[i],S);
            dfs(nums,i+1,sum-nums[i],S);
        }
    }
}

三、BFS模板

1.如果不需要确定当前遍历到了哪一层，BFS 模板如下

while queue 不空：
    cur = queue.pop()
    for 节点 in cur的所有相邻节点：
        if 该节点有效且未访问过：
            queue.push(该节点)

2.如果需要确定，如下

这里增加了 level 表示当前遍历到二叉树中的哪一层了，也可以理解为在一个图中，现在已经走了多少步了。size 表示在当前遍历层有多少个元素，也就是队列中的元素数，我们把这些元素一次性遍历完，即把当前层的所有元素都向外走了一步。

level = 0
while queue 不空：
    size = queue.size()
    while (size --) {
        cur = queue.pop()
        for 节点 in cur的所有相邻节点：
            if 该节点有效且未被访问过：
                queue.push(该节点)
    }
    level ++;

一、队列

1.关于队列的一些要点：

2.基本队列的实现示例及其缺点：

1.用动态数组和指向头部的索引实现（Java）：

2.数组法实现：

4.Java内置库的队列：

1.初始化：

2.常用方法：

5.队列的高级应用：广度优先搜索（BFS）

1.BFS : Breadth First Search

2.BFS的解释：

3.BFS的应用：

4.BFS的优化：

5.BFS一般框架实现代码（伪代码）：

6.经典题举例：

6.BFS升级：双向BFS

二、栈

1.关于栈的一些要点：

2.基本栈的实现示例：

2.常用方法：

4.栈的高级应用：深度优先搜索（DFS）

1.DFS：Depth First Search

2.DFS解释：

3.DFS应用：

4.DFS的缺点：

5.DFS一般框架实现代码（伪代码）：

6.经典题举例：

三、BFS模板

1.如果不需要确定当前遍历到了哪一层，BFS 模板如下

2.如果需要确定，如下