数据结构与算法 - 栈和队列

优质

小牛编辑

118浏览

2023-12-01

栈(Stack) 是限定仅在表尾进行插入和删除操作的线性表。对前前端工程师来说日操作浏览后退前进

我们把允许插入和删除的一端为栈顶(top)，另一端为栈底(bottom)。栈又称为 后进先出 (Last In Firsot Out)的线性表，简称 LIFO 结构。

栈的实现

数组 - 顺序栈（内存地址连续性）
链表 - 链式栈

数组 - 顺序栈

用数组来一实现个栈

/**
 push(element)：添加一个（或几个）新元素到栈顶
 pop()：移除栈顶的元素，同时返回被移除的元素
 peek()：返回栈顶的元素，不对栈做任何修改
 isEmpty()：如果栈里没有任何元素就返回true，否则返回false
 clear()：移除栈里的所有元素
 size()：返回栈里的元素个数

 a1 a2 a3 a4 a5 进栈
 先进后出   a5 a4 a3 a2 a1
 */
export default class ArrayStack {
  constructor () {
    this.items = []
  }

  push(ele) {
    this.items.push(ele)
    return this
  }

  pop () {
    return this.items.pop()
  }

  peek() {
    return this.items[this.items.length-1]
  }

  isEmpty(){
    return this.items.length === 0
  }

  size () {
    return this.items.length
  }

  print() {
    return this.items.toString()
  }
}

let stack = new ArrayStack()
stack.push('a1').push('a2').push('a3').push('a4')..push('a5')
console.log(stack.pop()) // a5

链表 - 链式栈

// https://github.com/ueumd/blog/blob/master/数据结构/栈/Stack.js

import SinglyLinkedList from '../链表/SinglyLinkedList.js'
/**
 push(element)：添加一个（或几个）新元素到栈顶
 pop()：移除栈顶的元素，同时返回被移除的元素
 peek()：返回栈顶的元素，不对栈做任何修改
 isEmpty()：如果栈里没有任何元素就返回true，否则返回false
 clear()：移除栈里的所有元素
 size()：返回栈里的元素个数

 A,B,C,D 进栈
 先进后出   D C B A
 */
export default class Stack {
  constructor(){
    this.linkedList = new SinglyLinkedList()
  }

  push (value) {
    this.linkedList.prepend(value)
    return this
  }

  pop () {
    const removeHead = this.linkedList.deleteHead()
    return removeHead ? removeHead : null
  }

  peek () {
    if (this.isEmpty()) {
      return null
    }
    return this.linkedList.head
  }

  isEmpty () {
    return !this.linkedList.head
  }

  size () {
    return this.linkedList.size()
  }

  clear () {
    this.linkedList = null
  }

  toArray () {
    return this.linkedList.toArray()
  }
}

栈的应用

待续...

队列（Queue）是只允许在一端进行插入操作，而在另一端进行删除作的线性表。同样队列在存储上也可以分为：

顺序队列
链式存储

普通队列

定义

队列是遵循 FIFO（First In First Out，先进先出）原则的一组有序的项。
队列在尾部添加新元素，并从顶部移除元素。
最新添加的元素必须排在队列的末尾。
队列只有入队 push() 和出队 pop()。

示列：

<meta charset="UTF-8">
<script>
  /**
   先进先出(FIFO First In First Out) A,B,C,D
   1 基于数据
   2 基于链表 (性能更高)


   delQueue                    enQueue
   ----------------------------------
   <-  A | B | C | D|              <-
   ---------------------------------
   front                          End
   只能表的前端进行删除失操作，表的后端进行插入操作
   */
  class Queue {
    constructor() {
      this.items = []
    }

    enQueue(ele) {
      this.items.push(ele)
    }

    // 移除队列的第一个元素，并返回被移除的元素
    deQueue() {
      return this.items.shift()
    }

    front() {
      return this.items[0]
    }

    isEmpty() {
      return this.items.length === 0
    }

    clear() {
      this.items = []
    }

    size() {
      return this.items.length
    }

    print() {
      return this.items.toString()
    }
  }

  let s = new Queue()
  s.enQueue('A')
  s.enQueue('B')
  console.log(s.print())


    // 击鼓传花
  var users = ['小王', '小明', '小红', '小夏', '小小']
  var num = 2

  function hotPotatoGame(users, num) {
    var q = new Queue()
    /*
     * 依次加入队列
     * <-                               <-
     * '小王', '小明', '小红', '小夏', '小小'
     */
    for (let i = 0; i < users.length; i++) {
      q.enQueue(users[i])
    }

    while (q.size() > 1) {

      // 不符条件的先从队头删除，再从队尾插入
      for (let i = 0; i < num - 1; i++) {
        q.enQueue(q.deQueue())
      }

      // 符合条件的直接删除
      console.log(q.deQueue() + ' 淘汰~')

    }

    console.log(q)
    // 返回最终剩下的那个人
    return q.front()
  }

  console.log(hotPotatoGame(users, num) + '留下~')
