对于循环队列与链队列的比较,可以从两方面来考虑:
- 从时间上,其实它们的基本操作都是常数时间,即都为0(1)的,不过循环队列是事先申请好空间,使用期间不释放,而对于链队列,每次申请和释放结点也会存在一些时间开销,如果入队出队频繁,则两者还是有细微差异。
- 对于空间上来说,循环队列必须有一个固定的长度,所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题,尽管它需要一个指针域,会产生一些空间上的开销,但也可以接受。所以在空间上,链队列更加灵活。
-
总的来说,在可以确定队列长度最大值的情况下,建议用循环队列,如果你无法预估队列的长度时,则用链队列。
用数组实现队列时,如果不移动,随着数据的不断读写,会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组,只是它在逻辑上把数组的头和尾相连,形成循环队列,当数组尾满的时候,要判断数组头是否为空,不为空继续存放数据,可以有效的利用资源。但是用循环队列有个小麻烦,不好判断数列是为空还是为满;
链队列就不存在上面的问题。“循环队列”最大优点就是节省空间和少分配空间,而链队列多了一点点地址存储开销。
延伸阅读
此文章所在专题列表如下:
- 栈的定义与大概理解
- 栈的抽象数据类型ADT
- 顺序栈:栈的顺序存储结构
- 顺序栈的进栈操作
- 顺序栈的出栈操作
- 获取顺序栈的栈顶元素
- 链栈:栈的链式存储结构
- 链栈的进栈操作
- 链栈的初始化与遍历
- 链栈的出栈操作
- 链栈的置空操作与判断链栈是否为空
- 为什么要使用栈这种数据结构
- 递归,栈的重要应用之一
- 栈是如何实现递归的
- 接触后缀表达式(逆波兰表示法)
- 图解后缀表达式的计算过程
- 将中缀表达式转化为后缀表达式
- 开始学习队列这个数据结构
- 队列的抽象数据类型ADT
- 顺序队列:队列的顺序存储结构
- 顺序队列的入队操作
- 顺序队列的出队操作
- 顺序队列置空与判断操作
- 队列顺序存储结构的不足
- 关于循环队列的一些讲解
- 链队列:队列的链式存储结构
- 链队列的初始化操作
- 链队列的入队操作
- 链队列的出队操作
- 补完链队列的其它常见操作
- 循环队列与链队列的优劣势
本文地址:http://www.nowamagic.net/librarys/veda/detail/2364,欢迎访问原出处。