前言

在之前的数组中，我们可以通过索引随机访问元素，但是在某些情况下，我们可能要限制数据的访问顺序，于是有了两种限制访问顺序的数据结构：栈（先进后出）、队列（先进先出），两者拥有相似的数据结构，所以我们这里一起讨论

栈

首先来一张图：

故此我们可以得出以下结论：
栈（stack）是一种运算受限的线性表：

LIFO（last in first out）表示就是后进入的元素，第一个弹出栈空间。类似于自动餐托盘，最后放上的托盘，往往先把拿出去使用。
其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。
向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

总结一下：先进先出，后进后出，一端操作
**
生活中也有相当一部分的栈结构：

自助餐的托盘
收到的实体文件（最新到的优先处理）（但是如果有选择性开始，则是队列或者优先级队列结构）

程序中的典型栈：

函数的调用栈（函数的调用原理）：A(B(C(D())))
递归：这里就有一个经典的栈溢出问题：比如函数 A 为递归函数，不断地调用自己（因为函数还没有执行完，不会把函数弹出栈），不停地把相同的函数 A 压入栈，最后造成栈溢出（Queue Overfloat）

练习

A 答案：65 进栈，5 出栈，4 进栈出栈，3 进栈出栈，6 出栈，21 进栈，1 出栈，2 出栈（整体入栈顺序符合 654321）。（√）
B 答案：654 进栈，4 出栈，5 出栈，3 进栈出栈，2 进栈出栈，1 进栈出栈，6 出栈（整体的入栈顺序符合 654321）。（√）
C 答案：6543 进栈，3 出栈，4 出栈，之后应该 5 出栈而不是 6，所以错误。（×）
D 答案：65432 进栈，2 出栈，3 出栈，4 出栈，1 进栈出栈，5 出栈，6 出栈。符合入栈顺序。（√）

栈的封装

方法：

基于数组
基于链表

因为是我们这里基于数组的基础上，所以暂时先讨论数组方式的实现(这里我们可以封装一些栈的常用操作)

push() 添加一个新元素到栈顶位置。
pop() 移除栈顶的元素，同时返回被移除的元素。
peek() 返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶的元素，仅仅返回它）。
isEmpty() 如果栈里没有任何元素就返回 true，否则返回 false。
size() 返回栈里的元素个数。这个方法和数组的 length 属性类似。
toString() 将栈结构的内容以字符串的形式返回。

class Stack{
    constructor(){
        this.items=[];
    }
    push(item){
        return this.items.push(item)
    }
    pop(){
        return this.items.pop()
    }
    peek(){
        return this.items[length-1]
    }
    isEmpty(){
        return this.items.length===0
    }
    size(){
        return this.items.length
    }
    toString(){
        let string='';
        for (const item in this.items) {
            string+=item+''
        }
        return string
    }
}

栈的典型应用

十进制转换为二进制的方法

function dec2bin(dec){
    let stack=new Stack();
    while(dec>0){
        stack.push(dec%2);
        dec = Math.floor(dec/2)
    }
    let string='';
    while(!stack.isEmpty()){
        string+=stack.pop()
    }

    return string
}

队列

队列（Queue）是一种运算受限的线性表，特点：先进先出。(FIFO：First In First Out)

只允许在表的前端（front）进行删除操作。
只允许在表的后端（rear）进行插入操作。

如下图：

总结一下：先进先出，前出后入

生活中也有相当一部分的栈结构：

排队，比如在电影院，商场，甚至是厕所排队。
优先排队的人，优先处理。 (买票、结账、WC)。

程序中的典型栈：

打印队列：计算机打印多个文件的时候，需要排队打印。
线程队列：当开启多线程时，当新开启的线程所需的资源不足时就先放入线程队列，等待 CPU 处理。

队列的封装

队列的实现和栈一样，有两种方案：

基于数组实现。
基于链表实现。

队列常见的操作

enqueue(element) 向队列尾部添加一个（或多个）新的项。
dequeue() 移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
front() 返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息与 Map 类的 peek 方法非常类似）。
isEmpty() 如果队列中不包含任何元素，返回 true，否则返回 false。
size() 返回队列包含的元素个数，与数组的 length 属性类似。
toString() 将队列中的内容，转成字符串形式。