</script>

优先队列

定义

优先队列中元素的添加和移除是依赖优先级的。

应用

一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客。
再比如：火车，老年人、孕妇和带小孩的乘客是享有优先检票权的。

优先队列分为两类

最小优先队列
最大优先队列

最小优先队列

是把优先级的值最小的元素被放置到队列的最前面（代表最高的优先级）。比如：有四个元素："John", "Jack", "Camila", "Tom"，他们的优先级值分别为 4，3，2，1。那么最小优先队列排序应该为："Tom"，"Camila"，"Jack"，"John"。

最大优先队列

与最小优先队列正好相反，把优先级值最大的元素放置在队列的最前面。以上面的为例，最大优先队列排序应该为："John", "Jack", "Camila", "Tom"。


// 优先级限队列根据priority 来确定插入的位置

/**
 * @param element  元素
 * @param priority 优先级
 */
class QueueElement {
  constructor(element, priority) {
    this.element = element
    this.priority = priority
  }
}

const items = new WeakMap()

export default class PriorityQueue {
  constructor() {
    items.set(this, [])
  }

  /**
   * 主要修改，在新元素添加的时候，放到优先级相同位置，
   * 但是先添加到队列的元素，我们同样遵从先进先出的原则。
   * @param element
   * @param priority
   */
  enqueue(element, priority) {
    let added = false

    let queueElement = new QueueElement(element, priority)
    let q = items.get(this)


    for (let i = 0; i < q.length; i++) {

      /**
       *   注意，只需要将这里改为大于号就可以了 最大优先对列
       *   queueElement.priority > q[i].priority
       */
      if (queueElement.priority < q[i].priority) {
        q.splice(i, 0, queueElement);
        added = true
        break
      }
    }

    // 优先级很低
    if (!added) {
      q.push(queueElement);
    }

    items.set(this, q)
  };

  dequeue() {
    let q = items.get(this)
    let r = q.shift()
    items.set(this, q)
    return r
  }

  front() {
    let q = items.get(this);
    return q[0]
  }

  isEmpty() {
    return items.get(this).length === 0
  }

  size() {
    let q = items.get(this)
    return q.length
  }

  clear() {
    items.set(this, [])
  }

  print() {
    let q = items.get(this)
    for (let i = 0; i < q.length; i++) {
      console.log(`${q[i].element}  - ${q[i].priority}`)
    }
  }
}

列队顺序存储的不足

我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。

所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为0(1)。

与栈不同的是队列的元素出列是在队头，即下标为 0 的位置。也就意味着，队列中的所有元素都得向前移动，足以保证队列的队头，也就是下标为 0 的位置不为空。此时时间复杂度为O(n)。

可有时想想，为什么出队列时一定要全部移动呢？如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大增加。也就是说，队头不需要一定在下标为0的位置，比如也可以是a[1]，下标为1的位置等，如下图：

为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。

假设是长度为5的数组，初始状态，空队列如所示，front与 rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4, front指针依然指向下标为0位置，而rear指针指向下标为4的位置。

出队a1、a2，则front指针指向下标为2的位置，rear不变，如下图所示，再入队a5，此时front指针不变，rear指针移动到数组之外。嗯？数组之外，那将是哪里？

问题还不止于此。假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“假溢出”。

总结：入队时：将新元素插入rear所指的位置，然后将rear加1。出队时：删去front所指的元素，然后将front加1并返回被删元素。

注意： (1)当头尾指针相等时，队列为空。 (2)在非空队列里，队头指针始终指向队头元素，队尾指针始终指向队尾元素的下一位置。 (3)长度：rear-front

循环队列

前面已指出了顺序队列的缺点，这里我们引出循环队列的概念。

将顺序队列臆造为一个环状的空间，即把存储队列元素的表从逻辑上看成一个环,称为循环队列。当队首指针 Q.ftont = MaxSiZe-1后，再前进一个位置就自动到0，这可以利用除法取余运算(%)来实现。

初始时：Q.front = Q.rea r= 0 队首指针进 1：Q.front=(Q.front+1)%MaxSize 队尾指针进 1：Q.rear=(Q.rear+1)%MaxSize 队列长度：(Q.rear+MaxSize-Q.front)%MaxSize

出队入队时：指针都按顺时针方向进1 (如图3-7所示)。

那么，循环队列队空和队满的判断条件是什么呢？显然，队空的条件是Q.front==Q.rear。如果入队元素的速度快于出队元素的速度，队尾指针很快就赶上了队首指针，如图3-7(d1)，此时可以看出队满时也有Q.front==Q.rear。

循环队列出入队示意图如图3-7所示。

为了区分队空还是队满的情况，有三种处理方式：

1) 牺牲一个单元来区分队空和队满，入队时少用一个队列单元，这是一种较为普遍的做法，约定以“队头指针在队尾指针的下一位置作为队满的标志”，如图3-7(d2)所示。

