栈和队列

栈(Stack)

栈是一种特殊的列表,限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据。例如饭店里用来放盘子的,就是一种栈的结构。

由于栈具有后入先出的特点,因此只能访问在栈顶的元素。栈的操作主要有两种:入栈和出栈。上面的图演示了入栈和出栈的过程。

栈的实现

实现一个栈,可以用数组来实现,也可以用链表来实现。下面将用数组来实现。

class Stack {
constructor() {
this.data = [];
this.top = 0; // 记录栈顶位置,如果有元素进栈,该变量值随之变化
}
push(item) {
this.data[this.top++] = item;
}
pop() {
// 栈为空,则直接返回null
if (this.top === 0) {
return null;
}
// 返回下标为top - 1 的数组元素,并将栈中元素个数减一
return this.data[--this.top];
}
clear() {
this.top = 0;
}
get length() {
return this.top;
}
}

那么栈的空间、时间复杂度又分别是多少?其实很简单,我们发现储存数据只需要长度为 nn 的数组就够了,在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是 O(1)O(1)

注意 ⚠️:算法的复杂度是指程序指除了原本的数据存储空间外,算法运行还需要额外的存储空间。

队列(Queue)

队列是一种先进先出的数据结构,这点和栈不一样。队列这个概念很好理解,可以想象成在食堂排队买饭吃,先到先得,后面来的排队,不允许插队。

队列的主要操作有两种:向队列中插入或删除新的元素。插入操作可以比喻成吃饭,删除操作可以比喻成(XX)。

和栈一样,队列可以用数组来实现,也可以用链表来实现。下面将用数组来实现一个队列。

class Queue {
constructor() {
this.data = [];
// head表示头部下标,tail表示尾部下标
this.head = 0;
this.tail = 0;
}
// 入队
enqueue(item) {
this.data[this.tail++] = item;
}
dequeue() {
// 如果head == tail 表示队列为空
if (this.head === this.tail) {
return null;
}
return this.data[++this.head];
}
get length() {
return this.tail - this.head;
}
}

对于栈来说,一个指针就够了,但是队列需要两个指针,分别用于指向头部和尾部。

在栈和队列相关的题目之外,挑选了一些额外的题目。不知道看过前面章节的你掌握了多少?这部分的题目可以帮助大家测试以下算法掌握得怎么样了。建议先不要急着看答案,越能自主解决问题,自身的能力才提升得更快。

本章节分为 4 个部分:

  • Part 1

    • 汉明距离

    • 位1的个数

    • 缺失的数字

  • Part 2

    • 有效的括号

    • 帕斯卡三角形

    • 颠倒二进制位

  • Part 3

    • 两整数之和

    • 数据流的中位数

    • 逆波兰表达式

  • Part 4

    • Task Sheduler

    • 有序矩阵中第K小的元素

    • 多数元素