先进先出的结构-队列


theme: keepnice

前言

在JavaScript的世界里,队列就像是排队买爆米花的电影迷一样,每个人都得按次序等待。但这个队列有点不一样,它不是排在电影院门口,而是在代码里等待执行。就像是一场奇幻冒险电影,让我们一起来揭开JavaScript队列的神秘面纱吧!

想象一下,你站在一家电影院前面,人群熙熙攘攘,大家都在争先恐后地买票。这时候,一个叫做JavaScript的小精灵出现了,他要给每个人一个编号,然后按照编号依次让大家进去。这就是JavaScript队列的基本原理:先到先得,依次执行。

但是,就像电影院里总有些人想插队一样,JavaScript队列也可能会被打乱。比如,当你在网页上点击按钮,或者触发了其他事件,这些操作可能会插入到队列的前面,打乱原本的执行顺序。这就好比有人突然跳队,搞得大家都不知所措。

当然,JavaScript也有一些“特技”来处理这种情况。比如,setTimeout()和setInterval()这两个函数就像是“暂停”和“重复播放”按钮,它们可以让你控制代码的执行时间,让队列里的任务按照你的意愿来执行。不过,有时候你也得小心使用,不然可能会让整个队列乱套。

另外,JavaScript队列还有一个特别有趣的地方,就是事件循环(Event Loop)。这个概念有点像是一场精彩的马戏表演,不停地重复着各种动作。事件循环负责不断地检查队列里有没有任务需要执行,如果有就把它们拿出来执行,直到队列为空为止。就像是一个不知疲倦的马戏团团长,时刻关注着每一个表演者的动作。

所以,JavaScript队列不仅仅是一群买电影票的人排队,更像是一场精彩绝伦的马戏表演,充满了意外和惊喜。只要你掌握了它的规则和技巧,就能在代码的舞台上驰骋自如,创造出令人叹为观止的表演!

1.初识队列

const queue = []
queue.push(1)
queue.push(2)
queue.push(3)
queue.push(4)
queue.push(5)
queue.push(6)
while (queue.length) {
  let top = queue.shift()
  console.log(top);
}

输出1,2,3,4,5,6

我们可以理解为队列是拥有push和shift方法(先进先出)的特殊数组,那么让我们来道算法题加深对队列的认识。

2.leetCode225

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(pushtoppop 和 empty)。

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

示例:

输入:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 2, 2, false]

解释:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

要使用两个队列实现一个后入先出(LIFO)的栈,可以利用队列的先入先出(FIFO)特性来模拟栈的后入先出。具体思路如下:

  1. 使用两个队列,记为 queue1 和 queue2。
  2. push 操作:将新元素压入非空的队列中,保持另一个队列为空。
  3. pop 操作:将非空队列中的元素依次出队并压入另一个队列,直到只剩下一个元素,然后将该元素出队即可。
  4. top 操作:与 pop 操作类似,但不需要将最后一个元素出队,而是直接返回即可。
  5. empty 操作:判断两个队列是否都为空。

使用这种方法,每次执行 pop 或 top 操作时,都需要将一个队列中的元素全部转移到另一个队列中,以维持栈的特性。这样可以保证栈顶元素总是位于非空队列的队尾,从而实现栈的后入先出的行为。

这种实现方法虽然需要额外的空间和时间复杂度,但是能够满足栈的功能要求。

// 使用两个队列实现栈数据结构
/**
 * Initialize your data structure here.
 */
var MyStack = function() {
  // 初始化两个队列
  this.queue1 = []; // 主要存储栈中的元素
  this.queue2 = []; // 辅助队列,用于在pop操作时暂存元素
};

/**

  • Push element x onto stack.
  • @param {number} x
  • @return {void}
    */
    MyStack.prototype.push = function(x) {
    // 将新元素压入非空队列中
    this.queue1.push(x);
    };

/**

  • Removes the element on top of the stack and returns that element.
  • @return {number}
    */
    MyStack.prototype.pop = function() {
    // 如果queue1为空,则将queue2作为暂存队列
    if (!this.queue1.length) {
    [this.queue1, this.queue2] = [this.queue2, this.queue1];
    }
    // 将queue1中除最后一个元素外的所有元素转移到queue2中
    while (this.queue1.length > 1) {
    this.queue2.push(this.queue1.shift());
    }
    // 返回queue1中的最后一个元素,即栈顶元素
    return this.queue1.shift();
    };

/**

  • Get the top element.
  • @return {number}
    */
    MyStack.prototype.top = function() {
    // 获取栈顶元素
    const x = this.pop(); // 调用pop方法获取栈顶元素
    this.queue1.push(x); // 将栈顶元素重新压入queue1中
    return x; // 返回栈顶元素
    };

