算法入门之队列

前言

队列和栈及其类似，队列在现实生活中的例子就是隧道，单通道一条线，先进去的先出来，后进去的后出来。

在算法中的队列也是这样

队列中从队头位置出队，从队尾入队，队列中的元素永远是先入先出FIFO（简称First In First Out）。

队列的实现方式同样有两种数组和 链表 ，实现队列的结构图如下（上面是数组实现，下面是链表实现）

链表实现队列

链表实现队列主要就是依靠队头指针和队尾指针，整个实现方式分为两个，入队和出队。

• 入队：就是将队尾指针的next指针指向新的Node节点。
• 出队：就是将队头指针指向原队头指针的下一个Node节点。

代码输出如下

 /**
 * 链表实现队列
 */class MyQueue1{
    /**
     * 队头指针用于出队
     */     private  Node head;
    /**
     * 队尾指针用于入队
     */    private Node last;
    /**
     * 链表元素个数
     */    private int size;
    // 队尾插入
    public  void  push(Object data){
         Node  node = new Node(data);
        if (size == 0){
            head = node;
            last = node;
        }else {
            last.next = node;
            last = node;
        }
        size++;
    }
    // 队头出队
    public Object pull(){
        if (size == 0){
            throw new Runtime Exception ("队列空无法出队");
        }
        Object object = head.data;
        Node temp = head;
        head = head.next;
        temp.next = null;
        size--;
        return object;
    }
    public void show(){
        Node temp = head;
        while (temp!=null){
            System.out.println(temp);
            temp = temp.next;
        }
    }
}
class Node{
    Object data;
    Node next;
    public Node(Object data){
        this.data = data;
        this.next = null;
    }
    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", next=" + next +
                '}';
    }
}
  

用链表实现队列那么入队出队时仅仅只需要移动队头指针和队尾指针那么时间复杂度为O(1)。

普通数组实现队列

数组实现队列稍微有点繁琐，当元素入队时就是将数组队尾的下一个位置赋值为指定元素，如下

当元素出队时就是从队头位置删除一个元素，剩余元素需要向前移动一个元素的位置，如下

根据结构图可以得到如下代码

 /**
 * 普通数组实现队列
 */class MyQueue2{
    private Object[] arr;
    private int size;
    public MyQueue2(int capacity){
        arr = new Object[capacity];
        size = 0;
    }
    // 队尾插入
    public void push(Object data){
        if (size == arr.length){
            throw new RuntimeException("队列已满！");
        }
        arr[size] = data;
        size++;
    }
    // 队头出队
    public Object pull(){
        if (size == 0){
            throw new RuntimeException("队列为空！");
        }
        Object obj = arr[0];
        // 移动元素
        for (int i = 0; i <size-1 ; i++) {
            arr[i] = arr[i+1];
            // 移动后的元素位置可以置空
            arr[i+1] = null;
        }
        size--;
        return obj;
    }
    public void show(){
        System.out.println(Arrays.toString(arr));
    }
}
  

我们可以看到用数组实现的队列中，如果元素出队，那么数组中的其它元素全部需要向前移动，那么时间复杂度为O(n)，相比较链表而言数组的实现方式效率差很多，那么有没有办法去优化这个逻辑呢？有！循环队列。

循环队列

循环队列和普通数组实现队列的区别在于队头指针不再是固定，元素删除后队头指针会移动，队尾指针指向的是最后入队元素的下一个位置，如下

当元素入队时队尾指针（队尾的下标）计算公式为

(队尾下标+1)%数组长度

所以插入结构如下

什么时候判断队列已满呢？当**(队尾下标+1)%数组长度 == 队头下标**时队列已满，这也就说明队列存放的个数是比数组的真实长度小1。

而元素出队就是队头下标向前移动一个位置，同时将原队头位置的元素清空即可

根据思路可以整理出如下代码

 /**
 * 因为用数组实现的队列需要移动元素太过于麻烦时间复杂度为O(n)，所以这里优化
 * 循环队列
 */class MyQueue3{
    private Object[] arr;
    // 队头下标
    private int front;
    // 队尾下标
    private int rear;
    public MyQueue3(int capacity){
        arr = new Object[capacity];
    }
    /**
     * 入队
     * @param data
     * (队尾下标+1)%arr.length == front表示队列已满
     */    public void push(Object data){
        if ((rear+1)%arr.length==front){
            throw new RuntimeException("队列已满！");
        }
        arr[rear] = data;
        rear = (rear+1)%arr.length;
    }
    /**
     * 出队
     * @return
     */    public Object pull(){
        if (rear == front){
            throw new RuntimeException("队列为空！");
        }
        Object object =  arr[front];
        arr[front] = null;
        front = (front+1)%arr.length;
        return object;
    }
    public void show(){
        System.out.println(Arrays.toString(arr));
    }
}
  

根据代码可以看出，使用循环队列出队的时间复杂度直接从O(n)变为O(1)，效率提升！