AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

手写数据结构 队列篇

2023-12-08 73
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 手写数据结构 队列篇

1. 队列简介

我们已经学习了栈。队列和栈非常类似，但是使用了与后进先出不同的原则。你将在本章学习这些内容。我们同样要学习双端队列的工作原理。双端队列是一种将栈的原则和队列的原则混合在一起的数据结构。

队列是遵循 先进先出(FIFO) 原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

在现实中，最常见的队列的例子就是排队。在电影院、自助餐厅、杂货店收银台，我们都会排队。排在第一位的人会先接受服务。

在计算机科学中，一个常见的例子就是打印队列。比如说我们需要打印五份文档。我们会打开每个文档，然后点击打印按钮。每个文档都会被发送至打印队列。第一个发送到打印队列的文档会首先被打印，以此类推，直到打印完所有文档。

1.1. 实现

const Queue = (() => {
  const store = new WeakMap();
  class Queue {
    constructor() {
      store.set(this, { _items: [] });
    }
    // 只读 队列大小
    get size() {
      return store.get(this)._items.length;
    }
    // 只读 是否为空
    get isEmpty() {
      return this.size === 0;
    }
    // 进入队列
    enqueue(ele) {
      store.get(this)._items.push(ele);
      return this.size;
    }
    // 退出队列
    dequeue() {
      return store.get(this)._items.shift();
    }
    // 返回队列第 1 个元素
    peek() {
      return store.get(this)._items[0];
    }
    // 默认迭代器 用于展示所有元素
    [Symbol.iterator]() {
      let i = 0;
      return {
        next: () => ({ value: store.get(this)._items[i], done: i++ === this.size }),
        [Symbol.iterator]() {
          return this;
        },
      };
    }
    // 清空所有元素
    clear() {
      store.get(this)._items = [];
    }
  }
  return Queue;
})();

1.2. 使用

const queue = new Queue();
queue.size = 2;
console.log(queue.size);
// -> 0
console.log(queue);
// -> Queue {}
console.log(queue.enqueue('apple'));
// -> 1
console.log(queue.enqueue('orange'));
// -> 2
console.log(queue.enqueue('pear'));
// -> 3
console.log(...queue);
// -> 'apple' 'orange' 'pear'
console.log(queue.dequeue());
// -> 'apple'
console.log(queue.peek());
// -> 'orange'
console.log(queue.size);
// -> 2
queue.clear();
console.log(queue.isEmpty);
// -> true
console.log(queue.peek());
// -> undefined

2. 双端队列

双端队列(double-ended queue) 是一种允许我们同时从前端和后端添加和移除元素的特殊队列。

双端队列在现实生活中的例子有电影院、餐厅中排队的队伍等。举个例子，一个刚买了票的人如果只是还需要再问一些简单的信息，就可以直接回到队伍的头部。另外，在队伍末尾的人如果赶时间，他可以直接离开队伍。

在计算机科学中，双端队列的一个常见应用是存储一系列的撤销操作。每当用户在软件中进行了一个操作，该操作会被存在一个双端队列中（就像在一个栈里）。当用户点击撤销按钮时，该操作会被从双端队列中弹出，表示它被从后面移除了。在进行了预先定义的一定数量的操作后，最先进行的操作会被从双端队列的前端移除。由于双端队列同时遵守了先进先出和后进先出原则，可以说它是把队列和栈相结合的一种数据结构。

2.1. 实现

const Dequeue = (() => {
  const store = new WeakMap();
  class Dequeue {
    constructor() {
      store.set(this, { _items: [] });
    }
    // 只读 元素数量
    get size() {
      return store.get(this)._items.length;
    }
    // 只读 是否为空
    get isEmpty() {
      return this.size === 0;
    }
    // 在前面添加元素
    addFront(ele) {
      store.get(this)._items.unshift(ele);
      return this.size;
    }
    // 在前面移除元素
    removeFront() {
      return store.get(this)._items.shift();
    }
    // 在后面添加元素
    addBack(ele) {
      store.get(this)._items.push(ele);
      return this.size;
    }
    // 在后面移除元素
    removeBack() {
      return store.get(this)._items.pop();
    }
    // 返回第1个元素
    peekFront() {
      return store.get(this)._items[0];
    }
    // 返回最后一个元素
    peekBack() {
      return store.get(this)._items[this.size - 1];
    }
    // 默认迭代器 展示所有元素
    [Symbol.iterator]() {
      let i = 0;
      return {
        next: () => ({ value: store.get(this)._items[i], done: i++ === this.size }),
        [Symbol.iterator]() {
          return this;
        },
      };
    }
    // 清空所有元素
    clear() {
      store.get(this)._items = [];
    }
  }
  return Dequeue;
})();

2.2. 使用

const dequeue = new Dequeue();
dequeue.size = 2;
console.log(dequeue.size);
// -> 0
console.log(dequeue.addBack('orange'));
// -> 1
console.log(dequeue.addBack('pear'));
// -> 2
console.log(dequeue.addFront('apple'));
// -> 3
console.log(...dequeue);
// -> 'apple' 'orange' 'pear'
console.log(dequeue.peekFront());
// -> 'apple'
console.log(dequeue.peekBack());
// -> 'pear'
console.log(dequeue.removeBack());
// -> 'pear'
console.log(dequeue.removeFront());
// -> 'apple'
dequeue.clear();
console.log(dequeue.size);
// -> 0
console.log(dequeue);
// -> Dequeue {}

