数据结构（初阶）—— 队列-阿里云开发者社区

数据结构（初阶）—— 队列

2022-11-24 90

版权

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

简介： 数据结构（初阶）—— 队列

一、队列的概念和结构

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

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。（一般如果采用顺序栈，常设计成循环队列的形式，这个放到下一期博客说）

数组实现队列：

链表实现队列：

二、链式结构表示队列

用链式结构表示队列，我们需要两个指针，一个控制队尾，一个控制队头，方便数据入队和出队；如果不控制队尾，那么在入数据的时候，我们就需要先去找到队尾（即链表的尾），这就很麻烦；

typedef int QDataType;
//链表的结构
typedef struct QueueNode
{
  QDataType data;
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
    //都是链表的指针，head和tail都可以去访问链表，在处理入队和出队上就很方便了
  QNode* head;//队头
  QNode* tail;//队尾
}Queue;

三、队列各个接口函数的实现

1.队列的初始化

//队列的初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
}

2.队尾入队列（尾插）

队列相当于在单链表的基础上加了一些限制，并且多了头尾指针的控制，在进行尾插的时候相比单链表快了很多，单链需要循环判断找尾，而队列可以直接找到尾；

如果单链表还不太清楚的同学可以复习一下：https://blog.csdn.net/sjsjnsjnn/article/details/123920224?spm=1001.2014.3001.5501

//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  newnode->data = x;
  newnode->next = NULL;
  if (pq->head == NULL)
  {
        //第一个元素入队
    pq->head = pq->tail = newnode;
  }
  else
  {
        //数据队尾入
    pq->tail->next = newnode;
        //tail控制队尾（记住新的尾）
    pq->tail = newnode;
  }
}

3.队头出队列（头删）

在头删的时候要注意，当头删删到队尾时候，此时head和tail指向的同一块空间，要记得把tail也要释放了；

//队头出队列
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  QNode* next = pq->head->next;
  free(pq->head);
  pq->head = next;
  //此时head和tail同时指向最后一个空间，释放head后，要注意也要把tail释放了
  if (pq->head == NULL)
  {
    pq->tail = NULL;
  }
}

4.取队头的数据

//取队头的数据
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));//判断队列是否为空
  return pq->head->data;//直接返回头指针所指向的数据
}

5.取队尾的数据

//取队尾的数据
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));//判断队列是否为空
  return pq->tail->data;//直接返回尾指针所指向的数据
}

6.计算队列的数据个数

//计算队列的数据个数
int QueueSize(Queue* pq)
{
  assert(pq);
  int n = 0;
  QNode* cur = pq->head;
  while (cur)
  {
    ++n;
    cur = cur->next;
  }
  return n;
}

7.判断队列是否为空

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}

四、源代码

Queue.h

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
  QDataType data;
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;
}Queue;
//队列的初始化
void QueueInit(Queue* pq);
//队列的销毁
void QueueDestroy(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QDataType x);
//队头出队列
void QueuePop(Queue* pq);
//取队头的数据
QDataType QueueFront(Queue* pq);
//取队尾的数据
QDataType QueueBack(Queue* pq);
//计算队列的数据个数
int QueueSize(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);

Queue.c

#include "Queue.h"
//队列的初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
}
//队列的销毁
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}
//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  newnode->data = x;
  newnode->next = NULL;
  if (pq->head == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}
//队头出队列
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  QNode* next = pq->head->next;
  free(pq->head);
  pq->head = next;
  //此时head和tail同时指向最后一个空间，释放head后，要注意也要把tail释放了
  if (pq->head == NULL)
  {
    pq->tail = NULL;
  }
}
//取队头的数据
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
//取队尾的数据
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
//计算队列的数据个数
int QueueSize(Queue* pq)
{
  assert(pq);
  int n = 0;
  QNode* cur = pq->head;
  while (cur)
  {
    ++n;
    cur = cur->next;
  }
  return n;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}

Test.c

#include "Queue.h"
void QueueTest1()
{
  Queue q;
  QueueInit(&q);
  //数据入队
  QueuePush(&q, 1);
  QueuePush(&q, 2);
  QueuePush(&q, 3);
  QueuePush(&q, 4);
  QueuePush(&q, 5);
  QueuePush(&q, 6);
  QueuePush(&q, 7);
  QueuePush(&q, 8);
  //1 2 3 出队列
  //QueuePop(&q);
  //QueuePop(&q);
  //QueuePop(&q);
  while (!QueueEmpty(&q))
  {
    QDataType front = QueueFront(&q);
    printf("%d ", front);
    QueuePop(&q);
  }
  QueueDestroy(&q);
}
int main()
{
  QueueTest1();
  return 0;
}