数据结构-队列

2024-03-04 32

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构-队列

1.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头.

2.队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

2.1定义队列

多个值我们使用两个结构体来封装，方便找头和尾。

typedef int QDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Que;

2.2初始化队列

void QueueInit(Que* pq)
{
  assert(pq);
  pq->size = 0;
  pq->head = pq->tail = NULL;
}

2.3销毁队列

销毁队列需要遍历，并且需要提前保存下一个节点的地址。

void QueueDestroy(Que* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
  QNode* next = cur->next;
  free(cur);
  cur = next;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
}

2.3数据入队列

首先为新节点malloc一块空间，将data赋值，然后将此节点的next置空。开始入对列，这时需要注意，如果队列为空，则此节点就同时是头和尾，如果不为空，则链接在tail的后面，在将新节点置为tail，最后size++。

void QueuePush(Que* pq, QDataType x)
{
  assert(pq);
  QNode* tmp = (QNode*)malloc(sizeof(QNode));
  if (tmp == NULL)
  {
  perror("malloc fail");
  exit(-1);
  }
  tmp->data = x;
  tmp->next = NULL;
  if (pq->tail == NULL)
  {
  pq->head = pq->tail = tmp;
  }
  else
  {
  pq->tail->next = tmp;
  pq->tail = tmp;
  }
  pq->size++;
}

2.4数据出队列

队列是先入先出，所以数据是从头节点出去，使用断言此队列不为空，在判断是不是只有一个节点，如果是就直接free掉这个节点即可，再将tai和head置空。如果不止一个节点，则需要保存第二个节点，free掉head，再将head置为下一个节点，最后size--。

void QueuePop(Que* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->head->next == NULL)
  {
  free(pq->head);
  pq->head = pq->tail = NULL;
  }
  else
  {
  QNode* next = pq->head->next;
  free(pq->head);
  pq->head = next;
  }
  pq->size--;
}

2.5取队列的头部数据

直接返回head的data即可。

QDataType QueueFront(Que* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}

2.6取队列的尾部数据

返回tail的data即可。

QDataType QueueBack(Que* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}

2.7判断队列是否为空

使用bool的返回值。

bool QueueEmpty(Que* pq)
{
  assert(pq);
  return pq->head == NULL;
}

2.8队列的数据个数

返回size即可。

int QueueSize(Que* pq)
{
  assert(pq);
  return pq->size;
}

今天的分享到这里就结束啦！谢谢老铁们的阅读，让我们下期再见。