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 ”  ©著作权归作者所有