概述
这里主要介绍几种栈本身的使用方法，不包括一些作为容器其他用法，比如进行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，此时相当于掉了个个，最先入栈的元素重新被压到栈顶了，会在删除时最先出栈，就实现了先进先出。
最后
以上就是安详水杯为你收集整理的在JavaScript / TypeScript中使用栈——几种栈的使用方法的全部内容，希望文章能够帮你解决在JavaScript / TypeScript中使用栈——几种栈的使用方法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复