js数组实现栈数据结构与练习使用
栈的定义
栈是一种特殊的线性表,栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的
同一端,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。
在现实生活中也能发现很多栈的例子。例如,下图里的羽毛球桶就是一个例子
下面我们来实现一个栈
function Stack(){
var items = []; //存储数据
//从栈顶添加元素,也叫压栈
this.push=function(item){
items.push(item);
};
//从栈顶移除元素
this.pop=function(){
return items.pop();
}
//返回栈顶元素
this.top=function(){
return items[items.length-1];
}
//判断栈是否为空
this.isEmpty=function(){
return items.length == 0;
}
//返回栈的长度
this.size=function(){
return items.length;
}
//清空栈
this.clear=function(){
items=[];
}
}
我们可以用栈来校验字符串中的括号是否合法
//判断括号是否合法函数
function is_leagl_brackets(string){
var stack=new Stack();
if(string){
for(var i=0; i<string.length; i++){
var item = string[i];
//遇到左括号入栈
if(item == "("){
stack.push(item);
}else if(item == ")"){
//遇到右括号判断是否为空 为空返回false 不为空删除栈顶元素
if(stack.isEmpty()){
return false;
}else{
stack.pop();
}
}
}
}
//最后返回栈是否为空
return stack.isEmpty();
};
console.log(is_leagl_brackets("()((((s))))")) //true
console.log(is_leagl_brackets("()((((s)))))")) //false
console.log(is_leagl_brackets("(())((((s)))))")) //false
console.log(is_leagl_brackets(")()(")) //false
还可以计算后缀表达式
//计算后缀表达式
function calc_exp(exp){
var stack = new Stack();
for(var i=0;i<exp.length;i++){
var item=exp[i];
if(["+","-","*","/"].indexOf(item) !=-1){
var val1=stack.pop();
var val2=stack.pop();
var exp_str=val2 + item + val1;
//计算并解析字符串
var res=parseFloat(eval(exp_str));
//结果压入栈中
stack.push(res.toString());
}else{
stack.push(item);
}
}
//返回栈顶元素
return stack.pop();
}
console.log(calc_exp(["4","13","5","/","+"])); //6.6
利用栈来实现一个栈中最小值并且时间复杂度为O(1);
//找出栈中最小值的方法且时间复杂度为O(1)
function MinStack(){
var data_stack=new Stack(); //存储数据
var min_stack=new Stack(); //存储最小的值
this.push=function(item){
data_stack.push(item);
//判断是否为空或者是否小于最小栈顶
if(min_stack.isEmpty() || item < min_stack.top()){
min_stack.push(item);
}else{
min_stack.push(min_stack.top());
}
}
//弹出栈顶元素
this.pop=function(){
min_stack.pop();
return data_stack.pop();
}
//返回栈的最小值
this.min=function(){
return min_stack.top();
}
}
var minStack=new MinStack();
minStack.push(2);
minStack.push(1);
minStack.push(23);
console.log(minStack.min()) //1
minStack.pop();
minStack.pop();
console.log(minStack.min()) //2
进阶版:将中缀表达式转化为后缀表达式 [‘1’,’+’,‘2’]=>[‘1’,‘2’,’+’]
//中缀表达式转后缀表达式
var priority_map = {"+": 1,"-": 1,"*": 2,"/": 2};
function infix_exp_2_postfix_exp(exp){
var stack = new Stack();
var postfix_lst = [];
for(var i = 0;i<exp.length;i++){
var item = exp[i];
// 如果是数字,直接放入到postfix_lst中
if(!isNaN(item)){
postfix_lst.push(item);
}else if (item == "("){
// 遇到左括号入栈
stack.push(item);
}else if (item == ")"){
// 遇到右括号,把栈顶元素弹出,直到遇到左括号
while(stack.top() != "("){
postfix_lst.push(stack.pop());
}
stack.pop(); // 左括号出栈
}else{
// 遇到运算符,把栈顶的运算符弹出,直到栈顶的运算符优先级小于当前运算符
while(!stack.isEmpty() && ["+", "-", "*", "/"].indexOf(stack.top()) >= 0
&& priority_map[stack.top()] >= priority_map[item]){
// 把弹出的运算符加入到postfix_lst
postfix_lst.push(stack.pop());
}
// 当前的运算符入栈
stack.push(item);
}
}
// for循环结束后, 栈里可能还有元素,都弹出放入到postfix_lst中
while(!stack.isEmpty()) {
postfix_lst.push(stack.pop())
}
return postfix_lst
};
// 12+3
console.log(infix_exp_2_postfix_exp(["12","+", "3"]))
// 2-3+2
console.log(infix_exp_2_postfix_exp(["2","-", "3", "+", "2"]))
// (1+(4+5+3)-3)+(9+8)
var exp = ["(","1","+","(","4","+","5","+","3",")","-","3",")","+","(","9","+","8",")"];
console.log(infix_exp_2_postfix_exp(exp))
好了我们已经大概了解栈了,如果上方例子用数组想的话会难好多吧!