一次弄懂栈、双栈、队列、双端队列（leetcode实战）

devhaozi · May 15, 2024, 3:50am

theme: juejin highlight: a11y-dark

前言

在 JavaScript 编程中，数据结构是构建高效和可靠程序的基础。栈、双栈、队列和双端队列是常见的数据结构，它们各自具有独特的特点和应用场景。

在js中，栈其实就是一种特殊的数组，队列也是一种特殊的数组，只是应用场景不同，那么有同学要问了，既然都是数组，那数组里的方法不都可以用吗？！没错，确实可以用，但是我们心里要把它默认当成是一个栈或者队列，遵循栈或者队列的原则来使用，不然他不就不是栈、队列了吗？

正文

栈和双栈

在js中，我们可以通过数组来模拟栈，栈就是一种特殊的数组。栈是一种遵循后进先出原则的线性数据结构。就像一摞盘子，只能在顶部添加或移除元素。在 JavaScript 中，可以使用数组来实现栈的基本操作，如入栈（push）和出栈（pop）。

双栈是将一个数组分为两个部分，分别作为两个栈来使用。这种结构可以在某些情况下提高空间利用率和操作效率。

如果这是一个数组，我们都知道，js中，数组可以push尾部添加数据，pop尾部删除数据，shift头部删除数据，unshift头部增加数据，甚至可以通过splice任意位置增加或者删除元素。那么栈就应该是这样的:

基于此，我们来看看力扣实战（力扣20）

给定一个只包括 `'('`，`')'`，`'{'`，`'}'`，`'['`，`']'` 的字符串 `s` ，判断字符串是否有效。
有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号

示例

示例 1： 
输入：s = "()" 
输出：true
示例 2：

输入：s = “(){}”

输出：true
示例 3：

输入：s = “(]”

输出：false

分析：

初步想法其实就是要匹配括号，括号一共有三种，中括号、小括号、大括号。
既然要匹配那么这个字符串可以首先判断它应该是偶数，否则匹配不了。
这种匹配，成双成对出现的题目，使用栈这种数据结构来实现非常方便，因为栈的特殊应用场景，出栈，入栈。可以想象一下，在这个题目里，首先我们需要创建一个栈（数组），然后我们可以创建一个对象，属性分别为三个左括号，值分别为对应的三个右括号，作用是，当我们是某个左括号时，我们希望能拿到对应的右括号做匹配。
我们首先遍历这个字符串，当遍历字符串为左括号时，我们就把这个左括号对应的右括号给入栈，当遍历到右括号时，我们就出栈pop，通过pop不仅可以出栈还可以返回这个刚刚出栈的栈顶元素，然后我们做判断，这个top栈顶元素与现在遍历到的右括号是不是一对，如果不是一对，那肯定不匹配直接返回false。
最后遍历结束如果都没返回false，那说明匹配成功返回true
但是到这里就结束了吗？

思考：

