首页 > web前端 > js教程 > 正文

js数据结构和算法之栈和队列详解

小云云
发布: 2018-03-17 12:01:58
原创
1477人浏览过


1.定义

栈是一种重要的线性结构。栈(stack)是一个后进先出(last in first out,lifo)的线性表,它要求只在表尾进行删除和插入操作。对于栈来说,这个表尾称为栈的栈顶,相应的表头称为栈底。

栈的操作只能在这个线性表的表尾进行:
     栈的插入操作(Push),叫做进栈,也称为压栈,入栈。

     栈的删除操作(Pop),叫做出栈,也称为弹栈。

2.栈的顺序存储结构

因为栈的本质是一个线性表,线性表有两种存储形式,那么栈也有分为栈的顺序存储结构和栈的链式存储结构

顺序存储结构:是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。

例如我们编程语言的数组结构就是这样滴。

360截图20180317120118827.jpg

链式存储结构:是把数据元素存放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的。

很显然,这样说的话链式存储结构的数据元素存储关系并不能反映其逻辑关系,因此需要用一个指针存放数据元素的地址,这样子通过地址就可以找到相关联数据元素的位置。

360截图20180317120131785.jpg

最开始栈中不含有任何数据,叫做空栈,此时栈顶就是栈底。然后数据从栈顶进入,栈顶栈底分离,整个栈的当前容量变大。数据出栈时从栈顶弹出,栈顶下移,整个栈的当前容量变小。

360截图20180317120147169.jpg

3.栈操作

(1).基本操作

/** * 
 * 栈的构造函数 
 * */ 
function Stack() { 
 	// 用数组来模拟栈 
	this.dataStore = []; //底层数据结构是数组
	this.top = 0; //top应该是等于数组的length的
}
//栈需要有如下的方法
Stack.prototype = {
	/**
	 * 1. push()
	 * 向栈中压入一个新元素, 需要将其保存在数组中变量 top 所对
	 * 应的位置, 然后将 top 值加 1, 让top指向数组中下一个空位置
	 * 特别注意 ++ 操作符的位置, 它放在 this.top 的后面, 这样新入栈的元素就被放在
	 * top 的当前值对应的位置, 然后再将变量 top 的值加 1, 指向下一个位置
	 * */
	push:function(element){
		this.dataStore[this.top++] = element;
	},
	/**
	 * pop() 方法恰好与 push() 方法相反——它返回栈顶元素, 同时将变量 top 的值减 1
	 * 也可以改造一下,只--this.top,不返回栈顶元素
	 * */
	pop:function(){
		return this.dataStore[--this.top];
	},
	/**
	 * peek() 方法返回数组的第 top-1 个位置的元素, 即栈顶元素
	 * */
	peek:function(){
		return this.dataStore[this.top-1];
	},
	length:function(){
		return this.top;
	},
	clear:function(){
		 this.top = 0;
	}
};
//测试 Stack 类的实现
var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
console.log("length: " + s.length());//length: 3
console.log(s.peek());//Bryan
var popped = s.pop();
console.log("The popped element is: " + popped);//The popped element is: Bryan
s.push("Cynthia");
s.clear();
console.log("length: " + s.length());//length: 0
登录后复制

相关推荐:

PHP基于数组实现的堆栈和队列功能实例分享

以上就是js数据结构和算法之栈和队列详解的详细内容,更多请关注php中文网其它相关文章!

最佳 Windows 性能的顶级免费优化软件
最佳 Windows 性能的顶级免费优化软件

每个人都需要一台速度更快、更稳定的 PC。随着时间的推移,垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是,许多工具可以让 Windows 保持平稳运行。

下载
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
作者最新文章
最新问题
开源免费商场系统广告
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号