循环队列【LeetCode】

循环队列【LeetCode】

  •  9个月前
  •  535
  •  Java Algorithm Queue 

概念

循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

实现思路

使用一个固定大小的数组,以及head、tail两个指针标识队列的开始和结束位置。

工作原理


实现操作

  • MyCircularQueue(k): 构造器,设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空,返回 -1 。
  • Rear: 获取队尾元素。如果队列为空,返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

代码

public class MyCircularQueue {

    private int[] arr;

    private int size = 0;

    private int head = -1;

    private int tail = -1;

    /**
     * Initialize your data structure here. Set the size of the queue to be k.
     */
    public MyCircularQueue(int k) {
        if (k <= 0) throw new RuntimeException("illegal size!");
        this.arr = new int[k];
    }

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

    /**
     * Delete an element from the circular queue. Return true if the operation is successful.
     */
    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }

        if (this.head == this.tail) {
            this.head = -1;
            this.tail = -1;
        } else {
            this.head = (this.head + 1) % this.arr.length;
        }
        this.size--;
        return true;
    }

    /**
     * Get the head item from the queue.
     */
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return this.arr[this.head];
    }

    /**
     * Get the last item from the queue.
     */
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return this.arr[this.tail];
    }

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

    /**
     * Checks whether the circular queue is full or not.
     */
    public boolean isFull() {
        return this.size == this.arr.length;
    }

}


扫一扫分享到微信

已有 条评论
写评论