栈只能一个数据 一个数据操作
栈的定义:
栈是特殊的线性表,仅能够在栈顶操作,有着先进后出的特殊性
从数据存储角度来看,实现栈的方式有两种,一种是以数组为基础,一种是以链表为基础,数组是最为简单的实现凡事
栈的方法应该有哪些:
1 push 添加一个元素到栈顶
2 pop 弹出一个栈顶元素
3 top 返回到栈顶元素
4 isEmpty 判断数组栈是不是空的
5 size 返回栈里的元素个数
6 clear 清空栈
——————————————————————————
使用栈的例子 练习题
下面的字符中包含小括号,请编写一个函数判断字符串中的括号是否合法,所谓合法,就是口号成对的出现
dasda(dad(s(da)sda)as)(dada)
(da(dasda)sd(dasdas)a)
()()(dasdas(dasdas)d)(
用栈的思维来做
遇到左括号,把左括号压入栈中
遇到右括号,判断栈是否为空,为空则说明没有左括号与之对应,不合法,如果不为空,则把栈顶元素移除,这对括号抵消掉
// 也可以用正则来判断
str.match(/(/)
str.match(/)/)
判断长度
——————————————————————
计算逆波兰表达式
逆波兰表达式,也叫后缀表达式,它是将复杂表达式转换为可以依靠简单操作得到计算结果的表达式 例如(a+b)(d+c) 转化为ab+cd+
后缀表达式
1+2 的后缀表达式 1 2+
2+3+5的后缀表达式 2 3 5 + +
好处 计算机都是把中缀表达式 转化为后缀表达式 进行计算
例子: var str = [4,13,5,'/','+'];
遍历数组,对每个元素做如下操作
如果不是运算符 ,就压入栈中
如果是运算符如+ - / ,则从栈里连续弹出两个元素,并对两个元素进行计算,将结果压入栈中
for循环结束之后,栈里只有一个元素,这个元素就是整个表达式的计算结果
————————————————————
中缀表达式
1+2
1+2+3
这些是中缀表达式
————————————————————
中缀表达式转后缀表达式 在git上
————————————————————————————————————
1 队列的定义
队列是一中特殊的线性表,其特殊之处在于,它之允许你在队列头部删除元素,在队列尾部添加元素
队列的方法:
enqueue: 从队列尾部添加一个元素
dequeue: 从队列头部删除一个元素
head: 返回头部的元素,注意不是删除
size: 返回队列大小
clear: 清空队列
isEmpty: 判断是否为空
tail: 返回尾部节点
——————
约瑟夫环
有一个数组a100存放0-99;要求每隔两个数删掉一个数,到末尾时循环至开头继续进行,求最后一个被删除的数
————————
斐波那契数列
这个数列从第3项开始,每一项都等于前两项之和。
用对列实现栈
用两个队列实现一个栈
————————————
打印杨辉三角