什么是队列

像栈一样，队列（queue）也是表。

使用队列插入在一端进行删除则在另一端进行。

比如说键盘进行字母或数字的输入，到显示器上如记事本上输出，其实这就是队列的应用。

队列是只允许在一端进行插入操作，而在另一端删除的线性表。

队列是一种先进先出的线性表，简称FIFO

允许插入的一端是队尾，允许删除的一端是队头。

队列的基本操作是enqueue(人队)，它是在表的末端(叫作队尾( rear))插入一个元素，和

dequeue(出队),它是删除(并返回)在表的开头(叫作队头( front))的元素。下图显示一个队列的

抽象模型。

队列接口Queue的定义：

+int getSize() 获取队列中的元素+boolean isEmpty() 判断队列是否为空+void enqueue() 从队头添加一个元素+E dequeue() 从队尾删除一个元素+E getFront() 获取队头元素+E getRear() 获取队尾元素+E clear() 清空队列

package DS01.动态数组;public interface Queue<E> extends Iterable<E>{    //获取队列中元素的个数    int getSize();    //判断队列是否为空    boolean isEmpty();    //入队一个元素    void enqueue(E e);    //出队一个元素    E dequeue();    //获取队头    E getFront();    //获取队尾    E getRear();    //清空队列    void clear();}

队列的顺序存储结构ArrayQueue的定义：

队列的顺序存储结构——入队操作

Front和Rear一开始都指向队头的前面，此时队列为空，当进入元素是，Front不动，Rear跟随进入的元素进行++。即队尾进入元素。

队列的顺序存储结构——出队操作

从队头开始删除元素，每删除一个元素，后面的元素都向前移动，然后Front不动，Rear–。

队列顺序存储结构的弊端

队列的顺序存储结构本身是由ArrayList实现的

在数据元素入队的时候，相当于在ArrayList表尾添加元素

在数据元素出队的时候，相当于在ArrayList表头删除元素

很明显，入队的时间复杂度0(1).出队的时间复杂度0(n) .

线性表增删数据元素时间复杂符都是O(),但是这个是按平均算的

队列的出队时间复杂度O(),可不是按平均算的，因为每次出队都是0(n)

队列的代码：

package DS01.动态数组;/*队列的顺序存储结构*/import java.util.Iterator;public class ArrayQueue<E> implements Queue<E> {//定义线性表对象list    private ArrayList<E> list;//默认无参构造函数    public ArrayQueue(){        list=new ArrayList<>();    }//    @Override    public int getSize() {        return list.getSize();    }    @Override    public boolean isEmpty() {        return list.isEmpty();    }    @Override    public void enqueue(E e) {        list.addLast(e);    }    @Override    public E dequeue() {        return list.removeFirst();    }    @Override    public E getFront() {        return list.getFirst();    }    @Override    public E getRear() {        return list.getLast();    }    @Override    public void clear() {        list.clear();    }    @Override    public Iterator<E> iterator() {        return list.iterator();    }//使用toSting返回数组的格式    @Override    public String toString() {        StringBuilder sb=new StringBuilder();        sb.append(String.format("ArrayQueue: %d/%d\n",getSize(),list.getCapacity()));        sb.append('[');        if(isEmpty()){            sb.append(']');        }else{            for(int i=0;i<list.getSize();i++){                sb.append(list.get(i));                if(i==list.getSize()-1){                    sb.append(']');                }else{                    sb.append(',');                }            }        }        return sb.toString();    }}

实现代码：

package DS01.动态数组;public class TestArrayQueue {    public static void main(String[] args) {        ArrayQueue<Integer> queue=new ArrayQueue<>();        for(int i=1;i<=15;i++){            queue.enqueue(i);        }        System.out.println(queue);        for(int i=1;i<=10;i++){            queue.dequeue();        }        System.out.println(queue);    }}