• 0

  • 481

前端仔的“数据结构与算法”之路——栈

云哥

关注云计算

1星期前

理解栈的概念

可以想象成一堆叠好的衣服,我们新叠好一件衣服,是放在最上层,去取衣服时为了不弄乱衣服,也是从最上层取,一件一件的放一边,直到找到我们需要的那一件。
栈是一种先进后出、后进先出的结构。

WechatIMG107.png

从操作上看,它是一种操作受限的结构,入栈只能放最上层,出栈也只能从最上层出。

对于前端来说,我们是可以用数组去模拟栈,而且功能比栈还丰富,操作不受限。看起来栈的作用并不强大。但是在遇到实际问题时,这种特点的数据结构往往更符合场景的逻辑,更顺畅的思维去解决问题。栈的存在是有意义的。
什么时候我们可以用栈来思考问题呢?

 

当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该首选“栈”这种数据结构。

栈的实现

栈的操作主要是两点

  • 入栈(在栈顶加入元素)
  • 出栈(从栈顶取出元素)

栈的实现我们可以用数组、链表去表达栈。
数组实现的方式,我们称为顺序栈。
链表实现的方式,我们称为链式栈。
代码实现上我们只需要保持入栈和出栈的规则即可。
由于我们前端语言是JavaScript,在使用数组的过程中不需要考虑动态扩容的问题,所在在用数组实现的顺序栈中,我们也不需要考虑扩容问题。

栈的应用

栈是一种基础的数据结构,概念很容易理解,实现也不复杂。我们加以应用场景,便能更深刻感受它。

函数调用栈

在操作系统中,分配的每个线程都存在于自己一块独立的内存空间中。这块内存空间被组织成栈这种结构,用来存储函数调用过程中的临时变量。每进入一个函数,就会将临时变量入栈,当函数执行结束,又会将函数的临时变量依次出栈。
简单的函数运行理解。

function main () {
  let total = 1
  let result = 0
  result = add(1, 2)
  console.log(result + total)
}
function add (x, y) {
  let sum = x + y
  return sum
}
main()

// total入栈
// result入栈
// x、y入栈
// sum入栈
// sum出栈
// 先、y出栈
// 。。。
复制代码

表达式求值

我们的数学表达式计算,计算机是如何处理的?逻辑上也用到了栈的数据结构。
我们模拟一个简单的操作,只有加减乘除。
10+20*3-50/10 // 65
计算机是如果处理这些数字和运算符,最终得出答案的呢?它使用了两个栈结构,来分别保存数字和运算符。

  • 从左到右遍历表达式
  • 遇到数字压入数字栈
  • 遇到操作符压入符号栈,如果压入的新符号比符号栈顶的优先级低或相同,则需要计算(如果低,栈顶肯定只能是乘除,如果相等,根据加减顺序从左置右,也需要先计算)
    取出数字栈两个元素、和符号栈顶元素,计算再压入数字栈,再将新符号入栈
  • 最后将符号栈使用计算过程清空
  • 数字栈最后一个元素就是结果

看图理解👇
这案例的情况压入的符号,会出现压入符号比栈顶优先级低的情况。
如果出现压入符号和栈顶优先级相同,也是要先计算的。
第七步到第八步省略了,50入栈,/号入栈,10入栈。

WechatIMG109.png

 

括号匹配

在书写代码或者表达式中,我们使用的[]{}()符号是如果验证输入正确符合规范的呢?也是可以利用栈去检查。

  • 从左到右遍历字符串
  • 将左括号“({[”这些压入栈
  • 如果遇到右括号“)}]”这些就取出栈顶元素,查看是否匹配
  • 匹配则出栈,继续下一步
  • 遍历结束,栈为空则我们的输入符合规范

浏览器前进后退操作

浏览器的前进后退,是我们接触最多的一个常见,它是如何保持我们的历史浏览记录,实现前进后退操作的呢?
有很多种方式实现,栈就是应用很广的一种。

  • 用两个栈实现浏览页面的存储X、Y,我们的视口页面始终为X栈顶页面
  • 浏览页面,压入X栈
  • 点击后退取出X栈顶页面,压入Y栈
  • 点击前进,取出Y栈顶页面,压入X栈
  • 如果X栈取出栈顶后,没有元素证明为最后一个页面,无法回退。

leetcode实战

通过真题,我们巩固一下栈的概念和操作。如果数据符合在一端插入删除,我们就可以考虑用栈去解决。

155. 最小栈👈

问题:

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 getMin() —— 检索栈中的最小元素。

