如果让你手写个栈和队列,你还会写吗?

阅读本文大概需要6分钟

昨天跟一个CSDN上的朋友聊天,他说现在如果让他自己手写一个栈或者队列,估计都要写蛮久的,平时虽然都在用,但是都是别人封装好的集合。

确实,经典的数据结构,包括排序算法,虽然我们平时不用手写了,但是这些内功,作为开发人员来说是必须要掌握的。受此启发,我打算更一下经典数据结构和算法的系列文章。今天先从栈和队列说起。

这些东西,挤地铁时,吃饭排队时,等公交时,可以拿来看看,或者,就把它当作个下午茶吧~

我们知道,在数组中,若知道数据项的下标,便可立即访问该数据项,或者通过顺序搜索数据项,访问到数组中的各个数据项。但是栈和队列不同,它们的访问是受限制的,即在特定时刻只有一个数据项可以被读取或者被删除。众所周知,栈是先进后出,只能访问栈顶的数据,队列是先进先出,只能访问头部数据。这里不再赘述。

栈的主要机制可以用数组来实现,也可以用链表来实现,下面用数组来实现栈的基本操作:

数据项入栈和出栈的时间复杂度均为O(1)。这也就是说,栈操作所消耗的时间不依赖于栈中数据项的个数,因此操作时间很短。栈不需要比较和移动操作。

队列也可以用数组来实现,不过这里有个问题,当数组下标满了后就不能再添加了,但是数组前面由于已经删除队列头的数据了,导致空。所以队列我们可以用循环数组来实现,见下面的代码:

和栈一样,队列中插入数据项和删除数据项的时间复杂度均为O(1)。

还有个优先级队列,优先级队列是比栈和队列更专用的数据结构。优先级队列与上面普通的队列相比,主要区别在于队列中的元素是有序的,关键字最小(或者最大)的数据项总在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。

这里实现的优先级队列中,插入操作需要 O(N) 的时间,而删除操作则需要 O(1) 的时间。

●编号785,输入编号直达本文

●输入m获取文章目录

推荐↓↓↓

人工智能与大数据技术

更多推荐《25个技术类公众微信》

涵盖:程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181109B0FLRQ00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券