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

来源:7-7 基于二分搜索树的映射实现

北京_鲁班七号

2018-09-17

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
}
写回答

1回答

liuyubobobo

2018-09-17

在我们课程的实现中,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 


加油!:)

0
2
liuyubobobo
回复
北京_鲁班七号
赞!计算机是工科,实践是王道。看过和做过完全是两个不同的层次:)加油!
2018-09-18
共2条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

查看课程