您的位置: 首页  >  文章  >  顺序队列（JAVA）

顺序队列（JAVA）

分类: 文章 • 2024-09-30 10:13:46

顺序队列就是基于数组实现的队列

直观的思路

队列元素从尾入队，从头出队，先进先出，后进后出
入队相当于在数组中追加一个元素array[tailPos] = element;
出队相当于将数组元素index=0取出，再全数组向前移动
很明显，每次出队都要全员移动，时间复杂度O(n)

出队时不做全员移动的思路

如果出队时不做全员移动，可以保留下次出队元素的索引值
那么就要记录两个游标值，一个指向下一次入队元素位置tailPos，一个指向下一次出队元素位置headerPos，而且不等式tailPos >= headerPos始终成立。tailPos索引表示下一次要入队元素的索引，所以当前时刻，该位置存放的元素不在队列当中的；相应的headerPos索引指向的元素一般情况下都在队列中，唯独headerPos = tailPos时，表示队列为空，需要先入队，使得tailPos更大一些，才能继续出队。
也就是说，headerPos = tailPos时，队列为空。
而队列满的标志是下一次入队tailPos和数组长度相同，即tailPos = arrayLength。
代码如下

import java.util.Arrays;

public class ArrayQueue1<T> {

    private T[] array;

    private int arrayLength;

    private int headerPos;

    private int tailPos;

    public ArrayQueue1(int length) {
        this.arrayLength = length;
        this.array = (T[]) new Object[length];
    }

    /**
     * 入队
     *
     * @param element
     * @return
     */
    public boolean enqueue(T element) {
        if (tailPos == arrayLength) {
            System.out.println("queue is full");
            return false;
        }
        this.array[tailPos++] = element;
        return true;
    }

    /**
     * 出队
     *
     * @return
     */
    public T dequeue() {
        if (headerPos == tailPos) {
            System.out.println("queue is empty");
            return null;
        }
        return this.array[headerPos++];
    }

    @Override
    public String toString() {
        T[] queue = Arrays.copyOfRange(this.array, headerPos, tailPos);
        return Arrays.toString(queue);
    }

    public static void main(String[] args) {
        ArrayQueue1<String> queue = new ArrayQueue1<>(7);
        System.out.println(queue);
        queue.enqueue("A");
        queue.enqueue("B");
        queue.enqueue("C");
        queue.enqueue("D");
        System.out.println(queue);
        queue.dequeue();
        System.out.println(queue);
        queue.dequeue();
        System.out.println(queue);
        queue.enqueue("E");
        System.out.println(queue);
        queue.enqueue("F");
        System.out.println(queue);
        queue.enqueue("G");
        System.out.println(queue);
        queue.enqueue("H");
        System.out.println(queue);
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.enqueue("I");
        System.out.println(queue);
    }
    
}

执行结果

[]
[A, B, C, D]
[B, C, D]
[C, D]
[C, D, E]
[C, D, E, F]
[C, D, E, F, G]
queue is full
[C, D, E, F, G]
queue is empty
queue is full
[]

从执行结果中可以看到，队列出现了又空又满的情形。
空确实是队列空了，但满其实是基于的数组满了。而此时，数组的元素对于队列而言，没有使用价值了。出队降低了时间复杂度，没有了全员移动，但此时的队列有了“使用寿命”。

在队列不满而数组满的时候做全员移动

如果数组满了，而且队列也满了，这时候如果不能入队是正常情况（也可以做扩容功能），但如果队列没满，只是数组满了，就需要腾空一些数组的位置出来给入队使用。注意全员移动的条件是：队列不满而数组满了
新的顺序队列实现代码如下

import java.util.Arrays;

public class ArrayQueue2<T> {

    private T[] array;

    private int arrayLength;

    private int headerPos;

    private int tailPos;

    public ArrayQueue2(int length) {
        this.arrayLength = length;
        this.array = (T[]) new Object[length];
    }

    /**
     * 入队
     *
     * @param element
     * @return
     */
    public boolean enqueue(T element) {
    	// 全员移动操作
        if (tailPos == arrayLength && headerPos > 0) {
            System.out.println("ready to batchMove");
            for (int i = headerPos; i <= tailPos - 1; i++) {
                this.array[i - headerPos] = this.array[i];
            }
            this.tailPos = this.tailPos - this.headerPos;
            this.headerPos = 0;
        }
        if (tailPos == arrayLength) {
            System.out.println("queue is full");
            return false;
        }
        this.array[tailPos++] = element;
        return true;
    }

    /**
     * 出队
     *
     * @return
     */
    public T dequeue() {
        if (headerPos == tailPos) {
            System.out.println("queue is empty");
            return null;
        }
        return this.array[headerPos++];
    }

    @Override
    public String toString() {
        T[] queue = Arrays.copyOfRange(this.array, headerPos, tailPos);
        return Arrays.toString(queue);
    }