队满条件为：(Q.rearfl)%MaxSize==Q.front。队空条件仍为：Q.front==Q.rear。队列中元素的个数：(Q.rear-Q.front+MaxSize)%MaxSize

2) 类型中增设表示元素个数的数据成员。这样，则队空的条件为Q.Size==0，队满的条件为 Q.size==MaxSize。这两种情况都有 Q.front=Q.rear。

3) 类型中增设tag数据成员，以区分是队满还是队空。tag等于0的情况下，若因删除导致Q.front==Q.rear则为队空；tag等于1的情况下，若因插入导致Q.ftont==Q.rear则为队满。

#define MaxSize 50  //定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];  //存放队歹I]元素
    int front, rear;  //队头指针和队尾指针
}SqQueue;

// 初始化
void InitQueue(&Q){
    Q.rear=Q.front=0;  //初始化队首、队尾指针
}

bool isEmpty(Q) {
    if(Q.rear == Q.front) return true;  //队空条件
    else return false;
}

// 入队
bool EnQueue(SqQueue &Q, ElemType x){
    if((Q.rear+1)%MaxSize == Q.front) return false; //队满
    Q.data[Q.rear]=x;
    Q.rear= (Q.rear+1)%MaxSize; //队尾指针加 1 取模
    return true;
}

// 出队
bool DeQueue(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front) return false;  //队空，报错
    x=Q.data[Q.front];
    Q.front= (Q.front+1)%MaxSize;  //队头指针加 1 取模
    return true;
}

现实例子就是击鼓传花(Hot Potato)，在游戏中，孩子们围着圆圈，把花尽快地传递给旁边的人。某一时刻传花停止，这个时候花在谁手里，谁就退出圆圈结束游戏。重复这个过程，直到只剩一个孩子(胜利)。

Javascript版循环队列

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script>
  /*
  CircularQueue(k):   构造器，设置队列长度为 k 。
  Front:              从队首获取元素。如果队列为空，返回 -1 。
  Rear:               获取队尾元素。如果队列为空，返回 -1 。
  enQueue(value):     向循环队列插入一个元素。如果成功插入则返回真。
  deQueue():          从循环队列中删除一个元素。如果成功删除则返回删除的元素。
  isEmpty():          检查循环队列是否为空。
  isFull():           检查循环队列是否已满。

  */

  class Node {
    constructor(value) {
      this.value = value
      this.next = null
    }
  }

  class CircularQueue {
    constructor(k) {
      this.capacity = k  // 链表的容量
      this.head = null  // 头部指针
      this.tail = null   // 尾部指针
      this.count = 0     // 元素个数
    }

    /**
     * 从队首获取元素，如果队列为空，返回 -1
     */
    Front() {
      if (this.isEmpty()) return -1
      return this.head.value
    }

    /**
     *  获取队尾元素。如果队列为空，返回 -1
     */
    Rear() {
      if (this.isEmpty()) return -1
      return this.tail.value
    }

    enQueue(val) {
      if (this.isFull()) return false

      let node = new Node(val)

      if (this.isEmpty()) {
        // 为空 头尾都指向node
        this.head = this.tail = node
      } else {
        // 更新尾指针
        this.tail.next = node
        this.tail = node
      }

      // 元素个数加1
      this.count++
      return true
    }

    /**
     * 删除头部指针 先进先出
     * @returns {boolean}
     */
    deQueue() {
      if (this.isEmpty()) return false
      let temp = this.head
      this.head = this.head.next
      // 元素个数减1
      this.count--
      return temp
      // return true
    }

    isEmpty() {
      return this.count === 0
    }

    isFull() {
      return this.count === this.capacity
    }
  }

    // 击鼓传花
  function hotPotato(nameList, num) {
    let queue = new CircularQueue(nameList.length)

    for (let i = 0; i < nameList.length; i++) {
      queue.enQueue(nameList[i])
    }

    let eliminated = ''

    while (queue.count>1) {

      for (let i = 0; i < num; i++) {
        queue.enQueue(queue.deQueue().value) //从队列开头移除一项，再将其添加到队列末位。
      }

      eliminated = queue.deQueue()    // 传递次数达到指定的数字，那个人淘汰

      console.log(eliminated.value + '被淘汰')
    }

    return queue.Front()
  }

  let names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
  let winner = hotPotato(names, 7)

  console.log(winner + "胜利者")
  //Camila被淘汰
  //Jack被淘汰
  //Carl被淘汰
  //Ingrid被淘汰

  //John胜利者

</script>
</body>
</html>

双端队列

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

在计算机科学中，双端队列的一个常见应用是存储一系列的撤销操作。双端队列同时遵守了先进先出和后进先出原则，可以说它是把队列和栈相结合的一种数据结构。如果链表实现即是头插法和尾插法。

全部代码在 github 数据结构

《大话数据结构》
《JavaScript 数据结构与算法之美》
数据结构-栈
javascript 队列(queue)算法与说明