（三）基本数据结构--队列

一、队列的实现

队列作为最常见的数据结构之一，其作用不言而喻。我将自定义一个队列的类，该队列是基础之前所学习的动态数组实现的。本文实现了数组队列与循环队列两种数据结构。

二、实现内容

队列的增删改查

由于栈是FIFO（first in first out)类型，则栈的增删只存在入队enQueue()和出队deQueue()

三、具体代码实现

循环队列的实现

遇到的问题与调试解决

• 在实现过程中，实现结果与实际不符合。
  运行结果总是多一个null ，经过很长！！的时间的调试发现 （为什么IDEA没有调试时候返回上一步啊！！！！我真的看了好多遍） ，发现在运行过程中resize（）时候发生了逻辑问题。然后一步步推理发现在刚开始resize中 新的数组传递语句顺序有问题

       data = newData;//先传递
       front = 0;此时强行改变了front指针，不影响队首元素
   	   tail = getSize();//由于先给的front
   	              //此时getSize中的返回值与front有关所以报错

则传递后的data front和getsize（）不正确。正确的语句应为

        tail = getSize();
        front = 0;
        data = newData;

• 循环队列相对数组队列来说，空间利用更好

循环队列的代码

package queue;

public class LoopQueue<E> implements Queue<E> {
    private E[] data;
    private int front, tail;

    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
    }

    public LoopQueue() {
        this(10);
    }

    public int getCapacity() {
        return data.length - 1;
    }

    @Override
    public void enqueue(E e) {
        if ((tail + 1) % data.length == front) {
            resize(2 * getCapacity());
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
    }

    @Override
    public E dequeue() {
        if(isEmpty())
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");

        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        if(getSize() == getCapacity() / 4 && getCapacity() / 2 != 0)
            resize(getCapacity() / 2);
        return ret;
    }

    @Override
    public E getFront() {
        return data[front];
    }


    @Override
    public boolean isEmpty() {
        if (getSize() == 0)
            return true;
        return false;
    }

    @Override
    public int getSize() {
        if (tail >= front) return tail - front;
        return (data.length-front +tail);

    }

    public void resize(int newCapacity) {
        E[] newData = (E[])new Object[newCapacity + 1];
        for(int i = 0 ; i < getSize(); i ++)
            newData[i] = data[(i + front) % data.length];


        tail = getSize();
        front = 0;
        data = newData;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue: size = %d , capacity = %d  ", getSize(), getCapacity()));
        res.append("front [");
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            res.append(data[i]);
            if ((i + 1) % data.length != tail)
                res.append(",");
        }
        res.append("]");
        return res.toString();
    }

    public static void main(String[] args) {

        LoopQueue<Integer> queue = new LoopQueue<>();
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.println(queue.toString());

            if (i % 3 == 2) {
                queue.dequeue();
                System.out.println(queue.toString());
            }
        }
    }
}
运行结果：
Queue: size = 1 , capacity = 10  front [0]
Queue: size = 2 , capacity = 10  front [0,1]
Queue: size = 3 , capacity = 10  front [0,1,2]
Queue: size = 2 , capacity = 5  front [1,2]
Queue: size = 3 , capacity = 5  front [1,2,3]
Queue: size = 4 , capacity = 5  front [1,2,3,4]
Queue: size = 5 , capacity = 5  front [1,2,3,4,5]
Queue: size = 4 , capacity = 5  front [2,3,4,5]
Queue: size = 5 , capacity = 5  front [2,3,4,5,6]
Queue: size = 6 , capacity = 10  front [2,3,4,5,6,7]
Queue: size = 7 , capacity = 10  front [2,3,4,5,6,7,8]
Queue: size = 6 , capacity = 10  front [3,4,5,6,7,8]
Queue: size = 7 , capacity = 10  front [3,4,5,6,7,8,9]

数组队列的实现

由于基础Array实现 Array代码在Array的介绍中查看，这里不再赘述。

数组队列的代码

package queue;

import array.Array;

public class ArrayQueue<E> implements Queue<E> {
    private Array<E> array;

    public ArrayQueue(int capacity) {
        array = new Array<>(capacity);
    }

    public ArrayQueue() {
        array = new Array<>();
    }

    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    @Override
    public E getFront() {
        return array.getFirst();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }


    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append("队列的队首为[");
        for (int i = 0; i < array.getSize(); i++) {
            res.append(array.get(i));
            if (i != array.getSize() - 1)
                res.append(",");
        }
        res.append("]");
        return res.toString();
    }