    public static void main(String[] args) {
        ArrayQueue2<String> queue = new ArrayQueue2<>(7);
        System.out.println(queue);
        queue.enqueue("A");
        queue.enqueue("B");
        queue.enqueue("C");
        queue.enqueue("D");
        System.out.println(queue);
        queue.dequeue();
        System.out.println(queue);
        queue.dequeue();
        System.out.println(queue);
        queue.enqueue("E");
        System.out.println(queue);
        queue.enqueue("F");
        System.out.println(queue);
        queue.enqueue("G");
        System.out.println(queue);
        queue.enqueue("H");
        System.out.println(queue);
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.enqueue("I");
        System.out.println(queue);
    }

}

执行结果

[]
[A, B, C, D]
[B, C, D]
[C, D]
[C, D, E]
[C, D, E, F]
[C, D, E, F, G]
ready to batchMove
[C, D, E, F, G, H]
[I]

可否在不做任何全员搬迁的条件下实现队列代码

环形顺序队列

环形顺序队列思路

将队列环绕一圈，假设数组长度为6，初始化状态下headerPos = tailPos = 0
下图为环形顺序队列的初始状态
顺序队列（JAVA）
接着入队和出队依次进行若干次，比如入队5次，出队2次
顺序队列（JAVA）
此时headerPos = 2, tailPos = 5
继续入队一个元素，期望达到如下效果
顺序队列（JAVA）
其中headerPos = 2, tailPos = 0
假如接着继续入队
顺序队列（JAVA）
此时headerPos = 2, tailPos = 1
假如接着继续入队
顺序队列（JAVA）
此时headerPos = tailPos
根据之前的判空判满条件可知，当headerPos和tailPos相等时，意味着队列为空。一直以来都是针对入队的优化操作，也就是说这里要考虑判满的条件。
如果这一步操作会成立，则判空和判满条件就相同了。
环形顺序队列的判满条件在更上一张图中发生。即图中的headerPos = 2, tailPos = 1
这会浪费数组中的一个位置，得到如下的满员情形（数组长度为6）

headerPos tailPos
0 5
1 0
2 1
3 2
4 3
5 4
(x+1)%6 x

代码

public class ArrayQueue3<T> {

    private T[] array;

    private int arrayLength;

    private int headerPos;

    private int tailPos;

    public ArrayQueue3(int length) {
        this.arrayLength = length;
        this.array = (T[]) new Object[length];
    }

    /**
     * 入队
     *
     * @param element
     * @return
     */
    public boolean enqueue(T element) {
        if (headerPos == (tailPos + 1) % arrayLength) {
            System.out.println("queue is full");
            return false;
        }
        this.array[tailPos] = element;
        tailPos = (tailPos + 1) % arrayLength;
        return true;
    }

    /**
     * 出队
     *
     * @return
     */
    public T dequeue() {
        if (headerPos == tailPos) {
            System.out.println("queue is empty");
            return null;
        }
        T temp = this.array[headerPos];
        headerPos = (headerPos + 1) % arrayLength;
        return temp;
    }

    @Override
    public String toString() {
        if (tailPos < headerPos) {
            T[] pre = Arrays.copyOfRange(this.array, headerPos, arrayLength);
            T[] suf = Arrays.copyOf(this.array, tailPos);
            List<T> result = new ArrayList<>();
            if (pre != null && pre.length != 0) {
                for (T t : pre) {
                    result.add(t);
                }
            }
            if (suf != null && suf.length != 0) {
                for (T t : suf) {
                    result.add(t);
                }
            }
            return "list : " + result.toString();
        } else {
            T[] queue = Arrays.copyOfRange(this.array, headerPos, tailPos);
            return "array : " + Arrays.toString(queue);
        }
    }

    public static void main(String[] args) {
        ArrayQueue3<String> queue = new ArrayQueue3<>(7);
        System.out.println(queue);
        queue.enqueue("A");
        queue.enqueue("B");
        queue.enqueue("C");
        queue.enqueue("D");
        System.out.println(queue);
        queue.dequeue();
        System.out.println(queue);
        queue.dequeue();
        System.out.println(queue);
        queue.enqueue("E");
        System.out.println(queue);
        queue.enqueue("F");
        System.out.println(queue);
        queue.enqueue("G");
        System.out.println(queue);
        queue.enqueue("H");
        System.out.println(queue);
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.enqueue("I");
        System.out.println(queue);
        queue.enqueue("J");
        System.out.println(queue);
        queue.enqueue("K");
        System.out.println(queue);
        queue.enqueue("L");
        System.out.println(queue);
        queue.enqueue("M");
        System.out.println(queue);
        queue.enqueue("N");
        System.out.println(queue);
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        queue.dequeue();
        System.out.println(queue);
    }

}

执行结果

array : []
array : [A, B, C, D]
array : [B, C, D]
array : [C, D]
array : [C, D, E]
array : [C, D, E, F]
list : [C, D, E, F, G]
list : [C, D, E, F, G, H]
array : [I]
array : [I, J]
array : [I, J, K]
array : [I, J, K, L]
array : [I, J, K, L, M]
list : [I, J, K, L, M, N]
list : [N]

相关推荐