是否存在一种情况，遍历到后面，结果后面全部都是左括号，既然是左括号，那不就直接入栈吗？后面没有右括号他就不会出栈，也不会做匹配判断，最后就返回true了，因此我们需要在最后判断一下栈是否为空，因为匹配成功一对，都会出栈，这样最终栈是空的，并且开始我们说了判断这个字符串是否为偶数，如果我们最终判断了这个栈是否为空的话，那么前期偶数判断也就没有必要了。

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function (s) {
    const stack = [];
    const leftToRight = {
        '{':'}',
        '[':']',
        '(':')'
    };
    if(s.length%2 !== 0){
        return false;
    }
    for(let i =0;i<s.length;i++){ if(s[i]="==" '('="" ||="" s[i]="==" '{'="" '['){="" stack.push(lefttoright[s[i]]);="" }else{="" let="" top="stack.pop()" !="=" top){="" return="" false;="" }="" !stack.length;="" };="" <="" code>


给大家一个例子，大家可以过一遍流程。例如给你一个s='{[()]}'

首先遍历s，首先是左边大括号，那么大的右括号入栈。
接着是左边中括号，那么右边中括号入栈。
依次，右边小括号入栈。
然后发现是右边小括号，那么做出栈操作pop，并判断我们通过pop操作拿到的这个top元素与遍历的这个右边小括号是否匹配，不匹配就false，否则继续。
继续发现是右边中括号，继续pop，拿到top与目前的遍历到的元素对比，发现是一样的
继续往下走就是右边大括号，还是pop最终都发现是一样的pop操作后，栈也是空的了，跳出循环发现stack.length=0，如果有长度那么就返回true了，因此我们这里要对stack.length取反。

队列与双端队列
数组的图在前面我们已经画过了，这里我们思考一下队列是一种什么样的数据结构，有什么样的应用场景。其实生活中队列很常见，我们排队买饭这就是一种队列，先来的先走，后来的后走。
image.png429×666 8.53 KB

那么什么是双端队列呢？
其实就是字面意思，有两头的队列。双端队列是一种特殊的队列，它支持从两端进行元素的插入和删除操作。与普通队列不同，双端队列可以在队列的头部和尾部插入元素，也可以从头部和尾部删除元素。这种灵活性使得双端队列在一些特定的场景中非常有用
image.png481×696 13.9 KB

因此大家想象一下，队列也是一种特殊的数组，那么在js中应该怎么表示？

创建队列：

let queue = []


入对：

queue.push(element)


出队（另一端）：

queue.shift()


获取队头元素：

let element = queue.shift()//shift方法会返回出队元素的值


获取头部元素：

let firstElement = queue[0];

注意：在队列中，只能获取队首元素，不能获取其他元素。
实战：力扣232
提示：
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：

MyQueue myQueue = new MyQueue();

myQueue.push(1); // queue is: [1]

myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)

myQueue.peek(); // return 1

myQueue.pop(); // return 1, queue is [2]

myQueue.empty(); // return false

思考：
想用栈来实现队列，队列是两头开的，而栈只开一头，因此我们可以用双栈实现这个效果
image.png959×612 12.7 KB


想象一下，当我们向第一个栈入栈1234，是队列的话出来也应该是1234
首先给stack1push1234,然后stack1.pop掉就能拿到top元素，比如这里top就是4，把4给stack2入栈，stack2以此类推就是4321，然后再出栈，我们就能够拿到期望的1234
image.png1106×591 17.1 KB


var MyQueue = function () {
    this.stack1 = [];
    this.stack2 = [];
};
/**

@param {number} x
@return {void}

*/

MyQueue.prototype.push = function (x) {

this.stack1.push(x);

};

/**


@return {number}

*/

MyQueue.prototype.pop = function () {

if (!this.stack2.length) {

while (this.stack1.length) {

this.stack2.push(this.stack1.pop());

}

}
return this.stack2.pop();


};
/**

@return {number}

*/

MyQueue.prototype.peek = function () {

if (!this.stack2.length) {

while (this.stack1.length) {

this.stack2.push(this.stack1.pop());

}

}

const stack2Len = this.stack2.length;

return this.stack2[stack2Len - 1];

};

/**

@return {boolean}

*/

MyQueue.prototype.empty = function () {

return !this.stack1.length && !this.stack2.length;

};

/**

Your MyQueue object will be instantiated and called as such:
var obj = new MyQueue()
obj.push(x)
var param_2 = obj.pop()
var param_3 = obj.peek()
var param_4 = obj.empty()

*/



这里只有一个注意点：
在我们做pop操作的时候，我们栈1入栈1234，出栈4321分别入栈给栈2就变成12...如果我没有全部入栈，这个时候栈1是43，栈2是12，然后栈1又来一个5，那么栈1就是435，栈2就是12，我们要拿到队头元素，那不应该是5吗，这个时候怎么会是2呢？因此我们要实现做判断，判断栈1是否为空，只要不为空，我们就把栈1全部出栈给栈2。
双端队列实战，力扣239滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k **的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
**示例 1：**
输入： nums = [1,3,-1,-3,5,3,6,7], k = 3
输出： [3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7      5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
示例 2：

输入：nums = [1], k = 1

输出： [1]


题解1：双指针
滑动窗口，顾名思义，就是一个会滑动的窗口，比如窗口大小是3，就是在数组中，找到在这个窗口内的最大值。

a 和 b 分别表示滑动窗口的起始位置和结束位置。
通过一个循环，当 b 小于数组长度时，进行以下操作：


初始化最大值为负无穷大（最小值）。
遍历窗口内的元素，找到最大值并更新。
将最大值添加到结果数组 arr 中。
移动窗口，将 a 和 b 分别向后移动一位。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
    var a = 0;
    var b = k - 1;
    var arr = []
    while (b < nums.length) {
        var max = -Infinity
        for (var i = a; i <= b; i++) {
            if (max < nums[i])
                max = nums[i];
        }
        arr.push(max)
        a++
        b++
    }
    return arr;
};