提示:

  • poptopgetMin 操作总是在 非空栈 上调用。

示例:

输入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出:
[null,null,null,null,-3,null,0,-2]

解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.
复制代码

思路:

典型的栈的实现,只是多了一个功能,可以获取栈的最小值。
问题就是我们怎么提供获取最小元素的接口。

  1. 最简单每次获取时,比较栈内所有的值,计算输出最小。但是这样时间复杂度会高。
  2. 还有一种方式是,再用一个小栈维护最小值。每次入栈新元素时,将当前栈的最小值同时压入小栈。此时压入小栈的元素只有两种情况:
  • 当前新的元素(新元素最小)
  • 之前的最小元素

出栈时,两个栈同时出栈顶元素。这样就能保持小栈的栈顶一直是当前最小的元素。
借助leetcode官方的图解

155_fig1.gif

 

代码:

var MinStack = function() {
    this.list = []
    this.min = [Infinity]
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.list.push(x)
    // 比较当前值和之前最小值,压入小栈
    this.min.push(Math.min(x,this.min[this.min.length - 1]))
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.list.pop()
    this.min.pop()
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.list[this.list.length - 1]
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.min[this.min.length - 1]
};
复制代码

20. 有效的括号👈

问题:

给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例:

输入: "()"
输出: true

输入: "()[]{}"
输出: true

输入: "(]"
输出: false

输入: "([)]"
输出: false

输入: "{[]}"
输出: true
复制代码

思路:

  • 遍历字符串
  • 将左括号压入栈
  • 遇到右括号,取出栈顶元素匹配(检查是否左右括号对应上)
  • 遍历结束,如果符合,栈应该为空

直接看代码👇

代码:

var isValid = function (s) {
    // 括号为双数才符合
    if (s.length % 2 !== 0) return false
    // 顺序栈
    let list = []
    // 存储括号对应关心
    let map = new Map([[')', '('], ['}', '{'], [']', '[']])
    for (let i = 0; i < s.length; i++) {
        let item = s[i]
        if (map.has(item) && list[list.length - 1] === map.get(item)) {
            // 匹配成功,出栈
            list.pop()
            continue
        } else if (map.has(item) && list[list.length - 1] !== map.get(item)) {
            // 匹配失败
            return false
        }
        list.push(item)
    }
    return list.length === 0
};
复制代码

844. 比较含退格的字符串👈

问题:

给定 S 和 T 两个字符串,当它们分别被输入到空白的文本编辑器后,判断二者是否相等,并返回结果。 # 代表退格字符。

注意:如果对空文本输入退格字符,文本继续为空。 提示:

1 <= S.length <= 200 1 <= T.length <= 200 S 和 T 只含有小写字母以及字符 '#'。

  进阶:

你可以用 O(N) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗?

示例:

输入:S = "ab#c", T = "ad#c"
输出:true
解释:S 和 T 都会变成 “ac”。

输入:S = "ab##", T = "c#d#"
输出:true
解释:S 和 T 都会变成 “”。

输入:S = "a##c", T = "#a#c"
输出:true
解释:S 和 T 都会变成 “c”。
复制代码

思路:

判断两个字符串是否相等,我们只需要计算出退格后的字符串再比较就好。插入和退格操作和栈的结构一样,都是在栈顶实现。所以我们可以用栈去进行退格操作。

  • 遍历字符串
  • 遇到#,删除栈顶元素,其余的入栈

代码:

var backspaceCompare = function (S, T) {    
        function pushStack (str){
        let list = []
        for(let i =0;i<str.length;i++){
            if(str[i]!=='#')list.push(str[i])
            else list.pop()
        }
        return list.join('')
    }
    return pushStack(S)===pushStack(T)
}
复制代码

思路:

但是进阶要求我们在空间复杂度O(1)完成操作。这样我们就不能申请新的空间存储字符串。
可以通过双指针遍历比较的方式。

  • 从字符串末尾开始遍历,保存#号出现次数
  • 遇到正常字符串且退格次数大于零时,(该字符需要删除)就跳过该字符
  • 其余的情况,字符是需要保留下来的,也就是我们需要比较的对象
  • 每一次两个指针都会指向留存的字符,比较是否相同

代码:

