队列（queue）

queue 定义

队列是一种只允许在表的掐断进行删除操作且在表的后端进行插入操作的线性表。允许插入操作的一端叫队尾（rear），允许删除一端称为队头（front）。队列是一种先进先出的线性表。

队列的链式表示

用链表表示的队列叫做链队列。一个链队列需要两个分别指向队头和队尾的指针才能唯一确定。空的链队列的判断条件是头指针和尾指针均指向头结点。

队列的顺序表示

除了使用一组地址连续的存储单元依次存放队里的元素外，还需要两个指针front和rear分别指示队列头元素和队列尾元素的位置。

循环队列，将顺序队列臆造成一个环境的空间，此时如果要对队列空间进行“满元素”和“空元素”的判断，需要增加一个标志位区分队列是“空”还是“满”，或者约定当队尾指正的下一个位置是队列头的位置，则队列为满。

当无法判断队列的长度大小时可以需要使用链队列。

实现

Java简单实现

package queue;

/**
 * 基于数组的队列
 *
 */
public class Queue {

    private Object[] data = null;
    /**
     * 队列的容量
     */
    private int maxSize;
    /**
     * 队头
     */
    private int front;
    /**
     * 队尾
     */
    private int rear;

    Queue(int initialSize) {
        if (initialSize >= 0) {
            this.maxSize = initialSize;
            data = new Object[initialSize];
            front = rear = 0;
        } else {
            throw new RuntimeException("初始化大小不能小于0：" + initialSize);
        }
    }

    Queue() {
        this(10);
    }

    public boolean add(E e) {
        if (rear == maxSize) {
            throw new RuntimeException("队列已满，无法插入新元素");
        } else {
            data[rear++] = e;
            return true;
        }
    }

    public E poll() {
        if (data.length == 0) {
            throw new RuntimeException("空队列");
        } else {
            E value = (E) data[front];
            data[front++] = null;
            return value;
        }
    }

    public E peek() {
        if (data.length == 0) {
            throw new RuntimeException("空队列");
        } else {
            return (E) data[front];
        }
    }

    public static void main(String[] args) {
        Queue q = new Queue();
        q.add("1");
        q.add("2");
        q.add("3");
        System.out.println(q.poll());
        System.out.println(q.peek());
    }
}

参考

《数据结构 （C语言版）》 严蔚敏

《Java面试核心知识点》 王磊