队列 Queue
|
|
|
1. 队列Queue 定义： 队列又叫做FIFO（先进先出）表，即first-in，first-out 现实中的队列 ——排队
队列的接口 public interface QueueInterface<T> {
/**
* 将新元素插入队列后端
* @param newEntry 待插入的对象 */
public void enqueue(T newEntry);
/**
* 删除并返回队列前端对象
* @return 位于队列前端的对象，如果队列为空则返回null */
public T dequeue();
/**
* 检索队列前端对象
* @return 位于队列前端的对象，如果队列为空则返回null */
public T getFront();
/**
* 检查队列是否为空
* @return 如果队列为空则返回true */
public boolean isEmpty();
/**
* 从队列中删除所有元素 */
public void clear();
}Java类库：Queue接口 public interface Queue<T> {
// 在对象的末端插入一个新元素，如果插入成功则返回true，否则抛出一个异常
public boolean add(T newEntry);
// 在对象的末端插入一个新元素，根据此操作成功与否返回true或false
public boolean offer(T newEntry);
// 在队列的前端检索并删除元素，如果在此操作之前队列已为空，则抛出异常NoSuchElementException
public T remove();
// 在队列的前对检索并删除元素，如果在此操作之前队列已为空，则返回null
public T poll();
// 检索队列前端的元素，如果队列为空，则抛出异常NoSuchelementException
public T element();
// 检索队列前端的元素，如果队列为空，则返回null
public T peek();
// 检索队列是否为空
public boolean isEmpty();
// 删除队列的所有元素
public void clear();
// 获得当前队列中的元素数据
public int size();
// 返回作用于队列的元素的迭代期器
public Iterator<T> iterator();
}双端队列接口描述 public interface DequeInterface<T> {
public void addToFront(T newEntry);
public void addToBack(T newEntry);
public T removeFront();
public T removeBack();
public T getFront();
public T getBack();
public boolean isEmpty();
public void clear();
}优先队列的接口描述 public interface PriorityQueueInterface<T extends Comparable<? super T>> {
/**
* 将新元素插入优先队列
* @param newEntry newEntry一个对象 */
public void add(T newEntry);
/**
* 删除并返回优先队列最高的元素
* @return 优先级最高的对象，如果优先队列为空则返回null */
public T remove();
/**
* 检索优先级最高的元素
* @return 优先级最高的对象，如果优先队列为空则返回null */
public T peek();
/**
* 检索优先队列是否为空
* @return 如果优先队列为空则返回true */
public boolean isEmpty();
/**
* 缺德优先队列的长度
* @return 当前优先队列中的元素数据 */
public int getSize();
/**
* 从优先队列中删除所有元素 */
public void clear();
}2. 基于(双端)链表的队列实现
public class LinkedQueue<T> implements QueueInterface<T>, Serializable {
private Node firstNode; // 引用队列前端的结点
private Node lastNode; // 引用队列后端的结点
public LinkedQueue() {
firstNode = null;
lastNode = null;
}
private class Node implements Serializable {
private T data; // entry in queue
private Node next; // link to next queue
}
// 在后端插入
public void enqueue(T newEntry) {
Node newNode = new Node(newEntry, null);
if (isEmpty())
firstNode = newNode;
else
lastNode.setNext(newNode);
lastNode = newNode;
}
// 删除前端元素
public T dequeue() {
T front = null;
if (!isEmpty()) {
front = firstNode.getData();
firstNode = firstNode.getNext();
if (firstNode == null)
lastNode = null;
}
return front;
}
// 检索前端元素
public T getFront() {
T front = null;
if (!isEmpty())
front = firstNode.getData();
return front;
}
public boolean isEmpty() {
return firstNode == null;
}
public void clear() {
firstNode = null;
lastNode = null;
}
}3. 基于(循环)数组的队列实现
public class ArrayQueue<T> implements QueueInterface<T>, Serializable {
private T[] queue; // 存放队列元素的循环数组
private int frontIndex;
private int backIndex;
private static final int DEFAULT_INITIAL_CAPACITY = 50;
public ArrayQueue() {
this(DEFAULT_INITIAL_CAPACITY);
}
public ArrayQueue(int initialCapacity) {
queue = (T[]) new Object[DEFAULT_INITIAL_CAPACITY 1];
frontIndex = 0;
backIndex = initialCapacity;
}
// 在后端插入
public void enqueue(T newEntry) {
if (isArrayFull()) {
// 扩建数组
}
backIndex = (backIndex 1) % queue.length; // 由于数组是循环的，需要使用取余 % 操作符，以使backIndex达到其最大值之后变回0
queue[backIndex] = newEntry;
}
// 删除前端元素
public T dequeue() {
T front = null;
if (!isEmpty()) {
front = queue[frontIndex];
queue[frontIndex] = null;
frontIndex = (frontIndex 1) % queue.length;
}
return front;
}
// 检索前端元素
public T getFront() {
T front = null;
if (!isEmpty())
front = queue[frontIndex];
return front;
}
public boolean isEmpty() {
return frontIndex == ((backIndex 1) % queue.length);
}
private boolean isArrayFull() {
return frontIndex == ((backIndex 2) % queue.length);
}
}4. 基于双端链表的双端队列实现
public class LinkedDeque<T> implements DequeInterface<T>, Serializable {
private DLNode firstNode; // 引用双端队列的前端结点
private DLNode lastNode; // 引用双端队列的后端结点
public LinkedDeque() {
firstNode = null;
lastNode = null;
}
private class DLNode implements Serializable {
private T data;
private DLNode next;
private DLNode previous;
}
// 插入元素
public void addToBack(T newEntry) {
DLNode newNode = new DLNode(newEntry, lastNode, null);
if(isEmpty())
firstNode = newNode;
else
lastNode.setNext(newNode);
lastNode = newNode;
}
public void addToFront(T newEntry) {
DLNode newNode = new DLNode(newEntry, null, firstNode);
if(isEmpty())
lastNode = newNode;
else
firstNode.setPrevious(newNode);
firstNode = newNode;
}
// 删除元素
public T removeFront() {
T front = null;
if(!isEmpty()) {
front = firstNode.getData();
firstNode = firstNode.getNext();
if(firstNode == null)
lastNode = null;
else firstNode.setPrevious(null);
}
return front;
}
public T removeBack() {
T back = null;
if(!isEmpty()) {
back = lastNode.getData();
lastNode = lastNode.getPrevious();
if(lastNode == null)
firstNode = null;
else
lastNode.setNext(null);
}
return back;
}
}5. 实现优先队列的方法 可以使用数组或链表实现优先队列。
但使用堆实现优先队列是一种更高效的方法。 转载请并标注: “本文转载自 linkedkeeper.com ” ©著作权归作者所有 |