/**

  • Returns whether the stack is empty.
  • @return {boolean}
    */
    MyStack.prototype.empty = function() {
    // 判断两个队列是否都为空
    return !this.queue1.length && !this.queue2.length;
    };

这段代码使用两个队列实现了栈的数据结构,下面是对其的总结:

  1. 数据结构:这段代码实现了一个栈的数据结构,使用了两个队列来模拟栈的行为。
  2. 构造函数:通过构造函数 MyStack 来初始化栈,其中使用了两个空数组作为队列。
  3. 入栈操作:push 方法用于将元素压入栈中,将元素添加到 queue1 中。
  4. 出栈操作:pop 方法用于移除栈顶元素并返回,若 queue1 为空,则将 queue2 赋值给 queue1,然后将 queue1 中除了最后一个元素外的元素移到 queue2 中,最后返回 queue1 中的最后一个元素。
  5. 获取栈顶元素:top 方法用于获取栈顶元素,实际上调用了 pop 方法获取栈顶元素,并在返回前将该元素重新压入 queue1 中。
  6. 判空操作:empty 方法用于判断栈是否为空,当 queue1 和 queue2 都为空时返回 true,否则返回 false
  7. 队列切换:在 pop 方法中,当 queue1 为空时,通过 [this.queue1, this.queue2] = [this.queue2, this.queue1] 将 queue2 赋值给 queue1,实现队列的切换。
  8. 元素移动:在 pop 方法中,通过循环将 queue1 中除了最后一个元素外的所有元素移动到 queue2 中,以实现出栈操作。
  9. 栈顶元素获取:在 top 方法中,通过调用 pop 方法获取栈顶元素,并在返回前将该元素重新压入 queue1 中,以实现获取栈顶元素的操作。

3.小结

队列(Queue)是计算机科学中一种常见的数据结构,具有先进先出(First-In-First-Out,FIFO)的特性,即最先进入队列的元素最先被移出。以下是队列的特性:

  1. FIFO特性: 队列的最显著特性是FIFO,即先进入队列的元素先被移出。这种特性保证了队列中元素的顺序性,使得队列适用于许多需要按顺序处理数据的场景,如任务调度、打印队列等。
  2. 基本操作: 队列有三种基本操作:入队(enqueue)、出队(dequeue)和获取队头元素(front)。入队操作将元素添加到队列的末尾,出队操作移除队列中的第一个元素并返回,获取队头元素则是返回队列中的第一个元素但不移除。
  3. 单向访问: 队列是一种单向访问数据结构,只能从队列的一端添加元素(尾部入队),从另一端移除元素(头部出队)。这种单向性质使得队列的操作具有明确的方向性,简化了操作实现和使用。
  4. 容量限制: 队列可以有容量限制,即队列的长度有上限,称为有界队列(bounded queue)。当队列达到容量上限时,入队操作将无法执行,这种情况下称队列为满(full);而在队列为空时执行出队操作会引发队列为空的异常。
  5. 无界队列: 与有界队列相对应,无界队列(unbounded queue)没有容量限制,可以动态地增长以容纳更多元素。这种类型的队列在某些场景下更为灵活,但也可能导致内存消耗过大或性能下降。
  6. 队列的实现: 队列可以通过多种方式实现,包括基于数组、链表、环形缓冲区等。不同的实现方式具有不同的优缺点,选择合适的实现方式取决于具体应用场景和需求。
  7. 线程安全性: 在并发环境中,队列的线程安全性至关重要。许多编程语言提供了线程安全的队列实现,例如Java中的ConcurrentLinkedQueue,它使用了CAS(Compare and Swap)操作来确保并发访问的安全性。
  8. 应用领域: 队列在计算机科学中有广泛的应用,包括任务调度、消息传递、缓冲区管理、广度优先搜索等。在实际编程中,队列常用于解决各种问题,例如实现多线程之间的通信、处理异步任务等。
  9. 性能分析: 队列的性能取决于其实现方式、操作复杂度以及元素数量等因素。通常情况下,入队和出队操作的时间复杂度为O(1),但在特定情况下可能会有所不同。
  10. 优化策略: 针对特定应用场景,可以采用不同的优化策略来改善队列的性能,例如使用双端队列(Deque)实现更高效的操作、合并多个队列以降低系统开销等。

总的来说,队列作为一种简单而有效的数据结构,在计算机科学中有着广泛的应用,通过合理地利用其特性和操作,可以有效地解决各种问题,提高程序的效率和可靠性。


这是一个从 https://juejin.cn/post/7369132465020108826 下的原始话题分离的讨论话题