这篇文章主要介绍了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) |
这似乎说明 链表 是一个性能不太优的数据结构,我们来对链表的接口进行一些调整,然后在看一下 时间复杂度 。
接口 | 说明 | 复杂度 |
---|---|---|
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)。
根据队列的性质,对于队列的操作势必会影响到链表的两端,根据前文的表格可以知道一端为O(1),另外一端为O(n)。
为什么在链表中链表头的操作会简单为O(1) 呢,根据上图可以看出,因为有了一个标识位 head
,因此可以很快的定位的表头,同样的我们可以设置一个tail
变量,这样对于两端插入元素都是很容易。
这样队列从head
端删除元素,从tail
端插入元素。
head
队首负责出队,tail
队尾负责入队。
关于“JavaScript链表如何实现栈和队列”这篇文章的内容就介绍到这里,感谢各位的阅读!相信大家对“JavaScript链表如何实现栈和队列”知识都有一定的了解,大家如果还想学习更多知识,欢迎关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。