数据结构——队列的java实现(一)-使用顺序存储结构(数组)以及实现

队列的定义：

队列(Queue)：是另一种被限制过的线性表，它是固定一端来插入数据元素，另一端只删除元素，也就是说队列中的元素移动是固定的，就像超市收银台一样，一边是进的，一边是出的，而且是先进入的首先获得服务的。

队列是一个特殊的线性表，它只允许在表的前端(front)进行删除操作，只允许在表的后端(rear)进行插入数据。进行插入操作的端称之为队尾，进行删除操作的端称之为队头。对于一个队列来说，每个元素都是从队列的rear端进入队列，然后等待该元素之前的所有元素出队之后，当前元素才能出队，因此队列简称先进先出(FIFO)。

队列不提供从中间任意位置访问元素的方法，也就是说，队列之允许在队列的前端删除元素，在后端插入元素。

数组队列的实现：

代码实现：

Queue.class

package code.ArrayCode;
public interface Queue<E> {

    int getSize();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E getFront();
}

ArrayQueue.class

package code.ArrayCode;

public class ArrayQueue<E> implements Queue<E> {

    private Array<E> array;

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

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

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

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

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

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

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

    @Override
    public String toString(){
        StringBuilder res = new StringBuilder();
        res.append("Queue: ");
        res.append("front [");
        for(int i =0 ; i < array.getSize() ; i++){
            res.append(array.get(i));
            //如果当前size不是最后一个，则添加一个,
            if(i != array.getSize() -1){
                res.append(", ");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}

public class Main {
      public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<Integer>();
        for(int i =0 ; i < 10 ; i++){
            queue.enqueue(i);
            System.out.println(queue);
            //第三个元素的时候出队列
            if(i % 3 ==2){
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

---

测试结果：

Queue: front [0] tail
Queue: front [0, 1] tail
Queue: front [0, 1, 2] tail
Queue: front [1, 2] tail
Queue: front [1, 2, 3] tail
Queue: front [1, 2, 3, 4] tail
Queue: front [1, 2, 3, 4, 5] tail
Queue: front [2, 3, 4, 5] tail
Queue: front [2, 3, 4, 5, 6] tail
Queue: front [2, 3, 4, 5, 6, 7] tail
Queue: front [2, 3, 4, 5, 6, 7, 8] tail
Queue: front [3, 4, 5, 6, 7, 8] tail
Queue: front [3, 4, 5, 6, 7, 8, 9] tail

---

数组队列的时间复杂度：