&web_id=" language="JavaScript">
Fork me on GitHub

JavaScript 栈

什么是栈

堆栈(英语:stack),也可直接称栈(港澳台作堆叠),在计算机科学中,是一种特殊的串列形式的数据结构,它的特殊之处在于只能允许在链接串列或阵列的一端(称为堆叠顶端指标,英语:top)进行加入数据(英语:push)和输出数据(英语:pop)的运算。另外栈也可以用一维数组或连结串列的形式来完成。堆叠的另外一个相对的操作方式称为伫列。

由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First Out)的原理运作。

堆叠数据结构使用两种基本操作:推入(push)和弹出(pop):
推入:将数据放入堆叠的顶端(阵列形式或串列形式),堆叠顶端top指标加一。
弹出:将顶端数据资料输出(回传),堆叠顶端资料减一。

用JavaScript实现栈的数据结构

接下来我们就要使用JavaScript实现栈的数据结构,包含数据的推入和推出。

首先我们定义一个栈

1
2
3
4
5
6
7
8
function Stack(){
this.data = [];
this.top = 0; //记录栈顶位置
this.pop = pop; //右推出
this.push = push; //右进入
this.display = display;
this.length = length; //计算数组长度
}

注意,top是用来记录栈顶位置,初始化为0,我们使用 push() 函数和 pop()函数来实现。

1
2
3
4
5
6
7
8
9
function push(element){
this.data[this.top] = element;
this.top++;
}
function pop(){
var lastElement = this.data[this.top-1];
this.top--;
return lastElement;
}

length()函数和display()函数是用来显示栈长度和显示栈内元素的,下面展示函数的实现。

1
2
3
4
5
6
7
8
9
function length(){
return this.top;
}
function display(){
var length = this.top;
for(var i=0;i<length;i++){
console.log(this.data[i]);
}
}

今天讲的东西都十分基础,是为了接下来中缀表达式和后缀表达式实现打下基础,接下来的一篇博客中将详解中缀表达式的计算过程。

Godlike Meteor wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
我知道不会有人点开,但万一真有人想不开呢?
------ 本文结束 ------