用STL库中的vector/deque/list模拟实现stack

2017-04-14 14:51 阅读 964 次 评论 0 条

stack是一种先进后出(FIFO)的数据结构,它只有一个出口。也就意味着它只能新增元素,移除栈顶元素,除此之外,没有任何方法去改变栈中的任何元素。

stack的特性

stack是一种后进先出的数据结构,这也就限制了stack是不能遍历的,也就意味着我们压栈只能从尾部插入数据,出栈也只能从尾部删除数据。

由于stack系以底部容器完成其所有工作,而具有这种"修改某物接口"的性质称之为adapter(配接器),因此,STL重点stack往往不被归类为container(容器),而被归类为container adapter

除此之外,stack是没有迭代器的,stack所有的元素进出都必须完全符合"先进后出"的条件,只有stack顶部的元素才有机会被外界使用,stack不提供走访功能,也不提供迭代器。

vector实现stack

vector是连续存储结构,每个元素在内存上是连续的;支持高效的随机访问和在尾端插入/删除操作,但其他位置的插入/删除操作效率低下;

deque实现stack

deque是双向开口的数据结构,若以deque为底部结构并封装其头部开口,便轻而易举地形成了一个stack。因此,SGI STL便以deque作为缺省情况下的stack底部结构。

list实现stack

除了deque双向队列之外,list也是双向开口的数据结构,list具备所有stack的功能,若以list为底部结构并封装其头部开口,一样能很轻松实现一个stack。

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:用STL库中的vector/deque/list模拟实现stack | 术与道的分享
分类:编程素养 标签:,
1024do.com导航_术与道导航平台

发表评论


表情