循环队列

定义一个接口

public interface Queue<E> {
    //计算队列的大小
    int getSize();
    //判空
    boolean isEmpty();
    boolean contains(E e);
    //入队
    void enqueue(E e);
    //出队
    E dequeue();
    //获得队首元素
    E getFront();
}

定义一个类，继承该接口

/**
 * 循环队列
 * @author hcc
 *
 * @param <E>
 *  规定数组的开始为队首 数组的末尾为队尾 （数据从队尾进入，队首出去）
 */
public class HLoopQueue<E> implements Queue<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private E[] data;
    private int front;
    private int tail;
    private int size;
    public HLoopQueue() {
        this(DEFAULT_CAPACITY);
    }
    
    @SuppressWarnings("unchecked")
    public HLoopQueue(int capacity) {
        data = (E[]) new Object[capacity];
        front = 0;
        tail = 0;
        size = 0;
    }
    
    /**
     * @return 队列的容量
     */
    public int getCapacity() {
        return data.length;
    }
    
    @Override
    public int getSize() {
        // TODO Auto-generated method stub
        return size;
    }

    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        if(front == tail) {
            return true;
        }
        return false;
    }
    /**
     * 判断队列是否已满
     * @return true表示已满 false表示未满
     */
    public boolean isFull() {
//      if(front == ((tail+1)%getCapacity())) {
//          return true;
//      }
//      return false;
        return front == ((tail+1)%getCapacity());
    }
    
    @Override
    public boolean contains(E e) {
        // TODO Auto-generated method stub
        if(e != null) {
            for(int i=0;i<size;i++) {
                if(data.equals(e)) {
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public void enqueue(E e) {
        // TODO Auto-generated method stub
        if(e == null) {
            throw new IllegalArgumentException("空指针异常！");
        }
        if(isFull()) {
            //TODO 扩容
            resize(getCapacity()*2);
        }
        data[tail] = e;
        tail = ((tail+1)%getCapacity());
        size++;
    }

    @Override
    public E dequeue() {
        // TODO Auto-generated method stub
        if(isEmpty()) {
            throw new IllegalArgumentException("队列为空！");
        }
        E e = data[front];
        data[front] = null;
        front = ((front+1)%getCapacity());
        size--;
        int capacity = getCapacity();
        if(size == capacity/4 && capacity/2 != 0) {
            resize(capacity/2);
        }
        return e;
    }

    @Override
    public E getFront() {
        // TODO Auto-generated method stub
        if(isEmpty()) {
            throw new IllegalArgumentException("队列为空！");
        }
        E e = data[front];
        return e;
    }
    
    /**
     * 修改队列的容量
     * @param capacity
     */
    @SuppressWarnings("unchecked")
    private void resize(int capacity) {
        E[] e = (E[]) new Object[capacity];
        int i = 0;
        while(front != tail) {
            e[i] = this.data[front];
            i++;
            front = (front+1)%getCapacity();
        }
        data = e;
        front = 0;
        tail = size;
    }
    
    public String toString() {
        StringBuilder str = new StringBuilder();
        str.append("HLoopQueue(循环队列):");
        str.append(" Front: ");
        str.append("[");
        for(int i = 0;i < size;i++) {
            if(i == (size-1)) {
                str.append(data[i]);
                str.append("]");
                break;
            }
            str.append(data[i]);
            str.append(",");
        }
        str.append(" Tail");
        return str.toString();
    }
}