var backspaceCompare = function (S, T) {
    let i = S.length - 1
    let k = T.length - 1
    let sback = 0
    let tback = 0
    // 比较到两个指针都指向小于0为止
    while (i >= 0 || k >= 0) {
        // 处理需要退格的字符
        while (i >= 0) {
            if (S[i] === '#') {
                sback++
                i--
            } else if (sback > 0) {
                sback--
                i--
            } else {
                break
            }
        }
        while (k >= 0) {
            if (T[k] === '#') {
                tback++
                k--
            } else if (tback > 0) {
                tback--
                k--
            } else {
                break
            }
        }
        // 经过两个指针的退格处理后,这一步指向的都是需要留存的字符
        if (S[i] !== T[k]) return false
        k--
        i--
    }
    return true
};
复制代码

232. 用栈实现队列👈

问题:

使用栈实现队列的下列操作:

push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。

说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。 假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。

示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false
复制代码

思路:

队列:先进先出的数据结构,操作刚好和栈相反。
栈是不能直接从数据开始取出元素的,不符合规范。所以我们只能用栈去模拟实现队列的操作。
得想办法将栈反转过来,这样栈顶部元素就是队列的首元素。必须借助另一个栈实现。

WechatIMG113.png
WechatIMG286.png
  • 其实插入操作,我们还是和普通栈一样,直接插入即可。
  • 不同的就是取队列首元素,要取栈底部的元素。所以取的操作我们需要反转栈。
  • 这时就要借助“黄色”栈去保存,依次取出“蓝色”栈,压入“黄色”栈。
  • 这样“黄色”栈顶就是最开始的元素。取操作就在“黄色”栈操作。
  • 如果“黄色“栈空了,重新去“蓝色”栈反转获取。

代码:

var MyQueue = function () {
    this.pushList = []
    this.popList = []
};

/**
 * Push element x to the back of queue. 
 * @param {number} x
 * @return {void}
 */
MyQueue.prototype.push = function (x) {
    this.pushList.push(x)
};

/**
 * Removes the element from in front of queue and returns that element.
 * @return {number}
 */
MyQueue.prototype.pop = function () {
    // 黄色栈空了,重新反转
    if (this.popList.length === 0) {
        while (this.pushList.length > 0) {
            this.popList.push(this.pushList.pop())
        }
    }
    return this.popList.pop()
};

/**
 * Get the front element.
 * @return {number}
 */
MyQueue.prototype.peek = function () {
    // 黄色栈空了,重新反转
    if (this.popList.length === 0) {
        while (this.pushList.length > 0) {
            this.popList.push(this.pushList.pop())
        }
    }
    return this.popList[this.popList.length - 1]
};

/**
 * Returns whether the queue is empty.
 * @return {boolean}
 */
MyQueue.prototype.empty = function () {
    // 判断是否为空时,蓝色和黄色栈都要计算长度
    return this.popList.length <= 0 && this.pushList.length <= 0
};
复制代码

496. 下一个更大元素 I👈

这也是一个经典题。可以用栈的逻辑去思考。

问题:

给定两个 没有重复元素 的数组 nums1 和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在,对应位置输出 -1 。

提示:

  1. nums1nums2中所有元素是唯一的。
  2. nums1nums2 的数组大小都不超过1000。

示例:

输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
    对于num1中的数字4,你无法在第二个数组中找到下一个更大的数字,因此输出 -1。
    对于num1中的数字1,第二个数组中数字1右边的下一个较大数字是 3。
    对于num1中的数字2,第二个数组中没有下一个更大的数字,因此输出 -1。

输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
    对于 num1 中的数字 2 ,第二个数组中的下一个较大数字是 3 。
    对于 num1 中的数字 4 ,第二个数组中没有下一个更大的数字,因此输出 -1复制代码

思路:

最简单的逻辑是,我们遍历nums1,获取元素在nums2中依次遍历,首先找到自己,然后下一个元素开始比较,找到比自身大的便停止。这样nums1的循环遍历中还要嵌套nums2的循环,时间复杂度O(n*m)。

第二种思路就是单调栈
单调栈就很适合处理此类“下一个元素”的问题。
单调栈也是普通的栈结构,只不过它相当于排序后的栈,只插入越来越小的元素,或越来越大的元素。

  • 首先我们可以忽略nums1,我们先将nums2每个元素的下一个更大元素找出来,并存在哈希表中,这里我们用Map结构。
  • 怎么找?我们需要借助一个单调栈。栈用来保存没有找到更大值的元素。所以插入的值会越来越小,如果大于证明找到了,我们可以依次出栈。而真正的对应关系存在Map中。
  • 遍历nums2,将元素压入栈,入栈前比较栈顶元素,如果小于,入栈。
  • 如果大于栈顶元素,证明栈顶元素的最大值找到了,出栈,并记录Map。
  • 直到遍历结束,栈内剩余的元素,都是找不到下一个更大值的。

