欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

java队列的数组实现

程序员文章站 2024-03-18 08:07:04
...

队列接口:

package Interface;

/**
 * 队列接口
 * <p>
 * 队列是一种先进先出的线性表
 * 只能在表的一端进行插入,另一段进行删除
 * 允许插入的一端叫队尾,允许删除的一端叫队头()
 *
 *
 * ps:还存在一种 双端队列 即队头和队尾都可以进行插入和删除的操作,队头和队尾在这里叫端点
 * 以及输入受限的双端队列(一端输入和删除,另一端只能删除)
 * 输出受限的双端队列(一端输入和删除,另一端只能输入)
 * 但是双端队列应用不广泛 不在此做讨论
 */
public interface IQueue<T> {

    /**
     * 初始化队列 构造一个空队列
     */
    IQueue InitQueue();

    /**
     * 销毁队列
     */
    IQueue DestroyQueue();

    /**
     * 清空队列
     */
    IQueue ClearQueue();

    /**
     * 队列判空
     */
    Boolean isEmpty();

    /**
     * 返回队列长度
     */
    Integer QueueLength();

    /**
     * 返回队列头元素
     */
    T GetHead();

    /**
     * 插入队尾元素
     */
    Boolean EnQueue(T e);

    /**
     * 删除队头元素  即出队
     */
    T DeQueue();

}
package impl;

import Interface.IQueue;

/**
 * 数组型队列
 * <p>
 * 同样需要一个头指针,一个尾指针  当头指针=尾指针=0时候为空
 * 需要实现分配一个固定大小的数组
 * 正常情况下下,尾指针永远指向队尾元素的下一个位置,比如说队尾元素在0 尾指针则在1
 * <p>
 * 注意!:数组型队列有很大的劣势,容易造成存储空间浪费,而且不易扩容。
 * 比如说,最大空间为6的数组队列, 进去了6个了元素,然后从队头出去了5个元素,此时,仍然不能插入新的元素
 * 因为队尾指针仍然指向第6个元素,其仍然占据了最后一个位置,而队头是不允许插入的。这样造成前面5个位置浪费。
 * <p>
 * 解决方法:1.元素移动位置,出队一个 后面的元素往前挪。   缺点:每次出队都需要移动位置 很麻烦 效率也低
 * 2.动态扩容,  缺点:浪费了前面的空间
 * 3.最佳解决方案:构造环形队列
 */
public class ArrayQueue<T> implements IQueue {
    private Integer size;
    private Integer header;
    private Integer tail;
    private final Integer length = 6;
    private Object[] arr;

    public IQueue InitQueue() {
        arr = new Object[length];
        tail = header = size = 0;
        return this;
    }

    public IQueue DestroyQueue() {
        arr = null;
        tail = header = size = 0;
        return this;
    }

    public IQueue ClearQueue() {
        tail = header = size = 0;
        for (int i = 0; i < arr.length; i++) {
            arr[i] = null;
        }
        return this;
    }

    public Boolean isEmpty() {
        if (tail == header) {
            return Boolean.TRUE;
        }
        return Boolean.FALSE;
    }

    public Integer QueueLength() {
        return size;
    }

    public Object GetHead() {
        return arr[header];
    }

    public Boolean EnQueue(Object e) {
        if (size >= length) {
            return Boolean.FALSE;
        }

        if (header == tail) {//先判断是不是空的 如果是 重置头尾指针  ,不然这个队列就只能用一次了
            header = 0;
            arr[header] = e;
            tail = 1;
            size++;
            return Boolean.TRUE;
        } else {
            arr[tail] = e;
            tail = tail + 1;
            size++;
            return Boolean.TRUE;
        }


    }

    public Object DeQueue() {
        if (header == tail) {
            return null;
        }
        T e = (T) arr[header];
        header = header + 1;
        size--;
        return e;
    }


    public static void main(String[] args) {
        ArrayQueue<Integer> arrayQueue = new ArrayQueue<Integer>();
        arrayQueue.InitQueue();
        arrayQueue.EnQueue(1);
        arrayQueue.EnQueue(2);
        arrayQueue.EnQueue(3);
        arrayQueue.EnQueue(4);
        arrayQueue.EnQueue(5);
        arrayQueue.EnQueue(6);
        Integer s = arrayQueue.size;
        System.out.println(arrayQueue.GetHead());
        for (Integer integer = 0; integer < s; integer++) {
            System.out.println(arrayQueue.DeQueue());
        }
        System.out.println(arrayQueue.isEmpty());
        arrayQueue.EnQueue(1);
        arrayQueue.EnQueue(2);
        arrayQueue.EnQueue(3);
        arrayQueue.EnQueue(4);
         s = arrayQueue.size;
        for (Integer integer = 0; integer < s; integer++) {
            System.out.println(arrayQueue.DeQueue());
        }
        System.out.println(arrayQueue.isEmpty());
    }
}

输出结果
1
1
2
3
4
5
6
true
1
2
3
4
true