目 录CONTENT

文章目录

队列(Queue):“先进先出”的数据结构

Hello!你好!我是村望~!
2023-01-10 / 0 评论 / 0 点赞 / 139 阅读 / 1,655 字
温馨提示:
我不想探寻任何东西的意义,我只享受当下思考的快乐~

队列(Queue):“先进先出”的数据结构

队列线性表的一种,在操作数据元素时,和一样,有自己的规则:使用队列存取数据元素时,数据元素只能从表的一端进入队列,另一端出队列

img

  • 队列从一端存入数据,另一端调取数据的原则称为“先进先出”原则。(first in first out,简称“FIFO”)
  • 根据队列的先进先出原则,(a1,a2,a3,…,an)中,由于 a1 最先从队尾进入队列,所以可以最先从队头出队列,对于 a2 来说,只有 a1 出队之后,a2 才能出队。

类似于日常生活中排队买票,先排队(入队列),等自己前面的人逐个买完票,逐个出队列之后,才轮到你买票。买完之后,你也出队列。先进入队列的人先买票并先出队列(不存在插队)。

队列的实际应用

队列在操作系统中应用的十分广泛,比如用它解决 CPU 资源的竞争问题。

对于一台计算机来说,CPU 通常只有 1 个,是非常重要的资源。如果在很短的时间内,有多个程序向操作系统申请使用 CPU,就会出现竞争 CPU 资源的现象。不同的操作系统,解决这一问题的方法是不一样的,有一种方法就用到了队列这种存储结构。

假设在某段时间里,有 A、B、C 三个程序向操作系统申请 CPU 资源,操作系统会根据它们的申请次序,将它们排成一个队列。

根据“先进先出”原则,最先进队列的程序出队列,并获得 CPU 的使用权。

待该程序执行完或者使用 CPU 一段时间后,操作系统会将 CPU 资源分配给下一个出队的程序,以此类推。

如果该程序在获得 CPU 资源的时间段内没有执行完,则只能重新入队,等待操作系统再次将 CPU 资源分配给它。

队列还可以用来解决一些实际问题,比如实现一个简单的停车场管理系统、实现一个推小车卡牌游戏等

队列的具体实现

和栈的实现方案一样,队列的实现也有两种方式,分别是:

  • 顺序队列:用顺序表模拟实现队列存储结构;
  • 链队列:用链表模拟实现队列存储结构。

这里我们还是先用 JavaScript 内置的数组顺序存储结构,来实现我们的队列

一个队列类,应有的属性和方法

interface Iqueue<T> {
  items: T[]; // 顺序队列 底层一样基于数组实现!
  enQueue(ele: T): T[]; // 入队
  deQueue(): T; // 出队
  toString(): string; // 队列字符串化
  size(): number; // 队列长度
  front(): T; // 排在队伍最前面的元素
}
export default class Queue<T> implements Iqueue<T> {

  items: T[] = [];

  enQueue(ele: T): T[] {
    this.items.unshift(ele);
    return this.items;
  }
  deQueue(): T {
    return this.items.pop() as T
  }
  size(): number {
    return this.items.length;
  }
  toString(): string {
    return this.items.toString();
  }
  front(): T {
    return this.items[0]
  }
}

测试队列 [按照个人习惯,队伍是从右往左排队的]

import Queue from "./2.线性结构Queue 队列";
import { passGame } from "./2.线性结构Queue 队列/击鼓传花";

const q = new Queue<number>();

q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
console.log(q.toString()); // 3,2,1

q.deQueue(); // 最前面的 1 出队

console.log(q.toString());  // 3,2
console.log(q.size());      // 2
console.log(q.front());     // 3

约瑟夫环

约瑟夫环问题,题意是:已知 n 个人(分别用编号 1,2,3,…,n 表示)围坐在一张圆桌周围,从编号为 k 的人开始顺时针报数,数到 m 的那个人出列;他的下一个人又从 1 开始,还是顺时针开始报数,数到 m 的那个人又出列;依次重复下去,直到圆桌上剩余一个人。

循环链表实现约瑟夫环

出列顺序依次为:

  • 编号为 3 的人开始数,数到2的人被淘汰,他先数 1,然后 4 数 2,所以 4 先出列;
  • 4 出列后,从 5 开始数 1,1 数 2,所以 1 出列;
  • 1 出列后,从 2 开始数 1,3 数 2,所以 3 出列;
  • 3 出列后,从 5 开始数 1,2 数 2,所以 2 出列;
  • 最后只剩下 5 自己,所以 5 胜出。
import Queue from ".";

/**
 * 
 * @param list 玩游戏的人
 * @param point 数的数字
 * @description 游戏规则,从第某一个人开始数数!数到某个数字的人被淘汰,最后一个人存活!
 */
export function passGame(nameList: string[], point: number): string {
    // 1. 创建一个队列
    const q = new Queue<string>()
    // 2. 首先把所有人放到队列中
    for (let i = 0; i < nameList.length; i++) {
        q.enQueue(nameList[i])
    }
    // 3. 如果队列长度大于1 则证明游戏尚未结束
    while (q.size() > 1) {
        /**
         *  3.1 每一次都从队列的第一个人开始,数到目标 point 
         *  尚未到目标值之前,也就是 point - 1 ,都把数过的元素,重新放到队列后面,继续新一轮的游戏
         */
        for (let idx = 0; idx < point - 1; idx++) {
            q.enQueue(q.deQueue())
        }
        // 3.3 数到 point 的就代表游戏结束,踢出队列
        q.deQueue()
    }
    return q.front()
}

测试代码:

const list = ['雷神将军', "琴", "凝光", "七七", "烟绯"]

const winner = passGame(list, 3)

console.log({winner}); // { winner: '七七' }

那么这个过程就是

  • 先把list排好队,

    • 按照队列 入 => [ '烟绯', '七七', '凝光', '琴', '雷神将军' ] => 出
  • 雷电将军开始数,数到凝光被淘汰,刚刚数过的就继续从新排队进入队列,

    • [ '琴', '雷神将军', '烟绯', '七七' ]
  • 然后继续从七七开始数,数到雷神将军被淘汰 [ '烟绯', '七七', '琴' ]

  • 然后从'琴'开始数,数到 '烟绯',被淘汰 [ '七七', '琴' ]

  • 最后 又从开始 数到 琴自己被淘汰,七七获胜

0

评论区