循环队列(数组实现)

前言

今天，我又下定决心准备在来到LeetCode来看看算法。我对算法的无知让我对算法有了更加多的学习欲望，虽然自己没有什么天赋，但是作为一个向上的程序员，这道坎还是要过的。队列算的上是最基本的数据结构了，但是今天的队列数据结构的构成却难倒了我，让我意识到了自己是有多菜，于是翻开官网回答，让我也是受益匪浅。下面就来讲讲我在写队列这个数据接结构的时候遇到的困难。

• 首先，在写队列的时候我不清楚队列需要哪些属性
• 第二，对于进队和出队的一些特殊情况我也不是很清楚
• 第三，甚至初始化一个队列的时候我居然也不知道要干嘛
• 第四，我又觉得自己好菜，但是，我还是站起来了!!!

官方解析

原题+代码

返回目录

设计循环队列

class MyCircularQueue {

  private int[] queue;
  private int headIndex;
  private int count;
  private int capacity;

  /** Initialize your data structure here. Set the size of the queue to be k. */
  public MyCircularQueue(int k) {
    this.capacity = k;
    this.queue = new int[k];
    this.headIndex = 0;
    this.count = 0;
  }

  /** Insert an element into the circular queue. Return true if the operation is successful. */
  public boolean enQueue(int value) {
    if (this.count == this.capacity)
      return false;
    this.queue[(this.headIndex + this.count) % this.capacity] = value;
    this.count += 1;
    return true;
  }

  /** Delete an element from the circular queue. Return true if the operation is successful. */
  public boolean deQueue() {
    if (this.count == 0)
      return false;
    this.headIndex = (this.headIndex + 1) % this.capacity;
    this.count -= 1;
    return true;
  }

  /** Get the front item from the queue. */
  public int Front() {
    if (this.count == 0)
      return -1;
    return this.queue[this.headIndex];
  }

  /** Get the last item from the queue. */
  public int Rear() {
    if (this.count == 0)
      return -1;
    int tailIndex = (this.headIndex + this.count - 1) % this.capacity;
    return this.queue[tailIndex];
  }

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

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

解决了我心中的的疑惑

返回目录

1. 解决了写队列需要哪些属性的问题

属性定义的原则：官方给出的解释是数据结构的关键是数据结构的属性设置，好的设计属性更加少，下面给出了几点原因

• 属性少说明属性之间的冗余性更加少
• 属性的冗余度越低，操作逻辑更加简单，发生错误的可能性就越低
• 属性数量越少，空间复杂度就越低，性能就更好

注意：属性也不是越少越好，在某些情况下，冗余的属性可以降低时间复杂度，达到时间和空间复杂度的平衡。相信写过业务代码的小伙伴都知道，数据表的设计上就经常会冗余一些字段减低某些业务的复杂度。

最终队列需要定义的属性也就出来了，这里没有额外用到尾结点的属性，因为我们可以通过 headIndex 和 count 推断出尾结点的下标(tailIndex = (headIndex + count - 1)%capacity)

• queue:一个固定大小的数组，也就是存放数据的容器
• headIndex:队列的头结点下标
• count:循环队列的当前长度
• capacity:队列的最大容量

2. 队列进队和出队我们需要考虑的特殊情况

在做许多算法的时候我都会遇到这种问题，因为算法中都会有着特殊的节点需要进行特殊的处理，比如旋转字符串就需要在字符串达到中间值的时候进行结束。队列的进队和出队也是有着特殊情况，如下：

• 进队:队列满的时候就是需要进行特殊处理的，尾结点移动到数组最大下标需要特殊处理
• 出队:队列空的时候就是需要进行特殊处理的，头结点移动到数组最大下标需要特殊处理

3. 队列的初始化需要做的事

其实，你只要确定好了了你这个队列数据结构所需要的属性就可以知道初始化所需要做的事了。

小结

返回目录

这个是数据结构的学习，也是比较基础的，下面就给出数据结构设计的要点

• 属性的设计选择(思路还是要从这个结构能够完成的功能来说)
• 特殊情况的处理，这个通常一下子是想不全面的，需要多测、多想

心得

个人有个毛病，就是总是想着第一次写代码就把这个代码写的很完美，但是这个是通常是不可能的，所以需要一步一步来，首先把基本的逻辑点写出来，然后一点一点的改进完善，最终的成品就会变得完美。所以就需要你不断对代码进行重构，这样子才可以写出好的代码，切记不要偷懒而不愿意对代码重写重构，还有，学习算法是需要你的决心和毅力，千万不要半途而废

最后

以上就是飞快便当为你收集整理的循环队列(数组实现)前言官方解析小结的全部内容，希望文章能够帮你解决循环队列(数组实现)前言官方解析小结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。