栈是一种高效的数据结构,数据只能在栈顶添加或删除,所以这样操作很快,也很容易实现。栈的使用遍布程序语言实现的方方面面,从表达式求值到处理函数调用。接下来,用JavaScript实现一个栈的数据结构。
定义栈的操作栈作为一种特殊的列表,只能从一端来进行访问,就像一摞盘子,放只能放在上面,拿也只能从上面拿,所以栈是一种先入后出的一种数据结构。因为栈的这种特点,栈中任意不在栈顶的元素都无法访问,为了得到栈底的元素,必须把该元素之上的元素拿掉,把栈底的元素暴露在栈顶。栈还可以清空其内所有元素,也可以记录栈内元素的个数。
综上,我们定义几个操作栈的方法。
push() 把元素添加到栈顶
pop() 把元素从栈顶删除
peek() 返回栈顶的元素
clear() 清空栈内元素
length() 栈内元素的个数
栈的实现
实现栈,底层的数据结构采用数组,以定义栈的构造函数开始;
function Stack() { this.dataStore = []; //用来保存栈内元素的数组 this.top = 0; //top用来记录栈顶位置,初始化为0 this.push = push; this.pop = pop; this.peek = peek; this.clear = clear; this.length = length; }