leetcode解析这里有看到一个很不错的解析,总结了此类“下一个元素”题型的解法,思路。

代码:

var nextGreaterElement = function (nums1, nums2) {
    // 单调栈
    let list = []
    // 对应表
    let map = new Map()
    for (let i = 0; i < nums2.length; i++) {
        while (nums2[i] > list[list.length - 1]&&list.length>0) {
            // 找到下一个更大值,出栈并更新Map
            map.set(list.pop(),nums2[i])
        }
        // 将当前nums2元素,记入map,初始-1,并入栈
        map.set(nums2[i],-1)
        list.push(nums2[i])
    }
    // 遍历nums1,在map中获取结果
    return nums1.map((n)=>{
        return map.get(n)
    })
};
复制代码

224. 基本计算器👈

计算器来了,先回想一下前面讲的栈的应用。

问题:

实现一个基本的计算器来计算一个简单的字符串表达式的值。 字符串表达式可以包含左括号 ( ,右括号 ),加号 + ,减号 -非负整数和空格

说明:

  • 你可以假设所给定的表达式都是有效的。
  • 不要使用内置的库函数 eval

示例:

输入: "1 + 1"
输出: 2

输入: " 2-1 + 2 "
输出: 3

输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23
复制代码

思路:

计算表达式,我们先回顾:
加减乘除使用了两个栈分别保存数字和运算符。依据压入的运算符,当压入较小优先级或相同优先级的运算符时,先取栈顶符号计算。原因:

  • 乘除符号比加减计算顺序上优先级高,在收集完成数字后便可以计算。
  • 优先级相同的两个符号,遵循从左到右计算原则。


同样这一题我们只需要多考虑两种情况,括号,多位数。

  • 括号内的运算逻辑和之前一样
  • 遇到左括号需要标记,下一个运算符出现不用计算
  • 遇到右括号,则将之前左括号内的剩余的运算符计算
  • 遇到数字要标记,因为可能是多位数,要一起收集入栈

这样可想而知,我们只需要多一个栈保存括号就好。然后再想想怎么标记左括号的下一个运算符不计算多位数的处理就可以了。
看代码👇,有注释,更方便食用。

代码:

var calculate = function (s) {
    // 括号栈
    let bra = []
    // 数字栈
    let num = []
    // 符号栈
    let ope = []
    // 标记是不是多位数
    let longNum = false
    for (let i = 0; i < s.length; i++) {
        let it = s[i]
        if (it === '(') {
            bra.push(it)
            longNum = false
        } else if (it === ')') {
            // 括号内如果存在多个运算符,之前已经计算了,最多只会剩余一个符号
            // 计算符号
            count(ope.pop())
            // 左括号出栈
            bra.pop()
            longNum = false
        } else if (it === '+' || it === '-') {
            // 如果不是刚遇到左括号,且之前有操作符号,则需要先计算
            if (bra[bra.length - 1] !== '(' && ope.length > 0) count(ope.pop())
            // 使用括号栈来标记是否与左括号相邻,如果括号栈长度大于零,则将空字符串入栈,表示多了一个操作符。
            // 这样读取括号栈顶时,如果是空字符串,就知道不是和左括号相邻
            if (bra.length > 0) bra.push('')
            ope.push(it)
            longNum = false
        } else if (parseInt(it) >= 0) {
            // 处理多位数
            if (!longNum) {
                num.push(it)
                longNum = true
            } else {
                num[num.length - 1] = num[num.length - 1] + it
            }
        }
    }
    if (ope.length > 0) count(ope.pop())
    if (num.length > 0) {
        let number = num[0]
        num = [parseInt(number)]
    }
    return num.pop() || 0
    function count(o) {
        if (!o) return
        // 处理符号计算的同时,也要将括号栈的空字符串标记出栈
        bra.pop()
        let n = parseInt(num.pop())
        let pre = parseInt(num[num.length - 1])
        num[num.length - 1] = o === '+' ? pre + n : pre - n
    }
};
复制代码

总结

  • 熟悉栈的特性:先进后出、后进先出。
  • 数组实现的顺序栈、链表实现的链式栈。
  • 栈这种数据结构的应用场景,表达式计算、历史记录、符号匹配等等。
  • 什么情况下使用栈?
    当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该首选“栈”这种数据结构。
  • 情况分不清时,多做题,同类型的写多了至少有点感觉。
免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

云计算

481

相关文章推荐

未登录头像

暂无评论