数据结构之队列

🎉welcome🎉
??博主介绍：博主大二智能制造在读，热爱C/C++，会不定期更新系统、语法、算法、硬件的相关博客，浅浅期待下一次更新吧！
??算法专栏：算法与数据结构
😘博客制作不易，👍点赞+?收藏+?关注

概念

在现实中，在结账的时候，或者当去餐厅吃饭的时候，人们都是排成了一队，队头的人总是最先出这个队列的(不考虑有人半路直接走)，而当队列中要出现新的人的时候，也是从队尾进去的(不考虑插队这种不道德行为)，这种先进先出的结果在数据结构中也存在，即队列，队列也是一种特殊的线性表，它与栈恰恰相反，队列中的元素是先进先出的，队列在计算机中使用很广泛，cpu在处理任务的时候，就按照任务的先后顺序进行处理。

顺序队列

队列是特殊的线性表，同样也可以使用顺序表或者链表来实现，使用顺序表实现队列，表头当队头，表尾当队尾。

结构体成员

队列所必须的成员只有一个，就是存储数据的指针，但是对于插入数据而言，因为在表尾，每次插入的时候不知道表尾在哪里的候，都需要去找尾，时间复杂度尾O(N)，同样，在获取队列元素个数的时候，同样需要遍历一遍队列，找到尾部，时间复杂度同样是O(N)，这个时候在结构体中存下队列内部元素个数即表尾元素的下一个位置，这个时候可以将这两个操作变成O(1)，同时，队列和栈一样，采用动态申请内存，则还需要一个成员来表示当前队列的最大容量，以方便判断插入时候是否需要扩容。

typedef int QuDataType;

typedef struct queue
{
	QuDataType* data;
	int size;
	int capacity;
}Qu;

初始化、销毁、扩容

与栈相同，队列选择动态申请内存，则在初始化、销毁、扩容逻辑是完全一样的：

//初始化
void QuInit(Qu* Qu)
{
	assert(Qu);

	Qu->data = (QuDataType*)malloc(sizeof(QuDataType) * 4);

	if (Qu->data == NULL)
	{
		perror("malloc");
	}

	Qu->size = 0;
	Qu->capacity = 4;
}

//销毁
void QuDeQuroy(Qu* Qu)
{
	assert(Qu);

	free(Qu->data);
	Qu->data = NULL;
	Qu->size = 0;
	Qu->capacity = 0;
}

//扩容
void Qudilata(Qu* Qu)
{
	assert(Qu);//断言如果为空则说明传过来的数据有问题
	if (Qu->size == Qu->capacity)//当我们存放的元素个数和容器最大容量一样的时候，说明需要扩容
	{
		QuDataType* tmp = (QuDataType*)realloc(Qu->data, sizeof(QuDataType) * Qu->capacity * 2);
		if (tmp == NULL)
		{
			perror("");
			return;
		}
		Qu->data = tmp;//因为realloc开辟的空间的时候可能换到另一个地方
		Qu->capacity *= 2;
	}
}

插入

对于用顺序表的队列而言，插入是在表尾插入，同时，在结构体成员中记录下了表尾的下一个位置，则可以在O(1)的时间进行插入。

void QuPush(Qu* qu, QuDataType x)
{
	assert(qu);

	Qudilata(qu); //扩容函数内部自己检查是否容量已满

	qu->data[qu->size++] = x;//后置++是先使用在++，当插入元素后size才会更新
}

判空

对于队列的而言，结构体成员内部有记录元素个数的size，当size等于0的时候，为空。

bool Quempty(Qu* qu)
{
	assert(qu);

	return qu->size == 0;
}

删除

队列的删除指的是头部元素出队列，这个时候是顺序表的头删，只需要从第二个元素开始，覆盖前一个元素，最后将size–即可。

void Qupop(Qu* qu)
{
	assert(Quempty(qu));

	for (int i = 1; i < qu->size; i++)//从第一个位置开始覆盖掉队头元素
	{
		qu[i] = qu[i - 1];
	}
	qu->size--;
}

获取队列内元素个数

直接返回size即可。

int Qusize(Qu* qu)
{
	assert(qu);

	return qu->size;
}

获取队头元素

队头元素即为表头，即下标0位置元素，在获取元素的时候，要先判断队列是否为空。

