数据结构之队列的实现（一）

2023-06-11 57

版权

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

简介： 在介绍栈之后，这里小编就给大家带来的另外一种特殊的线性结构——队列。

前言

在介绍栈之后，这里小编就给大家带来的另外一种特殊的线性结构——队列。

1.队列的概念

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

2.队列的实现

和栈一样队列也可以用顺序表和链表来实现，但是对队列而言使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。2.1 队列结构的实现

那么为了实现队列我们应该定义什么样的结构呢？首先我们应该是声明出表示队列节点的的结构，这与链表并没有太大差异，其次是我们需要声明出一个队列结构了这里我们的想法是我们需要用一个队头指针和一个队尾指针，分别记录队头和队尾节点，然后就是用一个变量来记录队列的长度。

具体大家可以理解为是如下结构：

那么具体用代码实现是：

1.typedef int QDataType;
//队列节点的结构
typedef struct QListNode
{
  struct QListNode* _pNext;
  QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
 QNode * _front;
 QNode* _rear;
 int size;
}Queue;

2.2 初始化队列

void QueueInit(Queue* q)
{
  assert(q);
  q->_front = q->_rear = NULL;
  q->size = 0;
}

2.3 队尾入队列的实现

void QueuePush(Queue* q, QDataType data)
{
   //节点的创建
  assert(q);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->_pNext = NULL;
  newnode->_data = data;
    //情况一：
  if (q->_front == NULL)
  {
    assert(q->_rear == NULL);
    q->_rear=q->_front = newnode;
  }
    //情况二：
  else
  {
    q->_rear->_pNext = newnode;
    q->_rear = newnode;
  }
  q->size++;
}

在入队列前，我们首先需要的是创建一个节点，这里我们需要注意的是将新建节点的的_pNext指针赋值NULL，把需要插入的内容赋值给新建节点存储数据内容的类型。

对于入队列的情况这里有两种情况我们需要考虑一下

情况一：当队列的队头指针和队列的队尾指针都指向NULL时，此时这里插入的一个节点即是队头节点，也是队尾节点

情况二：这种也就是一般情况，这里我们插入一个节点，只需要我们把队尾元素的pNext指针指向新插入的节点，那么这个新插入的节点也就是新的尾节点，所以我们这个时候就需要把队尾指针指向新的队尾节点。示例图如下

在添加元素后记得给统计栈元素的个数的数量+1。

2.4 判断队列是否为空

1. bool QueueEmpty(Queue* q)
2. {
3.  assert(q);
4.  return q->size == 0;
5. }

这里的判断方式和栈是否为空的方式一致，这里我就不再讲解，不懂得话大家可以去小编与栈有关介绍的文章进行查看。

2.5 队头出队列

void QueuePop(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  if (q->_front == q->_rear)
  {
  free(q->_front);
  q->_front = NULL;
  q->_rear == NULL;
  }
  else
  {
  QNode* next = q->_front->_pNext;
  free(q->_front);
  q->_front = next;
  }
  q->size--;
}