《数据结构与算法JavaScript描述》- 栈
栈是和列表类似的一种数据结构,是一种特殊的列表,可解决计算机世界里很多问题
栈是一种高效的数据结构,因为数据只能在栈顶添加或删除,所以这样的操作很快
栈内的元素只能通过列表的一端访问,这一端称为栈顶
栈是一种后入先出(LIFO,last-in-first-out)的数据结构
对栈的两种主要操作是将一个元素压栈和弹栈,另一个常用操作是预览栈顶的元素
实现一个栈当务之急是决定存储数据的底层数据结构,这里采用数组
function Stack() { this.dataStore = []; // 存储数据 this.top = 0; // 为了记录栈顶元素的位置,同时也标明哪里可加入新元素 this.push = push; // 压栈 this.pop = pop; // 弹栈 this.peek = peek; // 预览栈顶元素 this.length = length; // 返回栈内元素个数 this.clear = clear; // 清空栈 } function push(value) { this.dataStore[this.top++] = value; } function pop() { this.dataStore[--this.top]; } function peek() { return this.dataStore[this.top - 1]; } function length() { return this.top; } function clear() { this.top = 0; } var stack = new Stack();
push() 压入一个元素后,需要将其保存在 top 所对应的位置,然后 top 加 1,让其指向数组中下一个空位置
top 的位置表示栈顶,也表明了元素个数(相当于数组的length),而 top-1 为栈顶元素
pop() 返回栈顶元素同时将 top 减 1
将 top 设为 0,可轻松清空一个栈
对空栈使用 peek() 返回 undefined, js 数组没有索引越界问题, 如 arr[-12] 不报错,返回 undefined
相关推荐
shenwenjie 2020-09-24
xiesheng 2020-08-02
mingyunxiaohai 2020-07-28
Cypress 2020-07-08
koushr 2020-11-12
zhangxiafll 2020-11-13
kikaylee 2020-10-31
范范 2020-10-28
MILemon 2020-10-22
hugebawu 2020-10-12
LauraRan 2020-09-28
omyrobin 2020-09-23
guangcheng 2020-09-22
qiangde 2020-09-13
hanyujianke 2020-08-18
晨曦之星 2020-08-14
xiesheng 2020-08-06
KAIrving 2020-08-02