双端队列位置确定问题

双端队列中：addFront方法中，判断front==0，则队列中没有元素，data.length为0，新的添加元素逻辑不应该是data[0]=e吗，如果是data.length-1，那么逻辑不就变成了data[-1]=e吗，

kristi9018977 2022-09-13

源自：数据结构基础：动态数组，栈和队列 2-13 作业解析：实现双端队列

收起

1回答

liuyubobobo 2022-09-14 12:27:27

我不确定我是不是理解了你的问题，但是：

front == 0，不是队列里没有元素，front == 0 是队列里的第一个元素在 0 的位置；

同理，front == 1 是队列里第一个元素在 1 的位置；

front == 2 是队列里第一个元素在 2 的位置；

假设 front == 2，也就是队列里第一个元素在 2 的位置，addFront 将把新的元素放在这个元素的前面，也就是放在 2 - 1 = 1 的位置；

假设 front == 1，也就是队列里第一个元素在 1 的位置，addFront 将把新的元素放在这个元素的前面，也就是放在 1 - 1 = 0 的位置；

假设 front == 0，也就是队列里第一个元素在 0 的位置，addFront 将把新的元素放在这个元素的前面，也就是放在 0 - 1 = -1 的位置；但是，-1 不是一个合法的索引，不过，我们整个队列是循环起来的。所以，我们把新的元素放在整个数组的尾巴，也就是 data.length - 1 的位置。

Java 语言不支持写成 data[-1] = e 的方式。（但是 Python 语言支持。）

==========

这里唯一的例外是在初始的时候，front == 0 且 tail == 0，此时，front 没有指向队列首的元素，因为此时队列中没有任何元素。但这不影响我们的逻辑。如果在队列为空的时候，先调用 addFront 加入一个元素，这个元素会加入到 data.length - 1 的位置。但此时，front 也会更新为 data.length - 1，此时，data,length - 1 的位置就是队列头。

这就是循环队列的意思，队列头不是固定的。任何一个位置都可以是队列头，从队列头开始，往后做 +1 操作，就是向后遍历元素，加到数组越界了，就回到 0，这就是“循环”的意思。

或者如果我没有理解你的意思的话，给你用代码来表达一下你的逻辑？你认为哪个部分的代码应该怎样写？或者你认为课程的代码哪里有误？请你设计一个测试用例，让这个错误表达出来？

继续加油！：）

收起回答

提问者 kristi9018977 #1

  明白了，data.length有默认的10个容量，队列是循环的，所以data.length-1实际上是9，单步跟踪后发现，
  如果front==0，此时data[data.length - 1]=data[9]，是可以赋值的。
  如果代码写成下面这样，有问题么？
    (e) {
        (== getCapacity()) {
            resize(getCapacity() * )}= == ? : - [] = e++++}
这样写会有边界问题吗？

2022-09-16 14:49:31

提问者 kristi9018977 #2

    public void addFront(E e) {
        //当tail指针+1，和front指针重合时，就表示队列已经满了，就需要扩容
        if (size == getCapacity()) {
            resize(getCapacity() * 2);
        }
        front = front == 0 ? front : front - 1;
        data[front] = e;
        tail++;
        size++;
    }

2022-09-16 14:51:03