队列抽象数据类型（ADT）全面解析

### 队列抽象数据类型（ADT）全面解析 #### 1. 队列ADT概述 队列ADT是一种线性有序的元素集合，其元素添加到一端（尾部），并从另一端（头部）移除，遵循先进先出（FIFO）原则。它在生活中十分常见，比如学生在食堂排队付款、观众在电影院排队入场、车辆在高速公路入口排队等场景。 队列ADT支持的操作与栈ADT类似，主要操作如下： | 操作 | 描述 | | --- | --- | | clear() | 清空队列 | | isEmpty() | 判断队列是否为空，为空返回true，否则返回false | | peek() | 返回队列头部元素，但不删除它，若队列为空则抛出异常 | | size() | 返回队列中元素的数量 | | add(E element) / enqueue(E element) | 将元素添加到队列尾部 | | remove() / dequeue() | 移除并返回队列头部元素，若队列为空则抛出异常 | #### 2. 队列接口定义 使用Java接口来定义队列ADT，接口名为`NPSQueue`，代码如下： ```java package edu.nps.util; public interface NPSQueue<E> { public void add(E element); public void clear(); public boolean isEmpty(); public E peek() throws NPSQueueEmptyException; public E remove() throws NPSQueueEmptyException; public int size(); } ``` 当队列为空时，`peek()`和`remove()`方法会抛出`NPSQueueEmptyException`异常，其定义如下： ```java package edu.nps.util; public class NPSQueueEmptyException extends RuntimeException { public NPSQueueEmptyException() { this("Queue is empty"); } public NPSQueueEmptyException(String message) { super(message); } } ``` #### 3. 数组实现队列 使用数组实现队列时，需要考虑数组的循环使用，以避免不必要的数组扩容。 ##### 3.1 NPSArrayQueue类定义 ```java package edu.nps.util; public class NPSArrayQueue<E> implements NPSQueue<E> { private static final int DEFAULT_SIZE = 25; private E[] element; private int count; // 队列中元素的数量 private int front; // 要移除元素的位置 private int tail; // 要添加元素的位置 public NPSArrayQueue() { this(DEFAULT_SIZE); } public NPSArrayQueue(int size) { if (size <= 0) { throw new IllegalArgumentException("Initial capacity must be positive"); } element = (E[]) new Object[size]; clear(); } } ``` ##### 3.2 主要方法实现 - **add(E item)方法**： ```java public void add(E item) { // 检查队列是否已满 if (count == element.length) { expand(); } element[tail] = item; tail = (tail + 1) % element.length; count++; } ``` - **expand()方法**： ```java private void expand() { E[] temp = (E[]) new Object[(int)(1.5 * element.length)]; int e_idx = front; int t_idx = front; for (int i = 0; i < count; i++) { temp[t_idx] = element[e_idx]; t_idx = (t_idx + 1) % temp.length; e_idx = (e_idx + 1) % element.length; } tail = t_idx; element = temp; } ``` - **remove()方法**： ```java public E remove() throws NPSQueueEmptyException { E item; if (isEmpty()) { throw new NPSQueueEmptyException(); } else { item = element[front]; element[front] = null; front = (front + 1) % element.length; ```