3 数据结构之队列

3.1 什么是队列

Queue也是一种线性结构，相比数组，队列的操作是数组的子集。

只能从队尾添加元素，从队首取出元素。

和生活中的排队是一样的，先到先得。

 

 LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。下面我们用上一节的动态数组来实现自己的队列这种数据结构。

3.2 队列的基本实现

有了实现栈的经验，现在实现队列会比较容易些。

先写队列的接口Queue.java

public interface Queue
     
       {    void enqueue(E e); // 入队列    E dequeue(); //出队列    E getFront();  //获取队首元素    int getSize(); //获取队列中元素个数    boolean isEmpty();}
     

 

然后实现这些接口，同样基于上一节实现的动态数组。

public class ArrayQueue
     
       implements Queue
      
        {    private Array
       
         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();    }}
       
      
     

这样我们的队列就实现了

 

代码: https://github.com/zhang-anan/DataStructure/tree/master/src/cc/myall/demo03