QuDataType Qutop(Qu* qu)
{
	assert(QuEmpty(qu));

	return qu->data[0];
}

链式队列

对于链式队列而言，所有的操作都变成了对链表的操作，只是对于链表无需使用容量来记录。

循环队列

在队列中有一种特殊的队列，叫循环队列，循环队列顾名思义，即使队列内部元素变成首尾相连，同时循环队列一定是固定容量的，所以队列是不需要进行扩容操作的，这时候可以使用顺序表，规定好顺序表大小，不需要进行扩容操作，而使用链表的时候，可能有人会觉得首尾相连使用链表实现会更加方便，但是事实是相反的，链表对比顺序表，不仅仅需要扩容，而且当到达最大容量的时候，还需要进行一定的限制，使链表的扩容不能进行下去，同时，对于链表的首尾相连，很多人想到的办法是使尾部指向下一个节点的指针指向头节点，这会导致，你根本无法判断这个链表中有多少个节点，当然，这种也是有解决办法的， 比如在节点中多存放一个bool类型的成员，是尾节点就打上标记，而其他节点的标记与尾节点标记相反，但是这种办法会导致链表所占空间近一步的变大，链表本身就相比较可以容纳同等数据的顺序表要大的多，而这种方法会导致链表的这一劣势变得更加明显，而顺序表实现循环队列是怎么样进行首尾相连的？

顺序表如何实现首尾相连

顺序表实现首尾相连方法在于头指针和尾指针的运用，相比较于平时所认定的顺序表的头指针一直尾指针之前这种思想，在循环队列上就不起作用了，对于循环队列，将其抽象成图像是这样的：

是一个圆形，这种结构，任何元素都可以是头元素，也都可以是尾元素，那就会出现，尾指针指向的位置的地址空间出现在头指针指向的地址空间的前面，那这样如何判断这个队列满了？当头指针等于尾指针的时候，一定使满的吗？当他俩相等的时候也可能是空的，那如何解决这个问题呢？这时候在申请空间的时候，可以多申请一个位置的空间，这个位置是不会存放数据的，而因为循环队列使一个圈，那么在队列满的情况下，尾指针的下一个位置一定会是头指针。

那在插入元素的时候，如何保证所插入的元素时更新指针不会更新出界呢？因为这种方法会使队列在满的时候，尾指针不等于队列的最大容量，这个时候插入元素如果不对其进行一些检查，就会导致出界，访问后面的地址，将元素放到后面的地址上面去，那如何去解决？可以利用取模，对容量进行取模，这样就会保证一直在队列当中插入。

循环队列的实现

这里使用leetcode 622.设计循环队列讲解，题目要求如下：

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

• MyCircularQueue(k): 构造器，设置队列长度为 k 。
• Front: 从队首获取元素。如果队列为空，返回 -1 。
• Rear: 获取队尾元素。如果队列为空，返回 -1 。
• enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
• deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
• isEmpty(): 检查循环队列是否为空。
• isFull(): 检查循环队列是否已满。

实现如下(c++)：

class MyCircularQueue {
public:
  int front;//头指针
  int rear;//尾指针
  int r;//容量
  vector<int> q;//用于存储数据的顺序表
  MyCircularQueue(int k)  //创建一个循环队列
  {
      r = k + 1; //使得可以判断是空还是满
      q = vector<int>(r);
      rear = front =0;
  }

  bool enQueue(int value)  //尾插值
  {
      if((rear + 1) % r == front) return false; //当这个队列满的时候就不能接着进行插入
      q[rear] = value;
      rear = (rear + 1) % r; //更新尾指针到下一个位置，尾指针是出现在最后一个元素后面一个位置的
      return true;
  }

  bool deQueue() //删头部元素
  {
      if(rear == front) return false; //当头指针等于尾指针的时候代表空队列
      front = (front + 1) % r;
      return true;
  }

  int Front() 
  {
      if(rear == front) return -1;
      return q[front];
  }

  int Rear() 
  {
      if(rear == front) return -1;
      return q[(rear - 1 + r) % r];
  }

  bool isEmpty() 
  {
      return rear == front;
  }

  bool isFull()
  {
      return (rear + 1) % r == front;
  }
};

🚀专栏：算法与数据结构
🙉都看到这里了，留下你们的👍点赞+?收藏+📋评论吧🙉