队列&栈-01

数组中，我们可以通过索引来访问数据，很多情况下我们可能会想限制数据的处理顺序。

常见的两种处理顺序是:先入先出（FIFO）以及后入先出（LIFO）

处理顺序	数据结构
先入先出	队列
后入先出	栈

可以学到什么：

1. 了解：FIFO 和 LIFO 处理顺序的原理
2. 实现这两个数据结构
3. 熟悉内置队列和栈结构
4. 解决基本队列相关问题，BFS。
5. 解决基本栈相关问题。
6. 理解，使用 DFS 和其他递归解决问题时，系统栈如何帮你。

队列:先入先出的数据结构

在 FIFO 数据结构中，将首先处理添加到队列中的第一个元素。

如上图所示，队列是典型的 FIFO 数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。删除（delete）操作也被称为出队（dequeue)。你只能移除第一个元素。

队列-实现

队列的实现方式其实很好理解，就是一个数组，我们通过指针对头部进行索引，就可以实现了。

这种方法实现很简单，但是效率很低，因为数组的大小不是固定的，会随着指针的移动，占用的空间越来越大。

改进队列

循环队列：我们使用固定大小的数组，和两个指针来指示起始位置和结束位置，目的是重用我们之前被浪费掉的存储。

设计循环队列

要求我们设计的队列有如下功能：

• MyCircularQueue(k)：构造器，设置队列长度为 k
• Front：从队首获取元素。如果队列为空，返回-1
• Rear：获取队尾元素。如果队列为空，返回-1
• enQueue(value)：向循环队列插入一个元素。如果成功插入则返回真。
• deQueue()：从循环队列中删除一个元素。如果成功删除则返回真。
• isEmpty()：检查循环队列是否为空。
• isFull()：检查循环队列是否已满。

设计代码如下(C++)：

class MyCircularQueue {
private:
  int *data;   // 存放队列数据
  int head;   // 队列头部
  int tail;   // 队列尾部
  int len;  // 队列长度
  int count;  // 队列内部元素个数
public:
  /** 在此初始化数据结构，将队列长度设置为k **/
  MyCircularQueue(int k) {
    data = new int[k];
    head = 0;
    tail = 0;
    len = k;
    count = 0;
  }
  /** 将元素插入循环队列中，如果成功则返回true **/
  bool enQueue(int value) {
    if(isFull()){  // 循环队列满
      return false;
    } else {  //插入元素到队列尾部
      data[tail] = value;
      count++;
      tail = (tail+1) %len;
      return true;
    }
  }
  /** 从循环队列中删除元素，如果成功则返回true **/
  bool deQueue() {
    if(isEmpty()){  // 循环队列空
      return false;
    } else {
      head = (head + 1) % len;
      count--;
      return true;
    }
  }
  /** 获取队列头部元素 **/
  int Front() {
    if(isEmpty()){  // 循环队列空
      return -1;
    } else {
      return data[head];
    }
  }
  /** 获取队列尾部元素 **/
  int Rear() {
    if(isEmpty()){  // 循环队列空
      return -1;
    } else {
      int temp = tail == 0 ? (len-1) : (tail-1);
      return data[temp];
    }
  }
  /** 检查队列是否为空 **/
  bool isEmpty() {
    return count == 0;  //队列元素个数为0，元素空。
  }
  /** 检查队列是否已满 **/
  bool isFull() {
    return count == len;  // 队列元素个数等于数组最大长度，队列满
  }
};

队列用法

大多数流行语言都提供内置的队列库，因此实际情况我们并不需要重新发明轮子。

队列有着两个重要的操作，入队列和出队列，此外，我们应该能够获得队列中的第一个元素，因为应该首先处理它。

队列和广度优先搜索

队列和 BFS

广度优先搜索（BFS）的一个常见应用就是找出从根节点到目标结点的最短路径，示例来解释 BFS 算法中是如何逐步应用队列的。

1. 结点的处理顺序是什么？
   在第一轮中，我们处理根节点。在第二轮中，我们处理根结点旁边的结点；在第三轮中，我们处理距根节点两步的结点。
   与树的层序遍历类似，越是接近根节点的结点越早遍历。
   如果在第 K 轮中将结点 X 添加到队列中，则根节点与 X 之间的最短路径长度恰好是 K，也就是说，第一次找到目标结点的时候，你已经处于最短路径中了。