3.优先队列

在一般情况下，从队列中删除的元素，一定是率先入队的元素。但是也有一些使用队列的

应用，在删除元素时不必遵守先进先出的约定。这种应用，需要使用一个叫做优先队列的

数据结构来进行模拟。

从优先队列中删除元素时，需要考虑优先权的限制。比如医院急诊科（Emergency Department）的候诊室，就是一个采取优先队列的例子。当病人进入候诊室时，分诊护士会评估患者病情的严重程度，然后给一个优先级代码。高优先级的患者先于低优先级的患者就医，同样优先级的患者按照先来先服务的顺序就医。

3.1实现

const PriorityQueue = (() => {
    const store = new WeakMap();
    // 优先队列内部的元素类
    class QueueElement {
        constructor(element, priority) {
            this.element = element;
            this.priority = priority;
        }
    }
    class PriorityQueue {
        constructor() {
            store.set(this, { _items: [] });
        }
        // 只读 队列大小
        get size() {
            return store.get(this)._items.length;
        }
        // 只读 是否为空
        get isEmpty() {
            return this.size === 0;
        }
        // enqueue(element, priority) 入队，将元素按优先级加入到队列中
        // 重写 enqueue()
        enqueue(element, priority) {
            // 根据传入的元素，创建 QueueElement 对象
            const queueElement = new QueueElement(element, priority);
            // 判断队列是否为空
            if (this.isEmpty) {
                // 如果为空，不用判断优先级，直接添加
                store.get(this)._items.push(queueElement);
            } else {
                // 定义一个变量记录是否成功添加了新元素
                let added = false;
                for (let i = 0; i < this.size; i++) {
                    // 让新插入的元素进行优先级比较，priority 值越小，优先级越大
                    if (queueElement.priority < store.get(this)._items[i].priority) {
                        // 在指定的位置插入元素
                        store.get(this)._items.splice(i, 0, queueElement);
                        added = true;
                        break;
                    }
                }
                // 如果遍历完所有元素，优先级都大于新插入的元素，就将新插入的元素插入到最后
                if (!added) {
                    store.get(this)._items.push(queueElement);
                }
            }
            return this.size;
        }
        // 退出队列
        dequeue() {
            return store.get(this)._items.shift();
        }
        // 返回队列第 1 个元素
        peek() {
            return store.get(this)._items[0];
        }
        // 默认迭代器 用于展示所有元素
        [Symbol.iterator]() {
            let i = 0;
            return {
                next: () => ({ value: store.get(this)._items[i], done: i++ === this.size }),
                [Symbol.iterator]() {
                    return this;
                },
            };
        }
        // 清空所有元素
        clear() {
            store.get(this)._items = [];
        }
        // toString() 将队列中元素以字符串形式返回
        // 重写 toString()
        toString() {
            let result = "";
            for (let item of store.get(this)._items) {
                result += item.element + "-" + item.priority + " ";
            }
            return result;
        }
    }
    return PriorityQueue
})()

3.2使用

const queue = new PriorityQueue();
queue.size = 2;
console.log(queue.size);
// -> 0
console.log(queue);
// -> PriorityQueue {}
console.log(queue.enqueue('apple', 2));
// -> 1
console.log(queue.enqueue('orange', 1));
// -> 2
console.log(queue.enqueue('pear', 4));
// -> 3
console.log(...queue);
// -> 'apple' 'orange' 'pear'
console.log(queue.dequeue());
// -> 'apple'
console.log(queue.peek());
// -> 'orange'
console.log(queue.size);
// -> 2
queue.clear();
console.log(queue.isEmpty);
// -> true
console.log(queue.peek());
// -> undefined


文章标签：
前端开发
存储
关键词：
数据结构队列
默海笑
目录
相关文章
ephemerals__
|
4月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
393 9
RossyYan
|
2月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
160 77
蓝易云
|
11天前
|
算法 调度 C++
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例，希望能帮助读者更好地理解和应用这些重要的数据结构。
蓝易云
26 11
羑悻的小杀马特
|
24天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法：用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下： 1. **用两个队列实现栈**： - 插入元素时，选择非空队列进行插入。 - 移除栈顶元素时，将非空队列中的元素依次转移到另一个队列，直到只剩下一个元素，然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**： - 插入元素时，选择非空栈进行插入。 - 移除队首元素时，将非空栈中的元素依次转移到另一个栈，再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
羑悻的小杀马特
31 14
RossyYan
|
2月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
【数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务：编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧，祝你成功！(4)出队一个元素a。(4)出队一个元素x。
RossyYan
54 13
【C++数据结构——栈与队列】环形队列的基本运算（头歌实践教学平台习题）【合集】
RossyYan
|
2月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现链栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储整数，最大
RossyYan
52 9
RossyYan
|
2月前
|
C++
【C++数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】
【数据结构——栈和队列】括号配对（头歌实践教学平台习题）【合集】（1）遇到左括号：进栈Push()（2）遇到右括号：若栈顶元素为左括号，则出栈Pop()；否则返回false。（3）当遍历表达式结束，且栈为空时，则返回true，否则返回false。本关任务：编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务，你需要掌握：栈对括号的处理。（1）遇到左括号：进栈Push()开始你的任务吧，祝你成功！测试输入：(()))
RossyYan
48 7
龙大吉
|
4月前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
107 5
肾透侧视攻城狮
|
4月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
50 1
禁默
|
5月前
初步认识栈和队列
初步认识栈和队列
禁默
79 10