栈与队列(1)—队列与循环队列

1、先入先出的数据结构—队列

在一般的数据结构—队列中，我们一般将插入(insert)称为入队(enqueue)；新元素一般都被添加至队列的末尾以等待前面元素完成出队。而其中，删除(delete)一般称为出队(dequeue)，此时你只能移除第一个元素。

上图取自力扣图片，它很明确的提及上述的知识点。

1.1 队列的实现

队列的实现一般使用动态数组和指向队列头部的索引即可。

首先，队列应该支持两种操作：入队和出队。

入队能够追加一个新元素放置于元素，而出队会删除第一个元素。

import java.util.ArrayList;
import java.util.List;

public class queue {
    //1.设置一个List集合
    private List<Integer> data;
    //2.设置一个起始索引
    private int p_start;
    //3.在构造方法初始化队列
    public queue(){
        data = new ArrayList<Integer>();
        p_start = 0;
    }
    //4.添加入队方法，添加元素于队列中。如果操作完成返回一个True
    public boolean enQueue(int x){
        data.add(x);
        return true;
    }
    //5.删除队列元素，如果操作成功返回一个True
    public boolean dequeue(){
        if(isEmpty()==true){
            //此时队列为空
            return false;
        }
        p_start++;
        return true;
    }
    //6.此方法获取队列里的元素
    public int front(){
        return data.get(p_start);
    }
    //7.此方法判断是否为空（当索引大于List队列的长度）
    public boolean isEmpty(){
        return p_start >= data.size();
    }

1.2 队列的优缺点

在这里，我们使用List集合和索引的搭配使用来构造如上的队列。

优点：能够完成一个队列的实现
缺点：随着数据的不断增多，队列的空间开销越来越大，成本越来越高。

2、简单的实战教学—循环队列

class MyCircularQueue {
    int[] data;
    private int tail;//tail用于增添元素
    private int front;//front用于删除元素

    //构造函数，初始化属性值
    public MyCircularQueue(int k) {
        data = new int[k+1];
        front = 0;
        tail = 0;
    }
    //插入元素
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }else {
            data[tail]=value;
            tail=(tail+1)%data.length;
            return true;
        }
    }
    //删除元素
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }else{
           front = (front + 1) % data.length;
            return true;
        }
    }
    //获取头元素
    public int Front() {
        if(isEmpty()){
            return -1;
        }else{
            return data[front];
        }
    }
    //获取尾元素
    public int Rear() {
        if(isEmpty()){
            return -1;
        }else{
            return data[(tail - 1 + data.length) % data.length];
        }
    }
    //判空
    public boolean isEmpty() {
        return front==tail;
    }
    //判满
    public boolean isFull() {
        return (tail+1)%data.length==front;
    }
}

首先说明以下思路点：

• tail=(tail+1)%data.length;的目的在于能够使得tail在数组即将越界时能够返回最开始的地方，因为中间是取余符号。
• (tail - 1 + data.length) % data.length作为获取尾部元素在于它要-1以获取当前最后数组下标，并且作为取余也是因为tail可能会指向最开始的地方。

3、广度优先算法

广度优先算法BFS主要是找出从根节点到目标节点的最短路径。

首先介绍原理：第一轮首先是处理根节点，其次是处理根节点旁边的节点，再次就是处理距离根节点两步的节点等等，即越是接近根结点的结点将越早地遍历。

其次，这里使用的是队列将根节点排入队列中。在每一轮逐个处理在队列中的节点，将其邻居节点添加到队列上。

3.1 广度优先算法代码介绍

/**
 * 返回根节点和目标节点的最短路径
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // 设置装入Node节点的队列
    int step = 0;       // 设置当前步骤为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
}

如上伪代码展示的是广度优先算法的基本步骤。

后续本文将会根据队列分享几道leetcode题目，请大家后续关注小编对leetcode基础题的介绍，谢谢大家的观看。