1️⃣ 栈

2️⃣ 什么是栈，栈存储结构详解

栈是用来存储逻辑关系为 “一对一” 数据的线性存储结构，如图所示。

  1.   1. 栈只能从表的一端存取数据，另一端是封闭的，如图 1 所示；
  2.   1. 在栈中，无论是存数据还是取数据，都必须遵循 "先进后出" 的原则，即最先进栈的元素最后出栈。拿图的栈来说，从图中数据的存储状态可判断出，元素 1 是最先进的栈。因此，当需要从栈中取出元素 1 时，根据 "先进后出" 的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。

因此，我们可以给栈下一个定义，即栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构。
image.png
通常，栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素，拿图 2 来说，栈顶元素为元素 4；同理，栈底元素指的是位于栈最底部的元素，图 2 中的栈底元素为元素 1。
image.png

2️⃣ 进栈和出栈

基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：
向栈中添加元素，此过程被称为”进栈”（入栈或压栈）；
从栈中提取出指定元素，此过程被称为”出栈”（或弹栈）；

2️⃣ 栈的具体实现

栈是一种 “特殊” 的线性存储结构，因此栈的具体实现有以下两种方式：

  1. 顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
  1. 链栈：采用链式存储结构实现栈结构；

两种实现方式的区别，仅限于数据元素在实际物理空间上存放的相对位置，顺序栈底层采用的是数组，链栈底层采用的是链表。

2️⃣ JS代码模拟实现栈

function Stack() {
  this.arr = [];
  this.push = function (value) {
    this.arr.push(value)
  }
  this.pop = function () {
    return this.arr.pop()
  }
}
var stack = new Stack();
// 压栈
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.arr); // [ 1, 2, 3 ]
// 出栈
stack.pop();
console.log(stack.arr); // [ 1, 2 ]

1️⃣ 队列

2️⃣ 什么是队列（队列存储结构）

队列，和栈一样，也是一种对数据的”存”和”取”有严格要求的线性存储结构。
与栈结构不同的是，队列的两端都”开口”，要求数据只能从一端进，从另一端出，如图 1 所示：
通常，称进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。
image.png
不仅如此，队列中数据的进出要遵循 “先进先出” 的原则，即最先进队列的数据元素，同样要最先出队列。拿图 1 中的队列来说，从数据在队列中的存储状态可以分析出，元素 1 最先进队，其次是元素 2，最后是元素 3。此时如果将元素 3 出队，根据队列 “先进先出” 的特点，元素 1 要先出队列，元素 2 再出队列，最后才轮到元素 3 出队列。
栈和队列不要混淆，栈结构是一端封口，特点是”先进后出”；而队列的两端全是开口，特点是”先进先出”。
因此，数据从表的一端进，从另一端出，且遵循 “先进先出” 原则的线性存储结构就是队列。

2️⃣ 队列存储结构的实现有以下两种方式：

顺序队列：在顺序表的基础上实现的队列结构；
链队列：在链表的基础上实现的队列结构；

2️⃣ JS代码模拟实现队列

function Stack() {
  this.arr = [];
  this.push = function (value) {
    this.arr.push(value)
  }
  this.pop = function () {
    return this.arr.shift()
  }
}
var stack = new Stack();
// 入队
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.arr); // [ 1, 2, 3 ]
// 出队
stack.pop();
console.log(stack.arr); // [ 2, 3 ]