数据结构和算法-「队列」上-灵析社区

什么是队列数据结构？

队列是一种线性数据结构。该数据结构遵循执行操作的特定顺序。顺序是先进先出( FIFO )。这意味着队列中最先插入的元素将最先出现，最后插入的元素将最后出现。它是一个有序列表，其中元素的插入是从一端（称为后端）完成的，元素的删除是从另一端（称为前端）完成的。与堆栈类似，可以对队列执行多个操作。当向队列中插入元素时，该操作称为“入队” ；当从队列中删除元素时，该操作称为 “出队”。

重要的是要知道，如果队列大小已满，我们无法插入元素，而当队列本身为空时，我们无法删除元素。如果我们尝试在队列已满后插入元素，则这种情况称为溢出，而如果我们尝试在队列为空后删除元素，则这种情况称为下溢。

我们将队列定义为一个列表，其中对列表的所有添加都在一端进行，而对列表的所有删除都在另一端进行。首先被推入订单的元素，首先对其执行操作。

队列的先进先出原理：

队列就像等待买票的队伍，队列中的第一个人就是第一个得到服务的人。（即先到先得）。
队列中准备被服务的条目的位置，即将从队列中删除的第一个条目，称为队列的前端（有时称为队列* *头 ），类似地，最后一个条目的位置队列中，即最近添加的队列，称为队列的后部（或尾部）。见下图。

队列操作：

void enqueue(int Element)： 执行此操作时，会在队列末尾（即后端）插入一个元素。（其中 T 是通用的，即我们可以定义任何类型的数据结构的队列。）此操作需要常数时间，即 O(1) 。
int dequeue()： 执行该操作时，会从前端移除一个元素并返回。该操作需要常数时间，即 O(1)。
Enqueue() –将一个元素添加（或存储）到队列末尾。其时间复杂度为O(1)。
Dequeue() – 从队列中删除元素。其时间复杂度为O(1)。
Peek() 或 front() -获取队列前端节点可用的数据元素，而不删除它。
after() –此操作返回后端的元素而不删除它。
isFull() –该操作指示队列是否为空。此操作也在 O(1) 内完成。
isNull() –检查队列是否为空。

入队：

Queue 中的 Enqueue() 操作将一个元素添加（或存储）到队列末尾。应采取以下步骤将数据排队（插入）到队列中：

步骤1：检查队列是否已满。
步骤2：如果队列已满，则返回溢出错误并退出。
步骤3：如果队列未满，则递增后指针以指向下一个空空间。
步骤 4：将数据元素添加到队列位置，即后部指向的位置。
步骤 5：返回成功。

出队：

从队列中删除（或访问）第一个元素。执行出队操作的步骤如下：

步骤1： 检查队列是否为空。
步骤2： 如果队列为空，则返回下溢错误并退出。
步骤3： 如果队列不为空，则访问front指向的数据。
步骤 4： 增加前指针以指向下一个可用数据元素。
步骤 5： 返回成功。

 dequeue(){
   // 从队列中移除元素
   // 在空队列上调用时返回下溢
   if(this.isEmpty()){
       console.log("Queue is empty");
       return -1;
   }
   return this.items.shift();
 }

队列类型：

简单队列：简单队列也称为线性队列，是队列的最基本版本。这里，插入元素即入队操作发生在队尾，移除元素即出队操作发生在队首。
循环队列：在循环队列中，队列的元素充当圆环。循环队列的工作原理与线性队列类似，只是最后一个元素连接到第一个元素。它的优点是可以更好地利用内存。这是因为如果存在空白空间，即如果队列中的某个位置不存在元素，则可以轻松地在该位置添加元素。
优先级队列：该队列是一种特殊类型的队列。它的特点是它根据某种优先级排列队列中的元素。优先级可以是具有最高值的元素具有优先级，因此它创建一个按值降序排列的队列。优先级也可以是具有最低值的元素获得最高优先级，因此它依次创建一个值顺序递增的队列。
双端队列：顾名思义，双端队列意味着可以从队列的两端插入或删除元素，这与其他队列只能从一端插入或删除元素不同。由于此属性，它可能不遵守先进先出属性。

队列的实现：

顺序分配： 队列可以使用数组来实现。它可以组织有限数量的元素。
链表分配： 队列可以使用链表来实现。它可以组织无限数量的元素。

队列的应用：

多重编程：多重编程是指主存中同时运行多个程序。组织这些多个程序是至关重要的，并且这些多个程序被组织为队列。
网络：在网络中，队列用于路由器或交换机等设备。队列的另一个应用是邮件队列，它是存储数据和控制邮件消息文件的目录。
作业调度：计算机有一项任务来执行特定数量的作业，这些作业被安排一个接一个地执行。这些作业被一一分配给使用队列组织的处理器。
共享资源：队列用作单个共享资源的等待列表。

Queue的应用：

ATM 亭排队
售票柜台排队
键盘上的按键顺序
CPU任务调度
每个客户在呼叫中心的等待时间。

队列的优点：

可以轻松有效地管理大量数据。
由于遵循先进先出的规则，可以轻松执行插入和删除等操作。
当多个消费者使用特定服务时，队列非常有用。
队列对于数据进程间通信的速度很快。
队列可以用于其他数据结构的实现。

队列的缺点：

从中间插入、删除元素等操作比较耗时。
空间有限。
在经典队列中，只有从队列中删除现有元素后才能插入新元素。
搜索元素需要 O(N) 时间。
必须事先定义队列的大小。

队列的数组表示:

 // Queue class
 class Queue
 {
// 数组用于实现队列
   constructor()
   {
     this.items = [];
   }
 }

队列的链表表示:

 class QNode
 {
   constructor(key)
   {
     this.key = key;
     this.next = null;
   }
 }
  
 let front = null, rear = null;

队列代码示例

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

---来自百科

golang 实现一个 LRU 的 cache

package main

import (
    "fmt"
    "testing"
)

type LRUCache struct {
    list  []int
    csize int
    ma    map[int]int
}

func (lru *LRUCache) refer(x int) {
    if index, ok := lru.ma[x]; !ok {
        // 如果存在,比较当前的容量是否已达上限
        if len(lru.list) == lru.csize {
            // 如果已达上限,则删除栈顶元素
            lru.list = lru.list[:lru.csize-1]
        }
    } else {
        // 如果存在, 则删除对应 index 位置的值, 并将期追加到队尾
        lru.list = append(lru.list[:index-1], lru.list[index+1:]...)
    }
    lru.list = append(lru.list, x)
    lru.ma[x] = len(lru.list)
}
// 打印 cache 中的元素
func (lru *LRUCache) Display() {
    for i := len(lru.list) - 1; i >= 0; i-- {
        fmt.Println(lru.list[i])
    }
}

// 初始化 lru cache
func NewLRUCache(size int) *LRUCache {
    ma := make(map[int]int)
    return &LRUCache{
        list:  []int{},
        csize: size,
        ma:    ma,
    }
}

// 测试程序
func Test_NewLRUCache(t *testing.T) {
    cache := NewLRUCache(4)
    cache.refer(1)
    cache.refer(2)
    cache.refer(3)
    cache.refer(1)
    cache.refer(4)
    cache.refer(5)

    cache.Display()
}