数据结构之队列

一、了解队列

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

队列是一种先进先出（First In Last Out）的线性表，简称FIFO

允许插入的一端称为队尾，允许删除的一端称为队头

二、队列接口Queue的定义

三、队列的顺序存储结构ArrayQueue的定义
四、代码实现
Queue.java:

public interface Queue<E> {
	int getSize();
	boolean isEmpty();
	void enqueue(E e);
	E dequeue();
	E getFront();
	E getRear();
	void clear();
}

ArrayQueue.java:

public class ArrayQueue<E> implements Queue<E>{
	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();
	}
	public String toString() {
		StringBuilder sb=new StringBuilder();
		sb.append(String.format("ArrayQueue:%d/%d\n", getSize(),list.getCapacity()));
		sb.append("队头 [");
		for(int i=0;i<getSize();i++) {
			if(i==getSize()-1) {
				sb.append(list.get(i));
			}else {
				sb.append(list.get(i)+",");
			}
		}
		sb.append("] 队尾");
		return sb.toString();
	}
}

测试类：

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);
	}

}

结果如下：