在JavaScriptTypeScript中使用栈——几种栈的使用方法

这里主要介绍几种栈本身的使用方法，不包括一些作为容器其他用法，比如进行DFS，用来保存中间结点等等；也不包括递归栈，虽然有时候也可以把使用递归方法看做使用了栈，但抠字眼没什么意思。

此外，本文不会详细介绍语法，请读者担待。

用数组实现栈

这个并不属于正文，而且是很简单的内容，但是我觉得还是有必要在这里稍微提一下；看似很简单的东西也会有坑在里面。比如三合一问题，用一个数组实现三个有容量上限的栈：

class TripleInOne { private data: number[] = []; private left: number[] = []; private right: number[] = []; private ptr: number[] = []; constructor(stackSize: number) { this.left.push(0, stackSize, stackSize * 2); this.right.push(stackSize, stackSize * 2, stackSize * 3); this.ptr.push(...this.left); } push(stackNum: number, value: number): void { if (this.ptr[stackNum] < this.right[stackNum]) { this.data[this.ptr[stackNum]++] = value; } } pop(stackNum: number): number { return this.isEmpty(stackNum) ? -1 : this.data[--this.ptr[stackNum]]; } peek(stackNum: number): number { return this.isEmpty(stackNum) ? -1 : this.data[this.ptr[stackNum] - 1]; } isEmpty(stackNum: number): boolean { return this.ptr[stackNum] <= this.left[stackNum]; } }

解决这个问题并不困难，主要麻烦的是指针的移动（尤其是在C++这种语言不能使用STL的时候）。比如这种实现，每次添加后指针都会向后移动，所以在删除时要先向前移动，再进行删除，同时peek操作也要对应- 1，才能获取到正确的栈顶值。

最值栈

比较著名的就是最小栈了，能够在O(1)的时间内获得栈内的最小值。这里给出一种可能的实现。

class MinStack { private data: number[] = []; private min = [Number.MAX_VALUE]; push(x: number): void { this.data.push(x); this.min.push(Math.min(this.getMin(), x)); } pop(): void { this.data.pop(); this.min.pop(); } top(): number { return this.data[this.data.length - 1]; } getMin(): number { return this.min[this.min.length - 1]; } }

最大栈同理，换成max就是了。

至于你问我最小栈的应用是什么，很抱歉我也搞不清楚……但是这个题频繁出现，在几本经典的面试书籍上都出现过，所以还是有必要搞清楚的。

单调栈

这个也是一个很有用的数据结构，可以用于寻找一些具有单调性质的内容。比如：

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

这个其实就适合用单调栈处理，找到数组中现在已经有序的部分，然后一减就是乱序的部分。

以递增栈为例，这个栈内部的元素是单调递增的。为了确保栈内元素是递增的，每次遇到比栈顶元素小的新元素，就应该不断出栈直到新元素不再小于栈顶元素；这个道理还是很明显的。

const length = nums.length; const stack = []; for (let i = 0; i < length; ++i) { while (stack.length && stack[stack.length - 1] > nums[i]) stack.pop()!; stack.push(i); }

同时，单调栈有两种形式。还是以递增栈为例，递增栈有两种：

“物理”递增：栈内存储的是值，值本身递增；“逻辑”递增：栈内存储的是下标，下标对应的值递增。

存储下标可以用于解决一些距离、长度的问题。比如之前提到的那个问题，存下标就比较合适。这里也举个例子：

const length = nums.length; const stack = []; for (let i = 0; i < length; ++i) { while (stack.length && nums[stack[stack.length - 1]] > nums[i]) stack.pop()!; stack.push(i); }

最大频率栈

这个其实是一个很特殊的栈：入栈和普通栈一样，但退栈时是移除栈中出现最频繁的元素；如果最频繁的元素不止一个，则移除并返回最接近栈顶的元素。

不知道你们有没有想到OS的多级反馈队列调度算法，我觉得这个和那个几乎是一样的思路。引用一下百度百科里的图： 多级反馈队列调度算法的具体内容不仔细说了，大概就是每次从优先级最高的队列里选择进程执行，如果没有执行完就降低优先级，放到下一级队列里。

