数据结构(Java语言)——Queue简单实现

时间:2022-04-28 14:32:00

和栈类似,队列queue也是表。然而,使用队列时插入在一端进行而删除在另一端进行。

队列的基本操作是enqueue(入队)和dequeue(出队),入队是在队尾rear(表的末端)插入一个元素,出队是删除在队头front(表的开头)的元素。

和栈一样,对于队列而言任何表的实现都可以,而且对于每种操作,链表实现和数组实现都是快速的O(1)时间。下面主要讨论队列的循环数组实现。

对于每一个队列数组结构,我们保留一个数组theArray[]以及位置front和rear,它们表示队列的两端。我们还要记录实际存在于队列中的元素个数currentSize。为使一个元素x入队,我们执行enqueue()使currentSize和rear增1,然后置theArray[rear]=x。为使元素出队列,我们置返回值为theArray[front],并且currentSize减1,然后使front加1。以下是相关代码实现:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyQueue<AnyType> implements Iterable<AnyType> {
	private static final int DEFAULT_CAPACITY = 10;
	private AnyType[] theArray; // 以数组存放数据
	private int currentSize; // 当前队列的长度,非数组长度
	private int front; // 队头
	private int rear; // 队尾

	/**
	 * 构造函数自动执行clear()函数
	 */
	public MyQueue() {
		clear();
	}

	/**
	 * 分配内存,初始化各成员变量
	 */
	public void clear() {
		ensureCapacity(DEFAULT_CAPACITY);
		currentSize = 0;
		front = rear = 0;
	}

	/**
	 * 返回当前数组长度
	 * 
	 * @return 数组长度
	 */
	public int size() {
		return theArray.length;
	}

	/**
	 * 当前队列是否满
	 * 
	 * @return
	 */
	public boolean isFull() {
		return currentSize == size();
	}

	/**
	 * 当前队列是否空
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return currentSize == 0;
	}

	/**
	 * 根据参数确定数组长度
	 * 
	 * @param newCapacity
	 *            新的大小
	 */
	@SuppressWarnings("unchecked")
	public void ensureCapacity(int newCapacity) {
		// 第一次(数组未分配)直接分配内存
		if (theArray == null) {
			theArray = (AnyType[]) new Object[newCapacity];
			return;
		}
		// 参数小于当前长度直接返回
		if (newCapacity < size()) {
			return;
		}
		// 数组扩充时将原数据复制到新分配的数组里
		AnyType[] old = theArray;
		theArray = (AnyType[]) new Object[newCapacity];
		for (int i = front; i < front + old.length; i++) {
			theArray[i - front] = old[i % old.length];
		}
		// 重新赋值各变量
		front = 0;
		rear = old.length - 1;
		currentSize = old.length;
	}

	/**
	 * 入队操作
	 * 
	 * @param value
	 *            入队元素
	 */
	public void enqueue(AnyType value) {
		// 检查队列是否满
		if (isFull()) {
			ensureCapacity(size() * 2);
		}
		// 第一次入队时队尾无数据,直接赋值。之后队尾先加一取余再赋值
		if (theArray[rear] != null) {
			rear = (rear + 1) % size();
		}
		theArray[rear] = value;
		currentSize++;
	}

	/**
	 * 出队操作
	 * 
	 * @return 出队元素
	 */
	public AnyType dequeue() {
		// 若队列空则无法出队
		if (isEmpty()) {
			throw new NullPointerException();
		}
		// 出队操作
		currentSize--;
		AnyType value = theArray[front];
		theArray[front] = null;
		front = (front + 1) % size();
		return value;
	}

	/**
	 * 实现Iterable接口
	 */
	public Iterator<AnyType> iterator() {
		return new QueueIterator();
	}

	private class QueueIterator implements Iterator<AnyType> {

		private int current = 0;

		public boolean hasNext() {
			return current < size();
		}

		public AnyType next() {
			if (!hasNext()) {
				throw new NoSuchElementException();
			}
			return theArray[current++];
		}

	}

	public static void main(String[] args) {
		MyQueue<Integer> queue = new MyQueue<Integer>();
		Iterator<Integer> iterator1 = queue.iterator();
		Iterator<Integer> iterator2 = queue.iterator();
		queue.enqueue(1);
		queue.enqueue(2);
		queue.enqueue(3);
		queue.enqueue(4);
		queue.enqueue(5);
		queue.enqueue(6);
		queue.enqueue(7);
		queue.enqueue(8);
		queue.enqueue(9);
		queue.enqueue(10);
		queue.dequeue();
		queue.dequeue();
		queue.dequeue();
		queue.dequeue();
		queue.enqueue(11);
		queue.enqueue(12);
		System.out.println("队列未超出容量时结果:");
		while (iterator1.hasNext()) {
			System.out.print(iterator1.next() + " ");
		}
		System.out.println("\n队列超出容量时结果:");
		queue.enqueue(13);
		queue.enqueue(14);
		queue.enqueue(15);
		while (iterator2.hasNext()) {
			System.out.print(iterator2.next() + " ");
		}
	}
}
执行结果:

队列未超出容量时结果:
11 12 null null 5 6 7 8 9 10 
队列超出容量时结果:
5 6 7 8 9 10 11 12 13 14 15 null null null null null null null null null