可以看到，这是一道困难题，双指针的方法虽然很简单很容易理解，但是最终也是没能通过所有的案例，力扣在这里也是为难了一下我们
image.png860×755 72.5 KB
因此我们需要在时间上做一下优化。
队列来了
var nums = [1,3,-1,-3,5,3,6,7], k = 3;
var maxSlidingWindow = function(nums, k) {

const len = nums.length;

const res = ;

const queue = ;//维护一个递减队列

for (let i = 0; i < len; i++) {

//打破递减趋势

while (queue.length && nums[queue[queue.length-1]] <= nums[i]){

queue.pop();

}
    queue.push(i);

    //需要有值流出窗口
    while (queue.length &amp;&amp; queue[0] &lt;= i-k){
    queue.shift();
    }

    //该记录最大值
    if (i &gt;= k-1){
    res.push(nums[queue[0]]);
    }
}
return res;

};



const len = nums.length; 获取数组 nums 的长度。
const res = []; 用于存储滑动窗口的最大值结果。
const queue = []; 是一个递减队列，用于维护当前窗口内的最大值及其位置。 在循环中：


当新元素大于队列中某些元素时，将这些较小的元素出队，以保持队列的递减性。
将新元素入队。
检查队列中超出窗口范围的元素并出队。
当窗口达到合适大小（i >= k-1）时，将队列头部的元素（即当前窗口的最大值）添加到结果数组 res 中。
这种方法巧妙地利用了递减队列来高效地找到滑动窗口中的最大值。
这里我就不做过多分析了，学到这里，你能不能帮我分析一下，你通过这些数据结构学到了什么呢

小结

栈（Stack）： - 特点：后进先出（LIFO），数据操作在栈顶进行。


实现：可以用单链表实现，操作时间复杂度为 O(1)。
应用场景：函数调用、表达式求值、括号匹配等，需要回溯操作的场景。


队列（Queue）：


特点：先进先出（FIFO），数据操作在队尾和队头进行。
实现：可以用双链表实现，操作时间复杂度为 O(1)。
应用场景：按顺序处理数据，如线程并发、广度优先搜索等。


双栈（Double Stack）：


特点：两个栈的组合，可以同时进行两个栈的操作。
应用场景：特定问题需要同时维护两个栈的情况。


双端队列（Deque，Double-End Queue）：


特点：两端都可进可出，操作时间复杂度为 O(1)。
实现：可以用双链表实现。
应用场景：滑动窗口问题、任务调度等。

这些数据结构在 LeetCode 中有广泛应用，具体问题可能需要结合具体题目和解题思路来选择合适的数据结构。同时，了解它们的特点和操作对于解决相关问题至关重要。

这是一个从 https://juejin.cn/post/7368770335224807459 下的原始话题分离的讨论话题

Topic	Replies	Views
先进先出的结构-队列 JS/TS	11	May 16, 2024
Js数据结构之字符串 JS/TS	12	May 16, 2024
你真的了解js类型吗 JS/TS	12	May 14, 2024
深入了解JS作用域链，浏览器中JS的执行机制 JS/TS	11	May 14, 2024
前端应该了解的数据结构 \| 线性表 JS/TS	13	May 15, 2024

一次弄懂栈、双栈、队列、双端队列（leetcode实战）

theme: juejin highlight: a11y-dark

前言

正文

栈和双栈

队列与双端队列

小结

Related Topics