在这里，频率就相当于是优先级，出现几次就在第几层，而且频率越高优先级越高。所以，我们只需要记录一下当前“待处理进程”的优先级，然后维护这么一个多级的栈即可：

class FreqStack { private freqs = new Map<number, number>(); private stacks = new Map<number, number[]>(); private maxFreq = 0; push(x: number): void { const beforeFreq = this.freqs.get(x), currentFreq = beforeFreq ? beforeFreq + 1 : 1; // update freq this.freqs.set(x, currentFreq); // push to stack const stack = this.stacks.get(currentFreq); if (stack) stack.push(x); else this.stacks.set(currentFreq, [x]); // update max freq this.maxFreq = Math.max(this.maxFreq, currentFreq); } pop(): number { const res = this.stacks.get(this.maxFreq)!.pop()!; this.freqs.set(res, this.freqs.get(res)! - 1); if (!this.stacks.get(this.maxFreq)!.length) --this.maxFreq; return res; } }

这个代码还是用cpp写起来舒服。js甚至不如Java，Java 8之后好歹还有个给map初始值的方法，js只能硬写。为了能清晰地说明，我觉得还是放个cpp的版本比较好：

class FreqStack { private: unordered_map<int, int> freq; unordered_map<int, stack<int>> stacks; int maxfreq = 0; public: void push(int x) { ++freq[x]; maxfreq = max(maxfreq, freq[x]); stacks[freq[x]].push(x); } int pop() { int x = stacks[maxfreq].top(); stacks[maxfreq].pop(); --freq[x]; if (stacks[maxfreq].empty()) --maxfreq; return x; } };

用栈实现队列

队列是先进先出（FIFO）的数据结构。

当然了，对于js来说，这个问题毫无意义，因为js的数组本身是个双端队列，根本无所谓。

class MyQueue { private data: number[] = []; push(x: number): void { this.data.push(x); } pop(): number { return this.data.shift()!; } peek(): number { return this.data[0]; } empty(): boolean { return this.data.length === 0; } }

单栈

用单栈实现队列，其实没什么好说的，就是一个模拟的过程，无非是添加O(1)删除O(n)，添加的时候放到栈顶，删除的时候把栈底元素退出去，然后再把其他元素压回来；或者添加O(n)删除O(1)，添加的时候放到栈底，删除的时候把栈顶元素退栈。这两种写法取决于添加操作多，还是删除操作多。这里提供一种添加O(n)删除O(1)的写法：

class MyQueue { private stack: number[] = []; push(x: number): void { const tmp: number[] = []; while (this.stack.length) { tmp.push(this.stack.pop()!); } this.stack.push(x); while (tmp.length) { this.stack.push(tmp.pop()!); } } pop(): number { return this.stack.pop()!; } peek(): number { return this.stack[this.stack.length - 1]; } empty(): boolean { return this.stack.length === 0; } }

双栈

如果要用栈实现队列，从我个人角度，我觉得单栈比双栈的思路要自然。不过，双栈的写法看起来确实更清晰一些。

思路比较简单，准备两个栈，一个用于添加（appStack），一个用于删除（delStack）。添加新元素的时候直接向appStack中添加，删除的时候从delStack中删除，如果delStack中没有元素，就把appStack中现有的元素添加到delStack中，然后再删除，就这么简单。代码如下：

class CQueue { private appStack: number[] = []; private delStack: number[] = []; appendTail(value: number): void { this.appStack.push(value); } deleteHead(): number { if (!this.delStack.length) { while (this.delStack.length) { this.delStack.push(this.delStack.pop()!); } } return this.delStack.length ? this.delStack.pop()! : -1; } }

里面唯一可能的问题就是，从appStack添加到delStack这一步，是怎么保证有序的。我们设想一下压栈的过程，appStack中最先入栈的元素位于栈底，我们再按顺序把appStack中的元素压入delStack，此时相当于掉了个个，最先入栈的元素重新被压到栈顶了，会在删除时最先出栈，就实现了先进先出。