• 数据结构——栈&队列

    一、数据结构

    概念：

    • 数据结构（data structure）是计算机中存储、组织数据的方式

    常见的数据结构：

    • 栈、队列、链表、集合、字典、树...

    注：

    常见的数据结构较多, 每一种都有其对应的应用场景, 不同数据结构的不同操作性能是不同的

    数据结构和语言无关, 基本常见的编程语言都有直接或者间接的使用上述常见的数据结构

     算法：

    • 一个有限指令集, 每条指令的描述不依赖于语言

    • 接受一些输入（有些情况下不需要输入）

    • 产生输出

    • 一定在有限步骤之后终止

    • 解决问题的办法/步骤逻辑

    注：数据结构的实现, 离不开算法

    二、栈

    栈结构：

    • 是一种运算受限的线性表 其限制是仅允许在表的一端进行插入和删除运算
    • 受限的这一端被称为栈顶，相对地，把另一端称为栈底
    • 后进先出 last in first out (LIFO) ：后进入的元素先弹出栈空间，先进入的元素后弹出栈空间

    • 向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素

    • 从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素

    程序实现栈结构：

    栈的常见操作：

    • push(element): 添加一个新元素到栈顶位置.

    • pop()：移除栈顶的元素，同时返回被移除的元素

    • peek()：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）

    • isEmpty()：如果栈里没有任何元素就返回true，否则返回false

    • clear()：移除栈里的所有元素

    • size()：返回栈里的元素个数。这个方法和数组的length属性很类似

    1.ES5封装栈结构

    （1）将方法绑在函数对象上

    1.  function Stack() {
    2.       //开辟空间，保存栈元素
    3.       this.item = []
    4.  
    5.       //1.向栈顶添加元素  数组的最后添加元素
    6.       this.push = function (el) {
    7.         this.item.push(el)
    8.       }
    9.       //2.移除栈顶元素并返回栈顶元素  数组的最后一个元素
    10.       this.pop = function () {
    11.         return this.item.pop()
    12.       }
    13.       //3.返回栈顶元素  数组的最后一个元素
    14.       this.peek = function () {
    15.         return this.item.length - 1
    16.       }
    17.       //4.判空 栈为空true 数组的length长度来判断栈是否为空
    18.       this.isEmpty = function () {
    19.         return this.item.length == 0
    20.       }
    21.       //5.清空栈
    22.       this.clear = function () {
    23.         this.item = []
    24.       }
    25.       //6.栈元素的个数
    26.       this.size = function () {
    27.         return this.item.length
    28.       }
    29.     }
    30.     let stack = new Stack()
    31.     stack.push(2)
    32.     console.log(stack.item)

     （2）将方法绑在原型上

    1.  function Stack() {
    2.       //开辟空间，保存栈元素
    3.       this.item = []
    4.  
    5.       //1.向栈顶添加元素  数组的最后添加元素
    6.       Stack.prototype.push = function (el) {
    7.         this.item.push(el)
    8.       }
    9.       //2.移除栈顶元素并返回栈顶元素  数组的最后一个元素
    10.       Stack.prototype.pop = function () {
    11.         return this.item.pop()
    12.       }
    13.       //3.返回栈顶元素  数组的最后一个元素
    14.       Stack.prototype.peek = function () {
    15.         return this.item.length - 1
    16.       }
    17.       //4.判空 栈为空true 数组的length长度来判断栈是否为空
    18.       Stack.prototype.isEmpty = function () {
    19.         return this.item.length == 0
    20.       }
    21.       //5.清空栈
    22.       Stack.prototype.clear = function () {
    23.         this.item = []
    24.       }
    25.       //6.栈元素的个数
    26.       Stack.prototype.size = function () {
    27.         return this.item.length
    28.       }
    29.     }
    30.     let stack1 = new Stack()
    31.     stack.push(3)
    32.     console.log(stack.item)

    2.ES6封装栈结构

    1.  class Stack {
    2.             constructor() {
    3.                 //开辟空间，保存栈元素
    4.                 this.item = []
    5.             }
    6.             //1.向栈顶添加元素  数组的最后添加元素
    7.             push(el) {
    8.                 this.item.push(el)
    9.             }
    10.             //2.移除栈顶元素并返回栈顶元素  数组的最后一个元素
    11.             pop() {
    12.                 return this.item.pop()
    13.             }
    14.             //3.返回栈顶元素  数组的最后一个元素
    15.             peek() {
    16.                 return this.item.length - 1
    17.             }
    18.             //4.判空 栈为空true 数组的length长度来判断栈是否为空
    19.             isEmpty() {
    20.                 return this.item.length == 0
    21.             }
    22.             //5.清空栈
    23.             clear() {
    24.                 this.item = []
    25.             }
    26.             //6.栈元素的个数
    27.             size() {
    28.                 return this.item.length
    29.             }
    30.         }
    31.         let stack1 = new Stack()
    32.         stack.push(3)
    33.         console.log(stack.item)

     实例（进制转换）：

    • 引入封装的栈结构
    • 十进制转任意进制：余数压栈  （终止条件：栈为空）
    1.  function Desbasebin(num,base) {
    2.             //1.创建一个空栈
    3.             let stack = new Stack()
    4.             let arr=["A","B","C","D","E","F"]
    5.             while (num > 0) {
    6.                 //余数
    7.                 let yushu = num % base
    8.                 //余数压栈
    9.                 if(yushu>9){
    10.                     //16进制
    11.                     stack.push(arr[yushu-10])
    12.                 }
    13.                 else{
    14.                     stack.push(yushu)
    15.                 }
    16.                 num = Math.floor(num / base)
    17.             }
    18.             // console.log(stack.item)
    19.             let str = ''
    20.             //栈不为空时 依次出栈
    21.             while (!stack.isEmpty()) {
    22.                 str +=stack.pop()
    23.             }
    24.             return str
    25.         }
    26.  
    27.         console.log(Desbasebin(100,2))  //转2进制
    28.         console.log(Desbasebin(100,8))  //转8进制
    29.         console.log(Desbasebin(100,16))  //转16进制

    结果：

     

    三、队列

    队列结构：

    • 是一种运算受限的线性表  先进先出(FIFO First In First Out)

    • 受限之处在于它只允许在表的前端（front）进行删除操作，在表的后端（rear）进行插入操作

    程序实现队列结构：

    队列常见的操作

    • enqueue(element)：向队列尾部添加一个（或多个）新的项

    • dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素

    • front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似）

    • isEmpty()：如果队列中不包含任何元素，返回true，否则返回false

    • size()：返回队列包含的元素个数，与数组的length属性类似

     ES6封装队列结构：

    1.  class Queue {
    2.             constructor() {
    3.                 this.item = []
    4.             }
    5.             //1.入队
    6.             enqueue(el) {
    7.                 this.item.push(el)
    8.             }
    9.             //2.出队
    10.             delqueue() {
    11.                 return this.item.shift()
    12.             }
    13.             //3.返回队首元素
    14.             front() {
    15.                 return this.item[0]
    16.             }
    17.             //4.判空
    18.             isEmpty() {
    19.                 return this.item.length == 0
    20.             }
    21.             //5.返回元素的个数
    22.             size() {
    23.                 return this.item.length
    24.             }
    25.         }

    实例（击鼓传花）：

    • 引入封装的队列结构
    • 让栈中的每第三个元素出栈 前两个元素先出栈再入栈 直到最后只剩一个元素就是获胜者
    1. function game(arr) {
    2.             // 创建队列  依次入队
    3.             let queue = new Queue()
    4.             // for (let i = 0; i < arr.length; i++) {
    5.             //     queue.enqueue(arr[i])
    6.             // }
    7.             arr.forEach(el=> {
    8.                 queue.enqueue(el)
    9.             });
    10.             console.log(queue.item)
    11.             // 数数
    12.             let count = 1
    13.             while (queue.size() > 1) {   //队列中只有一个元素事啊停止
    14.                 if (count < 3) {
    15.                     let node = queue.delqueue() //先出队
    16.                     queue.enqueue(node)    //再入队
    17.                     count++
    18.                 } else {
    19.                     //直接出队
    20.                     queue.delqueue()
    21.                     count = 1
    22.                 }
    23.             }
    24.             return{
    25.                 winner:queue.front(),
    26.                 position:arr.indexOf(queue.front())
    27.             }
    28.  
    29.         }
    30.  
    31.         var arr = ["哈哈哈", "嘻嘻嘻", "呵呵呵", "哟哟哟", "嗷嗷嗷", "哦哦哦"]
    32.         console.log(game(arr))

    结果：

    四、优先级队列

    • 在插入一个元素的时候会考虑该数据的优先级(和其他数据优先级进行比较)
    • 比较完成后, 可以得出这个元素正确的队列中的位置. 其他处理方式, 和队列的处理方式一样

    程序实现优先级队列：

    1.  class Node {
    2.             constructor(data, priority) {
    3.                 this.data = data
    4.                 this.priority = priority
    5.             }
    6.         }
    7.         class PriorityQueue {
    8.             constructor() {
    9.                 this.item = []
    10.             }
    11.             enqueue(ele, priority) {
    12.                 // let newobj={data:ele,pro:priority}
    13.                 //创建新节点
    14.                 let newnode = new Node(data, priority)
    15.  
    16.                 if (this.item.length == 0) {
    17.                      //空队列 直接添加元素到队列中
    18.                     this.item.push(newnode)
    19.                 } else {
    20.                       //非空队列 依次比较优先级
    21.                     let isAdd = false //元素是否被添加到队列中
    22.                     for (let i = 0; i < this.item.length; i++) {
    23.                         console.log(this.item[i])
    24.                         if (newnode.priority < this.item[i].priority) {
    25.                             //新节点的优先级小于队列元素的优先级
    26.                             this.item.splice(i, 0, newnode) //将新节点插入到队列中
    27.                             isAdd = true
    28.                             break
    29.                         }
    30.                     }
    31.                     //循环遍历结束都没有比新节点小的元素，直接添加元素到队列的最后
    32.                     if (!isAdd) {
    33.                         this.item.push(newnode)
    34.                     }
    35.                 }
    36.             }
    37.         }
    38.         let pq=new PriorityQueue()
    39.         pq.enqueue("haha",21)
    40.         pq.enqueue("xixi",13)
    41.         pq.enqueue("yoyo",16)
    42.         pq.enqueue("heihei",4)
    43.         console.log(pq.item)
  • 相关阅读:
    HOT100自查题集
    JWT（简介）
    AI加速(九): 深度理解吞吐量和延时
    【python爬虫】免费爬取网易云音乐完整教程（附带源码）
    回忆初学编程的糗事：愚蠢的代码也是宝贵的学习经验
    测试用例设计方法之判定表法
    vue3 封装使用 pinia （可直接使用，包含数据持久化）
    代码Bug太多？给新人Code Review头都大了？快来试试SpotBugs
    个人财务预算系统BudgetBee
    [Vue]之Jwt的入门和Jwt工具类的使用及Jwt集成spa项目
  • 原文地址：https://blog.csdn.net/qq_56668869/article/details/126473675