# 基本概念
栈是一种遵循后进先出原则的有序集合。一端叫栈顶,一端叫栈底,新元素靠近栈顶,旧元素靠近栈底。
栈是一种受限的数据结构, 体现在只允许新的内容从一个方向插入或删除。
生活中我们可以发现很多栈的例子,例如一摞书或者叠放的盘子。
# 栈的一些方法
push(item)
: 添加元素到栈顶,称为入栈。pop()
: 移除栈顶元素,同时返回被移除的元素,称为出栈。peek()
: 返回栈顶元素,不对栈做任何修改。isEmpty()
: 栈是否为空,没有任何元素返回true,否则返回false。clear()
: 移除栈里的所有元素。size()
: 返回栈里元素个数。
# 用js实现一个栈
class Stack {
constructor() {
this._items = []
}
push(item) {
this._items.push(item)
}
pop() {
return this._items.pop()
}
peek() {
if (this._items.length) {
return this._items[this._items.length - 1]
}
return undefined
}
isEmpty() {
return this._items.length === 0
}
size() {
return this._items.length
}
clear() {
this._items = []
}
}
# 单调栈
单调栈要求栈中的元素是单调递减或者单调递减的。
单调增还是单调减取决于出栈顺序。如果出栈的元素是单调增的,那就是单调递增栈,如果出栈的元素是单调减的,那就是单调递减栈。
例如[1,2,3,4] 就是一个单调递减栈,[3,2,1] 就是一个单调递增栈。
单调递减栈也被称为最大栈,因为栈顶元素始终是最大的;单调递增栈也被称为最小栈,因为栈顶元素始终是最小的。
适合求解下一个大于 xxx或者下一个小于 xxx这种题目。
# 栈的常见题目
大家在使用栈的时候,要始终牢记栈的特性后进先出,多多练习相关题目和各种题解,逐渐形成题感。
进制转换
十进制整数转换二进制:除2取余,直到商为0为止,将得到的余数反向排列输出即可;
同理,十进制整数转换R进制:除R取余,直到商为0为止,将得到的余数反向排列输出即可;
function decimalBaseConvert(decimalNumber, base) { if (typeof decimalNumber !== "number" || typeof base !== "number") { throw new Error('decimalNumber && base should be number') } const remStack = new Stack() const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ' let baseStr = '' let rem let number = decimalNumber if (base < 2 || base > 36) { throw new Error('base should >=2 && <=36') } while (number !== 0) { rem = number % base remStack.push(rem) number = Math.floor(number / base) } while (!remStack.isEmpty()) { baseStr += digits[remStack.pop()] } return baseStr }
150. 逆波兰表达式求值 (opens new window)
该题目就是利用栈先进后出的特性来进行解决,遇到运算符,出栈两次进行运算,然后将结果入栈;遇到非运算符直接入栈,最后栈顶就是我们表达式的结果。
function evalRPN(tokens) { const stack = new Stack() const map = { '+': (a, b) => a + b, '-': (a, b) => a - b, '*': (a, b) => a * b, '/': (a, b) => Math.trunc(a / b) } tokens.forEach(ele => { if (map.hasOwnProperty(ele)) { const first = stack.pop() const second = stack.pop() let result = map[ele](second, first) stack.push(result) } else { stack.push(Number(ele)) } }); return stack.pop() }
496. 下一个更大元素 I (opens new window)
该题目我们就可以巧用单调栈进行解决,降低时间复杂度,更多详解请看官方题解。
var nextGreaterElement = function(nums1, nums2) { const result = [] const stack = [] const map = new Map() for(let i = 0; i < nums2.length; i++) { while(stack.length && stack[stack.length - 1] < nums2[i]) { map.set(stack.pop(), nums2[i]) } stack.push(nums2[i]) } stack.forEach((ele) => map.set(ele, -1)) for(let i = 0; i < nums1.length; i++) { result[i] = map.get(nums1[i]) } return result }
# 推荐题目(应该掌握的题目)
- 简单
- 中等
- 困难
# 更多文章
- javascript数据结构与算法第三版
- leetcode-栈 (opens new window)
- 力扣加加-单调栈 (opens new window)
队列 →