数据结构中的栈
栈是一种特殊的线性表，仅能够在栈顶进行操作，有着先进后出(后进先出)的特性。如下图
- 从数据存储的角度讲，实现栈有两种方式，一种是以数组为基础,一种是以链表为基础。
- 以数组的方式存储数据
// 先定义一个简单的Stack类 function Stack(){ // item不使用this,是为了防止变量暴露到外部，形成item私有变量。 // this.item=[];=>非常不推荐 // 设计类的时候属性不能暴露，非常安全 var item = [];//使用数组存储数据 }; - 栈的方法或者操作: push/pop/top/isEmpty/size/clear
- 以数组的方式存储数据
- push(element): 添加一个新元素到栈顶位置.
- pop()：移除栈顶的元素，同时返回被移除的元素。
- peek()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）。
- isEmpty()：如果栈里没有任何元素就返回true，否则返回false。
- clear()：移除栈里的所有元素。
- size()：返回栈里的元素个数。这个方法和数组的length属性很类似。
- 方法实现
- push 方法:将最新的元素放在了数组的末尾
// 压栈操作 this.push = function (element) { items.push(element) } - pop 方法:出栈操作应该是将栈顶的元素删除, 并且返回.
// 出栈操作 this.pop = function (element) { return items.pop() } - peek方法:主要目的是看一眼栈顶的元素
// peek操作 this.peek = function () { return items[items.length - 1] } - isEmpty方法:判断栈中是否有元素
// 判断栈中的元素是否为空 this.isEmpty = function () { return items.length == 0 } - size方法:获取栈中元素的个数
// 获取栈中元素的个数 this.size = function () { return items.length }- 整体代码
// 栈类
function Stack() {
// 栈中的属性
var items = []
// 栈相关的方法
// 压栈操作
this.push = function (element) {
items.push(element)
}
// 出栈操作
this.pop = function () {
return items.pop()
}
// peek操作
this.peek = function () {
return items[items.length - 1]
}
// 判断栈中的元素是否为空
this.isEmpty = function () {
return items.length == 0
}
// 获取栈中元素的个数
this.size = function () {
return items.length
}
// 清空栈
this.clear = function () {
items = [];
}
}
module.exports=Stack;
// 此处不要使用如下导出方式，如下方式实例化需要new Stack.Stack(), 直接将构造器导出到module上
// exports.Stack=Stack
- 栈的使用
- 测试题
- 题目答案：C
- A: 65进栈, 5出栈, 4进栈出栈, 3进栈出栈, 6出栈, 21进栈,1出栈, 2出栈
- B: 654进栈, 4出栈, 5出栈, 3进栈出栈, 2进栈出栈, 1进栈出栈, 6出栈
- D:65432进栈, 2出栈, 3出栈, 4出栈, 1进栈出栈, 5出栈, 6出栈
- 使用栈模拟
// 模拟面试题 var stack = new Stack() // 情况下代码模拟 stack.push(6) stack.push(5) stack.pop() // 5 stack.push(4) stack.pop() // 4 stack.push(3) stack.pop() // 3 stack.pop() // 6 stack.push(2) stack.push(1) stack.pop() // 1 stack.pop() // 2
- 测试题
- 思考
- 给你一个数组，你可以通过索引操作任意一个元素。但是给你一个栈，你能任意操作元素吗？栈提供给你的方法只允许你操作栈顶的元素。这种限制其实给了我们一种思考方式，这个方式也是栈的特性。后进先出，先进后出。
- 栈的底层实现其实就是数组，那为什么不直接使用数组的方法去做呢。这就是封装的思想，封装是为了隐藏实现细节，站在栈的角度思考问题会比数组的角度思考问题更加方便。
- 既然栈的底层就是对数组的操作，平时都这么熟悉数组，为什么没有自己去实现一个栈呢？尽管底层实现这么简单，越简单越能说明问题。
- 应用练习
- 用一个函数判断括号匹配问题
// 数组来存储的问题：存入数组再想办法一一抵消,但是无法判断一个左括号对应哪个右括号 // 栈的解决思路：for循环遍历每一个字符： function is_leagl_brackets(string){ var stack= new Stack(); for (var i=0 ; i<string.length ; i++) { var item = string[i]; // 遇到左括号，就把括号压入栈中 if(item=="("){ stack.push(item); // 遇到右括号，判断栈是否为空，如果为空，说明缺少左括号，直接返回false。如果栈不为空， // 就把栈顶元素移除，消除这对括号。 }else if (item==")"){ if(stack.isEmpty()){ return false; }else{ stack.pop(); } } } // 返回栈是否为空 return stack.isEmpty(); } console.log(is_leagl_brackets("()sadad(dsadsd)saf()(DFSFS)")); console.log(is_leagl_brackets("()()sd()(sd()fw)(")); - 后缀表达式
- 用一个函数判断括号匹配问题
function calc_exp(exp) {
var stack=new Stack();
for(var i=0;i<exp.length;i++){
var item=exp[i];
// 判断是否遇到运算符
if(["+","-","/","*"].indexOf(item)>=0){
// 弹出栈顶的两个元素
var value_1=stack.pop();
var value_2=stack.pop();
var exp_str=value_2+item+value_1;
// 计算并取整
var res=parseInt(eval(exp_str));
// 计算结果压入栈中,注意转成字符串，之前取整了
stack.push(res.toString())
// 未遇到运算符，入栈
}else{
stack.push(item);
// console.log(item)
}
}
// 返回栈中的元素
return stack.pop();
}
console.log(calc_exp(["4","13","6","/","+"])) // 6
console.log(calc_exp(["10","6","9","3","+","-11","*","/","*","17","+","5","+"])) // 2
- 实现min 方法=>返回栈里最小的元素 时间负责度为o(1)
// 引入写好的stack模块，思路：建立两个栈，一个存储数据，一个存储最小值
Stack = require("./stack")
function MinStack(){
var data_stack=new Stack(); // 存储数据
var min_stack=new Stack(); // 存储最小值
// push方法 往栈中放入最小值作为栈顶
this.push = function (item) {
// 将值存入栈
data_stack.push(item);
// 栈为空或者item小于栈顶的元素
if(min_stack.isEmpty()||item< min_stack.peek()){
// item为最小值成为栈顶
min_stack.push(item);
}else{
min_stack.push(min_stack.peek())
}
}
// pop方法弹出栈顶
this.pop=function(){
data_stack.pop();
min_stack.pop();
}
// min方法，返回栈中最小值
this.min=function(){
return min_stack.peek();
}
}
minstack= new MinStack();
minstack.push(3);
minstack.push(6);
minstack.push(8);
console.log(minstack.min()); // 3
minstack.push(2);
console.log(minstack.min()); // 2
