关于循环队列队尾元素的疑问

Question

LeetCode 上 关于问题：622. 设计循环队列，老师，我参照之前咱们写的LoopQueue代码，写了一套，但是在获取队列尾部元素的时候有点问题，tail和tail+1有点被绕晕了，回去查看了一下PDF文档，还是不明白这地方，希望老师能帮我解释一下，tail这个位置，到底存放不存放元素，tail+1的位置存不存放元素，现在对这两个位置的概念，有点模糊，我先贴一下我的代码：

public class MyCircularQueue {

private int[] array;//利用数据来实现
private int front, tail;//头部和尾部的数组向量坐标
private int size;

/**
 * Initialize your data structure here. Set the size of the queue to be k.
 */
public MyCircularQueue(int capacity) {
    this.array = new int[capacity + 1];//要空出一个元素来,不参与size计数，只是为了front和tail后续位置的不重叠，实际容量为capacity
    this.front = this.tail = 0;
    this.size = 0;
}

/**
 * Insert an element into the circular queue. Return true if the operation is successful.
 */
public boolean enQueue(int value) {
    if (!this.isFull()) {
        this.array[tail] = value;
        this.tail = (tail + 1) % array.length;
        this.size++;
        return true;
    }
    return false;
}

/**
 * Delete an element from the circular queue. Return true if the operation is successful.
 */
public boolean deQueue() {
    //把front往前挪一个位置
    if (!this.isEmpty()) {
        front = (front + 1) % array.length;
        this.size--;
        return true;
    }
    return false;
}

/**
 * Get the front item from the queue.
 */
public int Front() {
    return this.array[front];
}

/**
 * Get the last item from the queue.
 */
public int Rear() {// 1 2 3 4
    return this.array[tail % array.length];
}

/**
 * Checks whether the circular queue is empty or not.
 */
public boolean isEmpty() {
    return this.front == this.tail;

}

public String toString() {
    //此处的理解，需要加深
    StringBuilder loopQueue = new StringBuilder();
    loopQueue.append(String.format("LoopQuene:size=%d\n", size));
    loopQueue.append("front[");
    for (int i = front; i != tail; i = (i + 1) % array.length) {
        loopQueue.append(array[i]);
        if ((i + 1) % array.length != tail) {
            loopQueue.append(",");
        }
    }
    loopQueue.append("]tail");
    return loopQueue.toString();
}

/**
 * Checks whether the circular queue is full or not.
 */
public boolean isFull() {
    return ((this.tail + 1) % array.length) == this.front;
}

public static void main(String[] args) {
    MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为3

    System.out.println(circularQueue.enQueue(1));
    ;  // 返回true

    System.out.println(circularQueue.enQueue(2));
    ;  // 返回true

    System.out.println(circularQueue.enQueue(3));
    ;  // 返回true
    System.out.println(circularQueue.toString());
    System.out.println(circularQueue.enQueue(4));
    ;  // 返回false,队列已满

    System.out.println(circularQueue.Rear());
    ;  // 返回3

    System.out.println(circularQueue.isFull());
    ;  // 返回true

    System.out.println(circularQueue.deQueue());
    ;  // 返回true
    System.out.println(circularQueue.toString());
    System.out.println(circularQueue.enQueue(4));
    ;  // 返回true
    System.out.println(circularQueue.toString());
    System.out.println(circularQueue.Rear());
    ;  // 返回4
}

Answer 1

liuyubobobo 2018-09-17 17:13:06

在我们课程的实现中，tail是不存元素的。他永远指着最后一个元素后面一个的位置。

所以可以参考我们在课程中的代码实现：https://github.com/liuyubobobo/Play-with-Data-Structures/blob/master/03-Stacks-and-Queues/07-Implementation-of-Loop-Queue/src/LoopQueue.java

在入队的时候，第40行，永远先把新的元素放在tail的位置（因为tail没有元素），然后tail这个索引再做循环+1。

如果需要，Leetcode上622号问题也可以参考我的代码思路（C++）：

https://github.com/liuyubobobo/Play-Leetcode/blob/master/0622-Design-Circular-Queue/cpp-0622/main.cpp 

加油！：）

• 提问者 北京_鲁班七号 #1

  解决了，波波老师，非常感谢！看了一下您c++的获取队尾元素的方法体：
  if (this.isEmpty())
              return -1;
          int index = tail - 1;
          if (index < 0) {
              index += array.length;
          }
          return this.array[index];
  之前在这一块，被绕晕了，导致对tail和tail+1的理解出现偏差，看的时候觉得自己懂了，自己动手写的时候，发现很多东西需要去考虑，去笑话，谢谢！

• liuyubobobo 回复 提问者 北京_鲁班七号 #2

  赞！计算机是工科，实践是王道。看过和做过完全是两个不同的层次：）加油！