2. 队列的入队和出队顺序是什么？
   如上面的动画所示，我们首先将根节点排入队列。然后在每一轮中，我们逐个处理已经在队列中的结点，并将所有的邻居添加到队列中。值得注意的是:新添加的结点不会立即遍历，而是在下一轮中处理。
   结点的处理顺序与他们添加到队列的顺序是完全相同的顺序，即先进先出（FIFO）。这就是我们在 BFS 中使用队列的原因。

广度优先搜索-模版

在特定问题中执行 BFS 之前确定结点和边缘非常重要。通常，结点将是实际结点或是状态，而边缘将是实际边缘或可能的转换。

模版如下(伪代码格式)：

/**
 * 返回根节点和目标节点之间最短路径的长度。
 */
int BFS(Node root, Node target) {
  Queue<Node> queue;  // 存储所有等待处理的节点
  int step = 0;     // 从根到当前节点所需的步骤数
  // 初始化
  add root to queue;
  // BFS（广度优先搜索）
  while (queue is not empty) {
    step = step + 1;
    // 迭代队列中已经存在的节点
    int size = queue.size();
    for (int i = 0; i < size; ++i) {
      Node cur = the first node in queue;
      return step if cur is target;
      for (Node next : the neighbors of cur) {
        add next to queue;
      }
      remove the first node from queue;
    }
  }
  return -1;    // 从根到目标没有路径
}

1. 如代码所示，在每一轮中，队列中的结点是等待处理的结点。
2. 在每个更外一层的 while 循环之后，我们距离根结点更远一步。变量 step 指示从根结点到我们正在访问的当前结点的距离。

有时，确保我们永远不会访问一个结点两次很重要。否则，我们可能陷入无限循环。如果是这样，我们可以在上面的代码中添加一个哈希集来解决这个问题。这是修改后的伪代码：

/**
 * 返回根节点和目标节点之间最短路径的长度。
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // 存储所有等待处理的节点
    Set<Node> used;     // 存储所有使用的节点
    int step = 0;       // 从根到当前节点所需的步骤数
    // 初始化
    add root to queue;
    add root to used;
    // BFS（广度优先搜索）
    while (queue is not empty) {
        step = step + 1;
        // 迭代队列中已经存在的节点
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                if (next is not in used) {
                    add next to queue;
                    add next to used;
                }
            }
            remove the first node from queue;
        }
    }
    return -1;    // 从根到目标没有路径
}

有两种情况你不需要使用哈希集：1.你完全确定没有循环，例如，在树遍历中；2.你确实希望多次将结点添加到队列中。

岛屿数量

给你一个由’1’(陆地)和’0’(水)组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

使用广度优先搜索方式进行搜索

思想：遍历所有的网格，遇到 1，我们就认为遇到了一个岛屿，然后对岛屿的其他范围进行搜索，通过广度优先，对相邻的每个元素进行遍历，如果遇到元素值为 1 的则加入队列。知道队列为空。
我们要将遍历过的值归零。这样所有的都为 0 即结束。

代码如下所示(C++)：

class Solution {
public:
  int numIslands(vector<vector<char>>& grid) {
    // 获取数组的行数和列数
    int rows = grid.size();
    int cols = 0;
    if(rows ==0){
      return 0;
    }else{
      cols = grid[0].size();
    }
    int nums = 0;  // 初始化岛屿数量
    queue<pair<int,int>> Q;
    // 遍历数组的每一个元素
    for(int i = 0; i < rows; i++){
      for(int j = 0; j < cols; j++){
        if(grid[i][j] == '1'){  // 若当前元素值为1
          nums++;  // 岛屿数量加一
          Q.push(make_pair(i,j));
          grid[i][j] = '0';  // 将当前元素值设为0，表示已经访问
          // 循环迭代直到队列为空
          while(!Q.empty()){
            pair<int,int> node = Q.front();
            Q.pop();
            int row = node.first, col = node.second;
            // 遍历上下左右四格，若有元素值为1则加入队列
            if(row + 1 < rows && grid[row+1][col] == '1'){
              Q.push(make_pair(row+1,col));
              grid[row+1][col] ='0';
            }
            if(col + 1 <cols && grid[row][col+1] == '1'){
              Q.push(make_pair(row,col+1));
              grid[row][col+1] ='0';
            }
            if(row - 1 >= 0 && grid[row-1][col] == '1'){
              Q.push(make_pair(row-1,col));
              grid[row-1][col] ='0';
            }
            if(col - 1 >= 0 && grid[row][col-1] == '1'){
              Q.push(make_pair(row,col-1));
              grid[row][col-1] ='0';
            }
          }
        }
      }
    }
    return nums;
  }
};

声明：本文为学习记录，参考之处较多，如果有侵权内容，请联系我立即删除。