温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

JavaScript链表如何实现栈和队列

发布时间:2022-03-19 10:47:41 来源:亿速云 阅读:218 作者:iii 栏目:大数据

这篇文章主要介绍了JavaScript链表如何实现栈和队列的相关知识,内容详细易懂,操作简单快捷,具有一定借鉴价值,相信大家阅读完这篇JavaScript链表如何实现栈和队列文章都会有所收获,下面我们一起来看看吧。

链表的时间复杂度 如下:

接口说明复杂度
add(index, e)插入操作O(n)
remove(index, e)删除操作O(n)
set(index, e)修改操作O(n)
get(index, e)查找操作O(n)
contains(index, e)也是查找操作O(n)

这似乎说明 链表 是一个性能不太优的数据结构,我们来对链表的接口进行一些调整,然后在看一下 时间复杂度

JavaScript链表如何实现栈和队列

接口说明复杂度
addFirst(index, e)插入表头操作O(1)
addLase(index, e)插入链尾操作O(1)
removeFirst(index, e)删除表头操作O(1)
removeLast(index, e)删除链尾操作O(1)
getFirst(index, e)查找链表头操作O(1)

经过添加这些接口,链表的在使用时复杂度就变成了O(1)。

链表实现栈

JavaScript链表如何实现栈和队列

JavaScript链表如何实现栈和队列

链表实现队列

根据队列的性质,对于队列的操作势必会影响到链表的两端,根据前文的表格可以知道一端为O(1),另外一端为O(n)。

JavaScript链表如何实现栈和队列


为什么在链表中链表头的操作会简单为O(1) 呢,根据上图可以看出,因为有了一个标识位 head ,因此可以很快的定位的表头,同样的我们可以设置一个tail变量,这样对于两端插入元素都是很容易。

这样队列从head端删除元素,从tail端插入元素。

head 队首负责出队,tail队尾负责入队。

JavaScript链表如何实现栈和队列

关于“JavaScript链表如何实现栈和队列”这篇文章的内容就介绍到这里,感谢各位的阅读!相信大家对“JavaScript链表如何实现栈和队列”知识都有一定的了解,大家如果还想学习更多知识,欢迎关注亿速云行业资讯频道。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI