Java实现基本数据结构（三）——队列

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

public class ArrayQueue<E> implements Queue<E> {  // 泛型
	
	// 定义一个数组用来存储队列中的元素
	private ArrayList<E> array;

	// 无参构造，直接使用ArrayList类中定义的无参默认值
	public ArrayQueue() {
		array = new ArrayList<E>();
	}

	// 有参构造，指定初始队列容量
	public ArrayQueue(int capacity) {
		array = new ArrayList<E>(capacity);
	}
	
	// 返回栈的元素个数，其实就是返回array的元素个数，调用array中的getSize()方法即可
	@Override
	public int getSize() {
		return array.getSize();
	}

	// 返回栈的总体容量大小，同上，就是返回array的容量空间
	public int getCapacity() {
		return array.getCapacity();
	}
	
	// 返回栈是否为空，其实就是返回array是否为空，调用array中的isEmpty()方法即可
	@Override
	public boolean isEmpty() {
		return array.isEmpty();
	}
	
	/* 
	 * 将元素e入队，实际上就是向数组中添加元素。
	 * 由于队列的特性，只能从数组一端添加元素，为了高效，就限定只能从数组尾部添加即可。
	 * 用户调用enqueue函数时，就永远只能从数组尾部插入数据，满足了队列的条件。
	 */
	@Override
	public void enqueue(E e) {
		array.addLast(e);
	}

	/*
	 * 从队列将队首元素出队，其实就是将队首元素删除并返回。
	 * 由于添加的时候是从数组尾部添加的，所以这里只需要从数组头部删除元素即可。
	 * array中的删除函数，我们已经完成了将删除的元素返回，直接使用即可。
	 */
	@Override
	public E dequeue() {
		return array.removeFirst();
	}

	/*
	 * 查看队首元素，就是将数组头部的元素返回即可。
	 * 由于ArrayList中我们没有定义一个直接返回数组头部的函数。
	 * 所以需要使用array.get()函数，再将头部索引0传入即可。
	 */
	@Override
	public E getFront() {
		return array.get(0);
	}
	
	// 覆盖toString函数，便于输出栈的信息
	@Override
	public String toString() {
		
		StringBuilder res = new StringBuilder();
		res.append("Queue: front [");
		for (int i = 0; i < array.getSize(); i++) {
			res.append(array.get(i));
			if (i != array.getSize() -1) {
				res.append(", ");
			}
		}
		res.append("] rear");
		return res.toString();

	}
	
}

public class Main {

	public static void main(String[] args) {
		
		ArrayQueue<Integer> queue = new ArrayQueue<Integer>();
		for (int i = 0; i < 5; i++) {
			queue.enqueue(i);
		}
		System.out.println(queue);
		
		int a = queue.dequeue();
		System.out.println("delect " + a);
		System.out.println(queue);
		
		int b = queue.getFront();
		System.out.println("front is " + b);
		System.out.println(queue);
		
		queue.enqueue(100);
		System.out.println(queue);
		
	}

}

package Queue;

public class LoopQueue<E> implements Queue<E>{
	
	// 定义一个数组，用来存储元素
	private E[] data;
	// 定义队首和队尾指针
	private int front, tail;
	// 定义一个记录队列中元素数量的变量
	private int size;
	
	// 构造函数，用户可以自定义初始容量
	public LoopQueue(int capacity) {
		data = (E[])new Object[capacity];
		front = 0;
		tail = 0;
		size = 0;
	}
	
	// 无参构造，容量初始默认为10	
	public LoopQueue() {
		this(10);
	}
	
	// 获取当前队列的总容量
	public int getRealCapacity() {
		// 由于循环队列中需要预留一个空间保证入队时tail不和front重合，所以总容量是数组长度-1
		return data.length - 1;
	}

	// 获取当前队列中元素数量
	@Override
	public int getSize() {
		return size;
	}

	// 判断当前队列是否为空
	@Override
	public boolean isEmpty() {
		return front == tail;
	}

	// 入队操作
	@Override
	public void enqueue(E e) {
		
		// 入队之前判断是否队列已满，如果队列已满就先扩容再入队
		if ((tail + 1) % data.length == front)
			resize(data.length * 2);
		data[tail] = e;
		size ++;
		// 更新队尾指针的索引
		tail = (tail + 1) % data.length;
		
	}
	
	// 私有的扩容函数，不对外开放
	private void resize(int newCapacity) {
		
		// 建一个新的数组，空间是newCapacity
		E[] newData = (E[])new Object[newCapacity];
		// 将原本队列中的元素按顺序拷贝进新的数组，由于有指针定义队首和队尾，所以直接从newData[0]开始拷贝即可
		for (int i = 0; i < size; i++) 
			newData[i] = data[(front + i) % data.length];
		// 移动指针将队列的存储数组变更为newData
		data = newData;
		// 归位队首队尾指针
		front = 0;
		tail = size; // tail指向最后一个元素的下一个空间
		
	}

	// 出队队首元素并返回改元素
	@Override
	public E dequeue() {
		
		// 首先判断队列是否为空
		if (isEmpty()) 
			throw new IllegalArgumentException("Queue is empty!");
		// 记录队首元素，以便后续返回
		E ret = data[front];
		// 移除队首元素,指针后移,维护size
		data[front] = null;
		front = (front + 1) % data.length;
		size --;
		
		// 为了更好地利用内存空间，如果出队后，队列中的元素数量只占用了数组总容量的1/4，进行缩容操作
		// 这里需要注意的是，缩容后的容量不能为0
		if (size == getRealCapacity() / 4 && getRealCapacity() / 2 != 0)
			resize(getRealCapacity() / 2);
		
		return ret;
		
	}
	
	// 看一下队首元素
	@Override
	public E getFront() {
		
		// 首先判断队列是否为空
		if (isEmpty()) 
			throw new IllegalArgumentException("Queue is empty!");
		
		return data[front];
	}
	
	// 为了方便打印队列信息，重写toString函数
	@Override
	public String toString() {
		
		StringBuilder res = new StringBuilder();
		res.append("LoopQueue: front[");
		for (int i = front; i != tail; i = (i + 1) % data.length) {
			res.append(data[i]);
			if ((i + 1) % data.length != tail) {
				res.append(", ");
			}
		}
		res.append("] tail");
		return res.toString();
		
	}
	
}

public class Main {

	public static void main(String[] args) {
		
		LoopQueue<Integer> queue = new LoopQueue<Integer>();
		for (int i = 0; i < 5; i++) {
			queue.enqueue(i);
		}
		System.out.println(queue);
		
		int a = queue.dequeue();
		System.out.println("delect " + a);
		System.out.println(queue);
		
		int b = queue.getFront();
		System.out.println("front is " + b);
		System.out.println(queue);
		
		queue.enqueue(100);
		System.out.println(queue);
		
	}

}