一、什么是数据结构栈
在数据结构中有一个栈结构,在内存空间中也有一个栈空间,这两个”栈“是两个不同的概念。这篇我们说的是数据结构中的栈。栈是一种特殊的线性表,特殊性体现在只能在栈顶进行操作,往栈顶添加元素,一般叫push, 入栈;从栈顶移除元素,一般叫pop, 出栈,操作如图:
这个特征叫”后进先出“,Last In First On, 简称LIFO。和JS数组中的push和pop函数功能有点像。当然栈的内部设计,就可以用数组,或者也可以用链表。
二、栈结构设计和应用示例
2.1 内部实现:
栈结构对外暴露的方法有入栈(push)、出栈(pop)、获取栈顶元素(top)、获取栈长度(length)、清空栈内元素。如图:
这里贴出内部用数组实现的栈设计构造函数,链表实现见Github
/**
* 数据结构栈:先进后出,后进先出,即LIFO,栈的内部实现可以用数组,也可以用链表;
* 这里先用数组实现,对外暴露的方法有:
* push(element): 放入一个元素,即入栈
* pop() : 移除栈顶元素,即出栈
* top() : 获取栈顶元素
* clear() : 移除所有栈元素
* length() : 获取栈长度
*/
const Stack = function(){
let arr = []; //内部数组
//入栈方法
function push(element){
arr.push(element);
}
//出栈方法
function pop(){
return arr.pop();
}
//获取栈顶元素
function top(){
return arr.length > 0 ? arr[arr.length-1]:null;
}
//移除所有栈元素
function clear(){
arr = [];
}
//获取栈长度
function length(){
return arr.length;
}
this.push = push;
this.pop = pop;
this.top = top;
this.clear = clear;
this.length = length;
}
2.2 在这个栈构造函数的基础上,做几题目应用实践一下
2.2.1 用栈实现将十进制数字转成二进制,和八进制
/**
* 十进制转成二进制或八进制
* @param num 十进制数字
* @param base =2表示转成二进制,=8表示转成八进制
*/
function numChange(num, base){
var stack = new Stack();
do {
stack.push(num%base);
num = Math.floor(num/base);
}while(num > 0)
let str = '';
while(stack.length()>0){
str += stack.pop();
}
return str;
}
console.log(numChange(8, 2));
console.log(numChange(9, 2));
console.log(numChange(10, 2));
console.log(numChange(8, 8));
console.log(numChange(17, 8));
console.log(numChange(35, 8));
2.2.2 用栈来判断一个字符串是否回文。比如"abc"不是回文,"abcba"是回文,"abccba"是回文
//测试3,判断一个字符串是否回文
function isCircle(s){
let stack = new Stack();
for(let i = 0; i < s.length; i++){
stack.push(s[i]);
}
let newStr = '';
while(stack.length() > 0){
newStr += stack.pop();
}
return newStr == s;
}
console.log("\n\n判断一个字符串是否回文....");
console.log(isCircle("abc"));
console.log(isCircle("abcdcba"));
console.log(isCircle("helloolleh"));
三、力扣栈结构应用题目
3.1 有效的括号_第20题
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
/**
* 执行用时 :68 ms, 在所有 JavaScript 提交中击败了98.63%的用户
* 内存消耗 :33.7 MB, 在所有 JavaScript 提交中击败了76.56%的用户
*/
let arr = [], temp = top = null;
for (let i = 0; i < s.length; i++){
temp = s[i];
//碰到左括号,入栈
if (temp == '(' || temp == '[' || temp == '{'){
arr.push(temp);
}
//碰到右括号,出栈
else{
if (arr.length < 1) return false;
top = arr[arr.length-1];
if ((temp == ')' && top == '(')||
(temp == ']' && top == '[')||
(temp == '}' && top == '{')){
arr.pop();
}
else{
return false;
}
}
}
return arr.length > 0 ? false : true;
};
3.2 根据括号计算分数_第856题
/**
* @param {string} S
* @return {number}
* 执行用时 :80 ms, 在所有 JavaScript 提交中击败了62.96%的用户
* 内存消耗 :33.7 MB, 在所有 JavaScript 提交中击败了33.33%的用户
*/
var scoreOfParentheses = function(S) {
let arr = [], temp = null;
for (let i = 0; i < S.length; i++){
temp = S[i];
if (temp == '('){
arr.push(temp);
}
else{
if (arr.length < 1) return 0;
//调整栈,找到数组里面配套的左括号,如果目标左括号在栈顶,调整"("为1;
// 如果目标左括号不在栈顶,则从栈顶到目标左括号累加,每累加一次,出栈一次;
// 一直到目标左括号成为栈顶,这事根据规则(A)=2*A,则目标左括号位置的值为2*累加分
// 比如:()()((()(()())())()())
// [1,1,(,(,1,4,1
findTarget(arr);
}
}
return findTarget(arr);
};
//寻找匹配左括号, 倒序找到第一个匹配的"(",然后调整目标位置的值
function findTarget(arr){
let score = 0;
for (let i = arr.length-1; i >= 0; i--){
if (arr[i] == '('){
arr[i] = score > 0 ? 2*score : 1;
return 0;
}
else{
score += arr.pop();
}
}
return score;
}
3.3 逆波兰式求值_第150题
我们普通的运算式叫中缀表达式,后缀表达式是把运算符号写在数字后面,前缀表达式是把运算符号写在数字前面。比如
中缀表达式:a+b, 用后缀表达式为:ab+, 用前缀表达式为:+ab ;
中缀表达式:(a + b) * c - d/e, 用后缀表达式为:ab+c*de/-, 前缀表达式为:-*+abc/de
中缀表达式方便人类识别,后缀表达式是为了方便计算机识别,后缀表达式也叫逆波兰式;前缀表达式也叫波兰式
/**
* @param {string[]} tokens
* @return {number}
* 执行用时 :92 ms, 在所有 JavaScript 提交中击败了91.72%的用户
* 内存消耗 :37.2 MB, 在所有 JavaScript 提交中击败了40.48%的用户
*/
var evalRPN = function(tokens) {
//用栈来实现,碰到数字入栈,碰到运算符号,出栈计算
let arr = [], str = null;
for (let i =0; i < tokens.length; i++){
str = tokens[i];
if (str == "+" || str == "-" || str == "*" || str == "/"){
let num2 = parseInt(arr.pop()), num1 = parseInt(arr.pop()), res = 0;
if (str == "+"){
res = num1 + num2;
}
else if(str == "-"){
res = num1 - num2;
}
else if(str == "*"){
res = num1 * num2;
}
else if(str == "/"){
res = parseInt(num1 / num2);
}
arr.push(res);
}
else{
arr.push(str);
}
}
return arr.length ? arr.pop() : 0;
};
3.4 基本计算器_第224题(困难)
/**
* 按顺序计算,存储左括号前面的运算符,碰到“-”号,后面匹配的数字为相反数。相当于去括号计算
* @param s
* @return {number}
* 执行用时 :112 ms, 在所有 JavaScript 提交中击败了88.14%的用户
* 内存消耗 :36.8 MB, 在所有 JavaScript 提交中击败了94.12%的用户
*/
var calculate = function(s){
let arr = [], sum = 0, num = 0, flag = 1;
s = "+" + s; //前面加一个+号
for (let i = 0; i < s.length; i++){
if (s[i] == '+' || s[i] == '-'){ //+-后面可能为数字/空格/左括号
temp = s[i];
let need_up = false;
while(s[i+1] < '0' || s[i+1] > '9'){
if (s[i+1] == '('){ //将左括号前面的符号压入栈。一个左括号匹配一个+-号
need_up = true;
arr.push(temp);
}
i++;
}
//+-号后面的数字,或者+-号后面口号里面的数字
while(s[i+1] >= '0' && s[i+1] <= '9'){
num = num*10 + (s[i+1] - '0'); //拼接完整数字
i++;
}
if (temp == '+'){
sum += flag * num;
}
else{
sum -= flag * num;
}
num = 0;
if (need_up && arr[arr.length-1] == '-'){
flag *= (-1); //如果左括号前是-号,flag需要反转
}
}
else if(s[i] == ')'){
if (arr[arr.length-1] == '-'){
flag *= (-1); //移除-号时,flag需要反转
}
arr.pop(); //碰到右括号移除一个运算符
}
}
return sum;
}
栈链表实现和题目完整Demo见:https://github.com/xiaotanit/Tan_DataStruct