当前位置:   article > 正文

数据结构与算法详解——队列篇(附c++实现代码)_数据结构队列代码

数据结构队列代码

队列的概念

  队列的概念比较好理解,和我们现实中的排队比较相似,先进先出。栈和队列有点相似,栈有入栈出栈两种基本操作,队列相对应也有入队出队两种基本操作,不过栈只能从栈顶入,从栈顶出;而队列从队尾入,从队头出,所以队列也是一种操作受限的线性表。

队列的实现

顺序队列与链式队列

  和栈一样,用数组实现的队列叫顺序队列,用链表实现的队列叫链式队列
  前面说了,队列从队尾入,从队头出,因此我们需要维护队头head和队尾tail,顺序队列的入队和出队的代码大致是:

template<typename T>
void enqueue(T data){
   
	if(tail==capacity)	//队列已经满了,无法再入队
		throw "queue is full";
	array[tail]=data;
	++tail;
}

template<typename T>
T dequeue(){
   
	if(head==tail)		//队列已经空了,无法出队
		throw "queue is empty\n";
	T ret=array[head];
	++head;
	return ret;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

  这样子会有一个问题:head和tail都是不断变大的,随着若干次入队和出队,tail达到了数组的尾端也就是tail==capacity,而head可能在数组的中间位置,这时候队列的元素在[head,tail]上,数组[0,head)的空间却闲置了,但是此时无法入队。
在这里插入图片描述

  针对这个问题,我们可以在入队时当tail==capacity时也判断head!=0,都成立的话做一次数据的前移,将[head,tail]上的元素移到[0,tail-head]上,就可以将空间腾出来,这里就不展示完整代码了。
  链式队列的话就不需要考虑移数据或者动态扩容的问题,同样也是维护head和tail指针,入队出队的伪代码:

template<typename T>
void enqueue(T data){
   
	if(tail == nullptr)
		tail = new Node(data);
	else
  • 1
  • 2
  • 3
  • 4
  • 5
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家小花儿/article/detail/590117
推荐阅读
相关标签
  

闽ICP备14008679号