java - 使用可调整大小的数组在 Java 中实现队列 API

Question

package com.queueapi;

/**
 * Created by Dhaval on 6/15/2016.
 */

public class DynamicArrayQueue {
    private String[] s;
    private int head = -1;
    private int tail = -1;

    public DynamicArrayQueue() {
    }

    public boolean isEmpty() {
        return head == -1 || head > tail || s.length == 0;
    }

    public void enqueue(String item) {
        if (isEmpty()) {
            head = 0;
            tail = 0;
            s = new String[1];
        }

        if (tail - head == s.length) {
            resize(s.length * 2);
        }

        s[tail++] = item;
    }

    public String dequeue() throws QueueUnderFlowException {
        if (isEmpty()) {
            throw new QueueUnderFlowException();
        }

        String item = s[head++];
        if (tail - head == s.length / 4) {
            resize(s.length / 2);
        }
        return item;
    }

    public void resize(int capacity) {
        String[] copy = new String[capacity];
        for (int i = head; i < tail; i++) {
            copy[i - head] = s[i];
        }
        s = copy;
        tail = tail - head;
        head = 0;
    }
}

我正在尝试使用支持三种基本功能的数组来实现动态调整大小的队列:

1. isEmpty()
2. 入队()
3. 出队()

限制是队列应始终填充在 25-100% 范围内，因此当队列已满时，我将调整数组大小以将其大小加倍，如果队列中的元素数量等于 size/4，则将大小减小到 size/2。

该队列与测试器一起使用，测试器将输入视为: 1 - 2 - 3 - 当“-”出现时，执行 dequeue() 操作，否则执行 enqueue()。

代码在 1 2 3 - - - - 作为输入时失败。请给我一些关于我哪里出错的见解。

测试客户端

package com.queueapi;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class QueueTester {

    public static void main(String[] args) throws QueueUnderFlowException {

        DynamicArrayQueue queue = new DynamicArrayQueue();
        while(!StdIn.isEmpty()){

            String s = StdIn.readString();
            if(s.equals("-")){
                StdOut.print(queue.dequeue());
            }
            else{
                queue.enqueue(s);
            }
        }
    }
}

Answer 1

在您的问题案例中，成员值为:

head tail s
-1   -1   []
   Enque "1"
0    1    ["1"]
   Enque "2"
0    2    ["1" "2"]
   Enque "3"
0    3    ["1", "2", "3", null]
   Deque -> "1"
1    3    ["1", "2", "3", null]
   Deque -> "1"
0    1    ["3", null]
   Deque -> "1"
0    0    [null]
   Deque -> null

从这里就很清楚了。您没有引发“下溢”，因为:

• head 不是 -1，也不是
• 头不大于尾，也不大于
• 数组长度为零。

队列中的项目数为tail - head，为零。但你不检查这一点；相反，您检查 head > tail，只有当队列中的项目数为负数时才会失败。

您可以通过测试 head >= tail 来解决此问题。