做外贸网站那家专业山西优化公司

队列的特点

1. 先进先出（FIFO）
2. 允许在表的一端插入数据，在另一端删除数据

---

 

所需元素

1. 数组queueArray
2. 指向队头的指针front
3. 指向队尾的指针rear
4. 记录队列元素数量的elements
5. 数组的初始化大小maxSize

---

 

分析实现

　　1. 在实例化队列类时确定数组大小并初始化数组
　　2. 确定队列具有的功能：

　　　　（1）EnQueue(Object obj) 　　插入元素，即元素入队，并且是在队尾入队

　　　　（2）DeQueue() 　　删除元素，即元素出队，并且是在队头出队

　　　　（3）isEmpty()　　判空

　　　　（4）isFull() 　　判满

　　　　（5）getHead() 　　查看队头元素，只查看，不删除

　　　　（6）length()　　查看队列长度

　　　　（7）clear()　　清空队列

---

 

代码实现

public class Queue {

    /**
     * queueArray 底层数组
     * front 队头
     * rear 队尾
     * elements 队列元素
     * maxSize 数组最大容量
     */
    private Object[] queueArray;
    private int front;
    private int rear;
    private int elements;
    private int maxSize;

    /**
     * 初始化操作
     * @param maxSize
     */
    public Queue(int maxSize) {
        this.maxSize = maxSize;
        this.queueArray = new Object[maxSize];
        this.front = 0;
        this.rear = 0;
        this.elements = 0;
    }

    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty() {
        return (elements == 0);
    }

    /**
     * 判断队列是否为满队列
     * @return
     */
    public boolean isFull() {
        return (elements == maxSize);
    }

    /**
     * 插入元素，即元素入队，并且是在队尾入队
     * @param data
     */
    public void enQueue(Object data) {
        if (isFull()) {
            throw new RuntimeException("队列已满");
        }
        queueArray[rear++] = data;
        elements++;
    }

    /**
     * 删除元素，即元素出队，并且是在队头出队
     * @return
     */
    public Object deQueue() {
        if (isEmpty()) {
            throw new RuntimeException("空队列");
        }
        // 其实这里并没有真正删除数组里的元素，只是访问指针往上移，即不提供访问被删除元素的方式
        Object data = queueArray[front++];
        elements--;
        return data;
    }

    /**
     * 查看队头元素，只查看，不删除
     * @return
     */
    public Object getHead() {
        Object data = queueArray[front];
        return data;
    }

    /**
     * 查看队列长度
     * @return
     */
    public int length() {
        return elements;
    }

    /**
     * 清空队列
     */
    public void clear() {
        while (front != rear) {
            deQueue();
        }
    }
}

 

测试

public class QueueTest {

    public static void main(String[] args) {

        Queue queue = new Queue(4);

        System.out.println("队列是否为空? " + queue.isEmpty());

        queue.enQueue(11);
        queue.enQueue(2);
        queue.enQueue(5);
        queue.enQueue(67);

        System.out.println("队列是否已满? " + queue.isFull());
        System.out.println("队头元素： " + queue.getHead());
        System.out.println("队列长度： " + queue.length());

        System.out.print("打印队列元素： ");
        while (!queue.isEmpty()) {
            Object o = queue.deQueue();
            System.out.print(o + "\t");
        }
        System.out.println();

        /*queue.enQueue(5);
        queue.enQueue(67);*/
        // 清空队列
        queue.clear();
        System.out.println("清空队列后，队列是否为空? " + queue.isEmpty());
    }
}

 

结果

队列是否为空? true
队列是否已满? true
队头元素： 11
队列长度： 4
打印队列元素： 11    2    5    67    
清空队列后，队列是否为空? true

 

---

 

总结

1. 只允许在队尾rear插入元素；
2. 只允许在队头front删除元素；
3. 本例子插入和删除都是队头队尾指针的移动，所存储的元素并不会移动；
4. 删除的元素其实还存在数组中，只是不提供访问的方法；
5. 使用数组实现，扩容困难。

---