【数据结构】数组队列的简单实现

队列的定义：

队列是一种先进先出的线性数据结构，相比与数组，队列对应的操作是数组的子集，只能从一端（队尾）添加元素，也只能从另一端（队首）取出元素。

--------------------------------------------------------------------------------------------------------------------------------------------------------------

（一）定义接口

Queue（E）

①void enqueue（E）

向队尾添加一个元素，入队  

②E dequeue（）

取出队首的元素,出队

③E getFront（）

查看队首的元素

④int getSize（）

查看队列中元素个数

⑤boolean isEmpty（）

判断队列是否为空

（二）接口的实现类

ArrayQueue<E>

导入前面我已经封装好的动态数组Array类，基本操作都是复用该类的方法实现的。

------------------------------------------------------------------------------------------------------------------------------------------------

public class ArrayQueue<E> implements Queue<E> {
	private Array<E> array;

	// 构造函数
	public ArrayQueue(int capacity) {
		array = new Array<E>(capacity);
	}

	// 构造函数
	public ArrayQueue() {
		array = new Array<E>();
	}

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

	// 查看队列的空间大小
	public int getCapacity() {
		return array.getCapacity();
	}

	@Override
	// 查看队列是否为空
	public boolean wsEmpty() {
		return array.isEmpty();
	}

	public String toString() {
		StringBuilder sb = new StringBuilder();
		sb.append("Queue:").append("队首 [");
		for (int i = 0; i < array.getSize(); i++) {
			sb.append(array.query(i));
			if (i != array.getSize() - 1)
				sb.append(", ");
		}
		sb.append("] 队尾");
		return sb.toString();
	}
}

 

我们知道，数组队列有一个很严重的弊端，在出队时删除头元素，相当于使数组后面的元素全部往前挪一位，即数组进行覆盖操作，其复杂度为O（n），在下一篇我将用循环队列解决这个弊端。