数据结构-队列

数据结构-队列

 队列是一种限定为从一端从另进一端出（FIFO）的线性表。从一段插入元素的过程称为入队或进队， 从另一端取出一个元素称为出队。

 每次入队在队尾插入新的元素，每次出队时在队首取出一个元素。

利用数组实现的队列

使用数组实现队列时，需要预先设定好队列长度（length）， 初始化一个数组array[]，将指向第一个元素的指针（size）默认为0。进行入队 *** 作时数据以此向数组尾部递进，每添加一个元素后，size指针都是指向下一连续空间，当size = length 时，队满。出队时只需取出数组下标为i = 0的元素，然后将后面的所有元素依次往前移动一个位置（array[i] = array[i + 1]）, 这样做的好处时避免出队时每次取出队首元素后，队首前还存在一片不能使用的地址空间，所以我们需要将浪费掉的空间使用起来。

 

public class ArrayQueue {

    private static final int DEFAULT_SIZE = 128;

    
    private T[] dataArray;

    
    private int size;
    
    private int length;

    
    public ArrayQueue(Class type, int size) {
        dataArray = (T[]) Array.newInstance(type, size);
        this.size = 0;
        length = size;
    }

    
    public ArrayQueue(Class type) {
        this(type, DEFAULT_SIZE);
    }

    
    public void add(T val) {
        dataArray[size++] = val;
    }

    
    public T getFirst() {
        return dataArray[0];
    }

    
    public T pop() {
        T ret = dataArray[0];
        size--;
        for (int i = 0; i < size; i++) {
            dataArray[i] = dataArray[i + 1];
        }
        return ret;
    }

    
    public int size() {
        return size;
    }

    
    public boolean isEmpty() {
        return size == 0;
    }

    
    public int length(){
        return length;
    }

}

从上面的 出队方法可得知

    public T pop() {
        T ret = dataArray[0];
        size--;
        for (int i = 0; i < size; i++) {
            dataArray[i] = dataArray[i + 1];
        }
        return ret;
    }

 每次出队时后面的所有元素都需要移动， 如果存在频繁出队的 *** 作时，很影响效率，如何提高效率呢？如果将数组的首尾相连，每次入队和出队只做简单的++和--，这样就不存在数据移动了，因此可以使用循环队列来提高出队效率。

循环队列

        为了解决数组队列出队时需要移动元素的问题， 提出来循环队列。将一个数据逻辑上首位相接就构成了循环队列。这样虽然不需要移动元素， 但是会牺牲掉一个空间来判断队列状态（队空和对满）。

定义头指针front， 初始化时头指针指向0号空间；

定义尾指针rear， 初始化时尾指针指向0号空间；

当front = rear时， 队空；

入队 *** 作： array[rear++] = data;

出队 *** 作： return array[front++]；

当rear + 1 = front时，队满；

注：当头尾指针指向下一圈开始时， 我们不让指针号一直递增下去， 我们通常用当前指针除以循环队列长度的模作为指针的新符合，例如：rear = rear % maxSize。

 由于数据沾满数组空间时， 此时rear是指向下一个位置的，也就是指向了front所在的位置，此时rear = front，而前面我们初始化空队时front = rear = 0， 也就是说无论对满和队空时头指针和尾指针都是相等的，所以为了了解队列状态， 我们将牺牲一个空间作为标识， 当rear + 1 = front时队满，当 rear = front时队空。 

 

 这样的循环队列只要队不满就可以一直使用了，但是我们如何确定队列元素长度呢？

 存在两种情况：

        1. 若当前状态下，front <= rear时，长度为 rear - front；

        2. 若front > rear时， 长度为maxSize - (front - rear) ；

java实现循环队列：

public class LoopQueue {

    private static final int DEFAULT_SIZE = 128;

    
    private T[] queueList;

    
    private int front;
    
    private int rear;
    
    private int maxSize;

    
    public LoopQueue(Class type) {
        this(type, DEFAULT_SIZE);
    }

    public LoopQueue(Class type, int size) {
        queueList = (T[]) Array.newInstance(type, size + 1);
        rear = 0;
        front = 0;
        // 多分配一个空间用于确定队满和队空情况
        maxSize = size + 1;
    }

    
    public boolean isEmpty() {
        return front == rear;
    }

    
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    
    public Object getFront() {
        return queueList[front];
    }

    
    public void push(T val) {
        if (isFull()) {
            throw new IndexOutOfBoundsException();
        }
        // 入队 *** 作. 队满时抛出异常
        queueList[rear] = val;
        rear = (rear + 1) % maxSize;
    }

    
    public T pop() {
        if (isEmpty()) {
            return null;
        }
        T result = queueList[front];
        front = (front + 1) % maxSize;
        return result;
    }

    
    public int size() {
        // 1. 当头指针小于尾指针时，长度：len1 = rear - front
        // 2. 当头指针大于尾指针时，说明队列从第二圈开始了,
        //    空元素段为：front - rear 所以有元素段 maxSize - (front - rear) => len2 = maxSize + front - rear
        // 3. 利用同一个表达式表示这两种情况,其中n表示整数常量： (rear - front) + (n * maxSize) % maxSize
        return (rear - front + maxSize) % maxSize;
    }


}

 链表实现队列

利用链表结构可以很容易实现队列，入队时在队位添加元素， 出队时删除队首元素。但是链表不像数组那样可以直接定位到队尾位置， 导致每次入队时都要从队首开始找，具体实现如下。

代码中的SinglelinkedList是我已经写好的单链表数据结构，直接创建后调用链表的基础 *** 作方法即可实现先进先出的队列结构。 想要了解SinglelinkedList的代码请戳这个链接：java实现单链表和双链表数据结构_Huzz童年的纸飞机的博客-CSDN博客

当然，你也可以使用java自带的链表来创建队列。

public class Queue {

    private SinglelinkedList linkedList;

    private int size;

    public Queue() {
        linkedList = new SinglelinkedList();
        size = 0;
    }

    
    public void add(T data) {
        linkedList.append(data);
        size++;
    }

    
    public int size() {
        return this.size;
    }

    
    public T get() {
        T result = linkedList.getFirst();
        linkedList.del(0);
        size--;
        return result;
    }

    
    public void del() {
        linkedList.del(0);
        size--;
    }

}