栈的JS实现

栈，是一种特殊的线性表，其插入及删除的操作都在线性表的同一端进行。这一端称为栈顶，另一端称为栈底。就类似于餐厅里的一摞盘子，后放的盘子在上方，也会先被人拿走。栈具有“后进先出”的逻辑特性。栈在计算机科学中有着广泛的应用，递归函数的实现就利用了栈这种数据结构，在递归时，计算机会维护一个递归工作栈，当一个递归函数被调用时，被调函数的局部变量、形参的值以及一个返回地址就会储存在递归工作栈中。运行时按照后进先出的顺序，进行函数执行，完成递归操作。编译原理中也多次使用栈这种数据结构~

栈是一种特殊的线性表，故其在存储结构上也有链式存储和顺序存储两种。代码如下：

/*链栈的JS实现*/

function LinkedStack(){

        //节点结构定义

        var Node = function(element){

		this.element = element;

		this.next = null;

	}

	var length = 0,

		top; //栈顶指针

	//压栈操作

	this.push = function(element){

		var node = new Node(element),

			current;

		if(!top){

			top = node;

			length++;

			return true;

		}else{

			node.next = top;

			top = node;

			length++;

			return true;

		}

	}

        //退栈操作

	this.pop = function(){

		var current = top;

		if(top){

			top = current.next;

			current.next = null;

			length--;

			return current;

		}else{

			return 'null stack';

		}

	}

        //获取栈顶节点

	this.top = function(){

		return top;

	}

        //获取栈长

	this.size = function(){

		return length;

	}

	this.toString = function(){

		var string = '',

			current = top;

		while(current){

			string += current.element;

			current = current.next;

		}

		return string;

	}

        //清空栈

	this.clear = function(){

		top = null;

		length = 0;

		return true;

	}

}

//顺序栈的JS实现 这里直接使用了JS内置的Array对象

function ArrayStack(){

	var arr = [];

        //压栈操作

	this.push = function(element){

		arr.push(element);

	}

        //退栈操作

	this.pop = function(){

		return arr.pop();

	}

        //获取栈顶元素

	this.top = function(){

		return arr[arr.length-1];

	}

        //获取栈长

	this.size = function(){

		return arr.length;

	}

        //清空栈

	this.clear = function(){

		arr = [];

		return true;

	}

	this.toString = function(){

		return arr.toString();

	}

}

巴特西

栈的JS实现

最新文章

热门文章