栈和队列

栈

栈（Stack）是一种特殊的线性表，它仅允许在表的一端进行插入和删除操作。这种限制使得栈具有“先进后出”（FILO）的特性。

在栈中，元素按照从后往前的顺序排列，最新添加的元素总是位于栈顶，而最早添加的元素位于栈底。

栈通常用于解决一些涉及逆序、撤销等操作的问题，如深度优先搜索、括号匹配等。

栈则是一种抽象的逻辑概念，并没有实体。所以栈既可以用数组来实现，也可以用链表来实现，只要符合栈的先入后出规则就可以。

操作（入栈和出栈）

入栈

入栈（Push）就是把新元素放入到栈当中，只允许在栈顶一侧放入元素，新元素的位置将会成为新的栈顶。
入栈的操作分为两步：

1. 1.元素首先被放到栈顶的下一个位置
2. 把元素设置为栈顶。

出栈

出栈（Pop）就是把旧元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。

出栈的操作只需要一步：把原栈顶的前一个元素设为新栈顶。

时间复杂度

入栈和出栈只会影响到最后一个元素，不涉及其他元素的整体移动，所以无论是数组还是链表的实现，入栈出栈的时间复杂度都是O（1）

队列

• 队列（Queue）是另一种常用的数据结构，它遵循先进先出（FIFO）的原则。
• 队列只允许在表的队头（front）进行删除操作，而在表的队尾（rear）进行插入操作。
• 队列中的元素按照添加的顺序进行排列，最早添加的元素总是第一个被删除。
• 队列常用于实现数据的FIFO（先进先出）操作，例如在多线程编程中，可以用队列来实现线程间的通信和同步。

和栈类似，队列这种数据结构也是一种抽象的逻辑概念，即可以用数组来实现，也可以用链表来实现。

操作（入队和出队）

入队

入队（Enqueue）就是把新元素放入到队列当中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾。

出队

出队（Dequeue）就是把旧元素移出队列，只允许在队头一侧移出元素，出队元素的后面一个元素将会成为新的队头。

循环队列

当用数组来实现队列的话，像这样不断出队，队头左边的空间就会一点一点失去作用，那队列的容量就会变得越来越小，类似于图里显示的这样：

这个问题不会出现在链表实现的队列，只会出现在数组实现的队列当中。这时我们可以使用循环队列的方式来维持队列容量恒定。

看以下示例： 一个队列经过反复的入队和出队操作，还剩下2个元素，在“物理”上分布于数组的末尾位置。这时候又有一个新元素将要入队。

在数组不做扩容的前提下，如何让新元素入队并确定新的队尾位置呢？我们可以重新利用已出队元素留下的空间，让队尾指针指回到数组的首位。

这样一来，整个队列的元素就“循环”起来了。在物理存储上，队尾的位置也可以在队头之前。当再有元素入队时，放入数组的首位，队尾指针继续后移。

一直到（队尾下标+1）%数组长度 = 队头下标 时，代表此队列真的已经满了。需要注意的是，队尾指针指向的位置永远空出一位，所以队列最大容量比数组长度小1。

这就是所谓的循环队列，让我们来看一看代码实现：

DETAILS

class CircularQueue {  
  constructor(k) {  
    this.k = k; // 队列的容量  
    this.queue = new Array(k); // 初始化队列数组  
    this.head = -1; // 头指针，初始化为-1  
    this.tail = -1; // 尾指针，初始化为-1  
  }  
  
  // 入队操作  
  enqueue(value) {  
    if (this.isFull()) {  
      return false; // 队列已满，入队失败  
    }  
    if (this.isEmpty()) {  
      this.head = 0; // 队列为空，头指针移动到第一个位置  
    }  
    this.tail = (this.tail + 1) % this.k; // 更新尾指针的位置  
    this.queue[this.tail] = value; // 在尾指针位置添加元素  
    return true; // 入队成功  
  }  
  
  // 出队操作  
  dequeue() {  
    if (this.isEmpty()) {  
      return false; // 队列为空，出队失败  
    }  
    if (this.head === this.tail) {  
      this.head = -1; // 队列中只有一个元素，出队后将头指针置为-1  
      this.tail = -1; // 出队后将尾指针置为-1  
    } else {  
      this.head = (this.head + 1) % this.k; // 更新头指针的位置  
    }  
    return true; // 出队成功  
  }  
  
  // 获取队头元素  
  front() {  
    if (this.isEmpty()) {  
      return -1; // 队列为空，返回-1  
    }  
    return this.queue[this.head]; // 返回队头元素  
  }  
  
  // 获取队列长度  
  size() {  
    if (this.isEmpty()) {  
      return 0; // 队列为空，返回0  
    }  
    return (this.tail - this.head + this.k) % this.k; // 计算队列长度  
  }  
  
  // 判断队列是否为空  
  isEmpty() {  
    return this.head === -1 && this.tail === -1; // 如果头指针和尾指针都为-1，则队列为空  
  }  
  
  // 判断队列是否已满  
  isFull() {  
    return (this.tail + 1) % this.k === this.head; // 如果尾指针加1后与头指针相同，则队列已满  
  }  
}

循环队列不但充分利用了数组空间，还免去了数组元素整体移动的麻烦，具有更高的空间利用率和更好的性能。

时间复杂度

入队和出队复杂度都是O（1）