栈的模拟实现及常见算法
2021-03-31 18:28
标签：lan 最大 线性 重复 思路 不为 结果 tar 直方图 栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。栈按照后进先出的原则来存储数据，也就是说，先插入的数据将被压入栈底，最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。栈在汇编语言程序中，经常用于重要数据的现场保护。栈中没有数据时，称为空栈。 利用栈将转化数字的进制，假设将数字n转换为以b为基数的数字，方法如下: 利用栈，可以轻松判断一个字符串是否是回文(回文指一个字符串从前往后写和从后往前写都一样) 当然正常我们直接使用 实现一个特殊的栈，有栈的正常方法，能返回栈里的最小值。要求时间复杂度为O(1) 思路：创建两个栈，一个栈 data 放正常的数据。另一个栈 mins 放当前数据中的最小值。例如：若新添加的数据小于当前的最小值，两个栈都添加新的数据。若新添加的数据大于当前栈中的最小值，mins 仍然添加当前最小值。 而且，data出数据的时候，mins同时出栈。 leetCode 20:给定一个只包括 ‘(‘，‘)‘，‘{‘，‘}‘，‘[‘，‘]‘ 的字符串，判断字符串是否有效。 有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。 LeetCode 739: 根据每日气温列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。 图解链接： https://mp.weixin.qq.com/s/3kDSOHyd-qOw7apzj0Z9YQ 利用堆栈，还可以解决如下常见问题： 参考链接 https://github.com/lznbuild/my-blog/issues/26 https://mp.weixin.qq.com/s/3kDSOHyd-qOw7apzj0Z9YQ 栈的模拟实现及常见算法 标签：lan 最大 线性 重复 思路 不为 结果 tar 直方图 原文地址：https://www.cnblogs.com/suihang/p/13564483.html定义
模拟实现
class Stack{
constructor(){
this.stack = [];
this.top = 0;
this.max=10000;
};
// 入栈
push(item){
if(this.topthis.max){
this.top++;
this.stack.push(item);
}else{
consle.error(‘栈溢出‘)
}
}
// 出栈
pop(){
if(this.top > 0) {
let x = this.stack.pop();
this.top--;
return x;
}else{
console.log(‘栈已经为空‘)
}
}
// 判断栈是否为空
empty(){
return this.top === 0;
}
// 返回位于栈顶的元素
peek(){
return this.stack[this.top];
}
// 栈的大小
size(){
return this.top;
}
}
常见应用
进制转换
function mulBase(num, base){
var stack = new Stack();
do {
stack.push(num % base);
num = Math.floor(num /= base)
} while(num > 0)
var str = ‘‘;
while(stack.length() > 0){
str += stack.pop();
}
return str
}
回文判断
function isPalindrome(word){
var stack = new Stack();
for(var i = 0, len = word.length; i++){
stack.push(word[i]);
}
var rword = ‘‘;
while(stack.length() > 0){
rword += stack.pop();
}
return rword == word;
}
var arr = Array.prototype.slice.call(word);
return arr.reverse().join(‘‘) == word
实现特殊栈
常见的算法
有效的括号
var isValid = function(s) {
let map = {
‘(‘: -1,
‘)‘: 1,
‘[‘: -2,
‘]‘: 2,
‘{‘: -3,
‘}‘: 3
}
let stack = []
for (let i = 0; i ) {
if (map[s[i]] ) {
stack.push(s[i])
} else {
let last = stack.pop()
if (map[last] + map[s[i]] != 0) return false
}
}
if (stack.length > 0) return false
return true
}
每日温度
const dailyTemperatures = function(T) {
const len = T.length // 缓存数组的长度
const stack = [] // 初始化一个栈
const res = (new Array(len)).fill(0) // 初始化结果数组，注意数组定长，占位为0
for(let i=0;i
其他