class Queue {

  constructor() {
    this.items = [];
  }

  // enqueue(item) 入队，将元素加入到队列中
  enqueue(item) {
    this.items.push(item);
  }

  // dequeue() 出队，从队列中删除队头元素，返回删除的那个元素
  dequeue() {
    return this.items.shift();
  }

  // front() 查看队列的队头元素
  front() {
    return this.items[0];
  }

  // isEmpty() 查看队列是否为空
  isEmpty() {
    return this.items.length === 0;
  }

  // size() 查看队列中元素的个数
  size() {
    return this.items.length;
  }

  // toString() 将队列中的元素以字符串形式返回
  toString() {
    let result = '';
    for (let item of this.items) {
      result += item + ' ';
    }
    return result;
  }
}

队列的典型应用

击鼓传花：传入一组数据集合和设定的数字 number，循环遍历数组内元素，遍历到的元素为指定数字 number 时将该元素删除，直至数组剩下一个元素。

dfunction passGame(list,number){
    const queue=new Queue();
    for (const item of list) {
        queue.enqueue(item)
    }
    while(queue.size()>1){
        for(let i=0;i<number-1;i++){
            queue.enqueue(queue.dequeue())
        }
        queue.dequeue()
    }
    const end = queue.front();
    return list.indexOf(end)
}

优先队列

与普通队列的区别：

插入元素时会考虑元素的优先级，并和其他数据的优先级比较，再插入正确的位置

优先级队列主要考虑的问题：

每个元素不再只是一个数据，还包含优先级。
在添加元素过程中，根据优先级放入到正确位置。

生活中类似优先队列的场景：

优先排队的人，优先处理。 (买票、结账、WC)。
排队中，有紧急情况（特殊情况）的人可优先处理。

程序中：

比如每个线程的重要性不同，我们可以通过优先级大小，来决定处理的次序

  class QueueElement {
    constructor(element, priority) {
      this.element = element;
      this.priority = priority;
    }
  }

  class PriorityQueue extends Queue{
      constructor(){
          super()
      }
      enqueue(element,priority){
          let queueElement=new QueueElement(element,priority);
          if(this.isEmpty()){
              this.items.push(queueElement)
          }else{
              for(let i=0;i<this.items.length;i++){
                  if(queueElement.priority>this.items[i].priority){
                      this.items.splice(i,0,queueElement)
                      break
                  }
            }
      }
    }
      dequeue() {
        return super.dequeue();
      }

      front() {
        return super.front();
      }
      isEmpty() {
        return super.isEmpty();
      }

      size() {
        return super.size();
      }
      toString() {
        let result = '';
        for (let item of this.items) {
          result += item.element + '-' + item.priority + ' ';
        }
        return result;
      }
  }

  const priorityQueue = new PriorityQueue();

// 入队 enqueue() 测试
priorityQueue.enqueue('A', 10);
priorityQueue.enqueue('B', 15);
priorityQueue.enqueue('C', 11);
priorityQueue.enqueue('D', 20);
priorityQueue.enqueue('E', 18);
console.log(priorityQueue);
//--> output:
// QueueElement {element: "A", priority: 10}
// QueueElement {element: "C", priority: 11}
// QueueElement {element: "B", priority: 15}
// QueueElement {element: "E", priority: 18}
// QueueElement {element: "D", priority: 20}

// 出队 dequeue() 测试
priorityQueue.dequeue();
priorityQueue.dequeue();
console.log(priorityQueue);
//--> output:
// QueueElement {element: "B", priority: 15}
// QueueElement {element: "E", priority: 18}
// QueueElement {element: "D", priority: 20}

// isEmpty() 测试
console.log(priorityQueue.isEmpty()); //--> false

// size() 测试
console.log(priorityQueue.size()); //--> 3

// toString() 测试
console.log(priorityQueue.toString()); //--> B-15 E-18 D-20

算法与数据结构

线性结构（二）———栈和队列（基于数组）

前言

栈

练习

栈的封装

栈的典型应用

队列

队列的封装

队列的典型应用

优先队列