数据结构之队列

什么是队列

队列也是一个操作受限的线性表，它还是一种线性表
队列只允许在一头进行添加元素，这头被称为队尾
然后在另一头进行删除元素，这一头被称为队头
它的元素规律是先进先出（First In First Out）FIFO
模拟现实生活，就是我们生活中的排队队列

队列的实现

用什么实现

我们知道队列每次都删除最前面的元素，所以我们用数组这中结构，是非常不方便的，因为数组想要删除最前面的元素，要把后面的元素都往前移动，所以我们用链表实现

接口实现队列的功能

package MyQueue;


public interface Queue {
    void offer(E val);//入队
    E pop();//出队操作
    E peek();//查看队首元素
    boolean isEmpty();//查看队是否为空
}

用链表实现

package MyQueue;

import java.util.NoSuchElementException;

class Node{
    E val;
    Node next;

    public Node(E val) {
        this.val = val;
    }
}
public class QueueList implements Queue {
    private Node head;
    private Node tail;
    private int size;
    @Override
    public void offer(E val) {
        Node node=new Node(val);
        if (head==null){
            head=node;
            tail=node;
        }else {
            tail.next=node;
            tail=node;
        }
        size++;
    }

    @Override
    public E pop() {
       if (isEmpty()){
           throw new  NoSuchElementException("栈为空");
       }else {
           Node node=head;
           E val=head.val;
           head=head.next;
           node.next=node=null;
           size--;
           return val;
       }
    }

    @Override
    public E peek() {
        if (isEmpty()){
            throw new  NoSuchElementException("栈为空");
        }else {
            return head.val;
        }
    }

    @Override
    public boolean isEmpty() {
       return size==0;
    }
    public String toString(){
        StringBuilder sb=new StringBuilder();
        sb.append("front [");
        for ( Node node = head; node!=null; node=node.next) {
            sb.append(node.val);
            if (node.next!=null){
                sb.append(',');
            }
        }
        sb.append("] top");
        return sb.toString();
    }
}

循环队列
什么是循环队列

我们在操作系统中的生产者和消费者，和数据库中的InnoDB存储引擎中的redo日志都是用循环队列实现的。
循环队列就是使用长度固定的数组来实现，用两个指针指向实现队列，一个head指向队首，一个tail指向队尾有效元素的后一个位置
添加元素只需要直接在数组尾部添加，删除元素直接将head后移就行（逻辑删除）
那么[head,tail)就是这个队列的有效元素

为什么叫循环队列

怎么实现这个循环的操作

我们知道想实现这样的循环，每次的操作只是加一肯定是不行的，我们采用取余这个操作符

队列满和队列为空的判断

队列满和队列为空的冲突

如何解决，我们牺牲一个存储空间，来区分队列为满还是为空

代码实现
package MyQueue;

import java.util.NoSuchElementException;

public class LoopQueue implements Queue{
    private Integer[] date;
    //表示定长数组
    private int head;
    //指向头结点
    private int tail;

    public LoopQueue(int size) {
        date=new Integer[size+1];
        //size为要存储数据的个数，因为要浪费一个，所以要多一位空间
    }

    @Override
    public void offer(Integer val) {
        if (isFull()){
            throw new ArrayIndexOutOfBoundsException("队列已经满了");
        }
        date[tail]=val;
        tail=(tail+1)%date.length;
    }

    @Override
    public Integer pop() {
        if (isEmpty()){
            throw new NoSuchElementException("队列为空");
        }
        Integer val=date[head];
       head=(head+1)%date.length;
       return val;
    }

    @Override
    public Integer peek() {
        if (isEmpty()){
            throw new NoSuchElementException("队列为空");
        }
       return date[head];
    }

    @Override
    public boolean isEmpty() {
        return head==tail;
    }
    public boolean isFull(){
        return (tail+1)%date.length==head;
    }
    public String toString(){
        StringBuilder sb=new StringBuilder();
        sb.append("front [");
        int lastIndex=tail==0?date.length-1:tail-1;
        for (int i = head ;i!=tail; ) {
            sb.append(date[i]+" ");
            if (i!=lastIndex){
                sb.append(",");
            }
            i=(i+1)%date.length;
        }
        sb.append("] tail");
        return sb.toString();
    }
}
在打印toString方法中有一个细节

在添加逗号的时候，我们要注意tail=0的这个地方，因为平时最后一个元素是tail-1,tail=0时候，最后一个有效的元素的length-1;

双端队列（Deque)

概念
双端队列（ deque ）是指允许两端都可以进行入队和出队操作的队列， deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队，也可以从队尾出队和入队。
不推荐使用Stack这个类，因为Stack已经被抛弃，它非常低效，都是同步操作
双端队列常用的一个子类就是LinkList

数据结构之队列

Java相关栏目本月热门文章