# 堆栈

是一种具有操作约束的线性表。只能在一端进行插入，删除操作

特性

后来先服务

后进先出(LIFO)

# 操作集

创建空的堆栈
插入数据 push
删除数据 pop
判断堆栈是否为空
判断堆栈是否满了

# 通过数组的方式实现堆栈

TIP

JS 数据自动 push 和 pop 方法可以满足基本使用

# 用链表实现堆栈

# 基本结构

// 链表节点数据结构
class LinkNode {
  constructor() {
    // 存储数据
    this.data = null;
    // 指向下一个节点
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.head = null;
  }

  // 判断是否为空
  isEmpty() {
    if (!this.head) return true;
    else return false;
  }
  // 加入新节点
  push(node) {
    if (!this.head) {
      this.head = node;
    }
    node.next = this.head;
    this.head = node;
  }
  // 推出头节点
  pop() {
    if (!this.head) {
      return;
    }
    const node = this.head;
    this.head = node.next;
    node.next = null;
    return node;
  }
}

# 队列

队列跟堆栈一样具有约束的线性表，队列只能在一端插入，在另一端删除。

特性

先来先服务

先进先出(FIFO)

# 操作集

创建队列
加入元素
删除元素
判断是否为空
判断是否满了

# 数组方式实现

具有两个标记，一个标记头元素 head，用于基础删除元素后下标位置。另一个标记结尾元素 last，用于记录最后加入元素的下标位置。

注意

head 等于 last 时无法判断队列是空的还是满的。

解决方法：

队列添加永远保持长度-1 个，此时只有队列为空时，head 等于 last，否则不相等
通过额外一个 length 记录队列长度，可以解决该问题
通过额外一个 tag 记录队列最后一次操作类型，如果是插入则表示队列满了。否则队列未满

# 链表实现方式

front 记录表头， rear 记录最后添加的节点。

出队列操作直接返回 front，将 front 指向下一个节点。

入队列操作，直接将 rear.next 插入新节点, rear 指向新的节点。

/**
 * 队列实现
 */


class LinkNode {
  constructor(data = null) {
    this.data = data;
    this.next = null;
  }
}

export class Queue {
  constructor() {
    this.__front = null;
    this.__rear = null;
  }

  // 出队列
  delete() {
    if (this.__front === null) {
      return;
    }
    const frontCell = this.__front;
    // front 等于 rear 表示只剩下一个节点，将它们清空。
    if (this.__front === this.__rear) {
      this.__front = this.__rear = null;
    } else {
      this.__front = frontCell.next;
    }
    return frontCell;
  }

  // 入队列
  append(node) {
    // front为空时候需要赋值给新节点
    if (this.__front === null) this.__front = node;
    if (this.__rear === null) {
      this.__rear = node;
    } else {
      this.__rear.next = node;
      this.__rear = node;
    }
  }
}