深入理解栈和队列(二):队列

简介: 深入理解栈和队列(二):队列

个人主页:17_Kevin-CSDN博客

专栏:《数据结构》


一、队列的概念和结构

队列是只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出

FIFO(First In First Out)

入队列:进行插入操作的一端称为队尾

出队列:进行删除操作的一端称为队头

二、队列的操作

队列有以下几种常见的操作:

  • 入队(Enqueue):将一个元素添加到队尾。
  • 出队(Dequeue):从队头删除并返回一个元素。
  • 查看队头元素(Front):返回队头元素,但不删除它。
  • 查看队尾元素(Rear):返回队尾元素,但不删除它。
  • 判断队列是否为空(Empty):返回队列是否为空。
  • 清空队列(Clear):删除队列中的所有元素。

三、队列的实现

1. 实现方法的选择

队列可以使用多种数据结构来实现,如数组、链表等。

但是用链表实现队列效果更优,因为如果是数组的话,队列每次需要从头上出数据,这样就需要将数组后面的数据依次往前挪动,这样会增加时间复杂度,不如使用链表直接free掉队头数据快捷。

2. 代码实现

2.0 创建队列结构

typedef int QDataType;
 
typedef struct QueueNode
{
  int val;
  struct QueueNode* next;
}QNode;
 
 
typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;

创建一个结构体类型QNode来作为队列中每个节点的数据存储结构体,用Queue作为存储队头和队尾还有队列长度的结构体类型。

2.1 初始化队列

void QueueInit(Queue* pq)
{
  assert(pq);
 
  pq->phead = NULL;
  pq->ptail = NULL;
  pq->size = 0;
}

和链表的初始化大同小异。

2.2 队列的销毁

void QueueDestroy(Queue* pq)
{
  assert(pq);
 
  QNode* cur = pq->phead;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
 
    cur = next;
  }
 
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}

首先检查传入的pq队列是不是已经没有数据了,然后创建一个Queue类型的变量cur和next用来遍历销毁队列。在循环中用next来指向cur的下一个数据,然后free掉现在cur的数据,持续推动向前,一个接一个销毁。

while (cur) 循环结束后,cur 确实已经被设置为 NULL,但是将队列的头指针和尾指针都设置为 NULL 是为了确保队列的状态被正确地重置为空闲状态。

即使 cur 已经是 NULL,队列的其他成员变量(如 size)仍然可能包含不正确的值。通过将头指针和尾指针都设置为 NULL,可以确保队列被完全清空,并避免任何潜在的错误或未初始化的状态。

2.3 入队列

// 入队列
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
 
  newnode->val = x;
  newnode->next = NULL;
 
  if (pq->ptail)
  {
    pq->ptail->next = newnode;//将当前尾的next设置为newnode
    pq->ptail = newnode;//更新pq的尾节点,所以当前尾节点为newnode
  }
  else
  {
    pq->phead = pq->ptail = newnode;
  }
 
  pq->size++;
}

在创建空间并分配后,根据队列的当前状态进行不同的操作。如果队列的尾指针 pq->ptail 不为 NULL,则将 newnode 插入到队列的尾部。首先,将 pq->ptail->next 设置为 newnode,将 newnode 连接到队列的尾部。然后,将 pq->ptail 更新为 newnode,以便后续的操作可以正确地找到队列的尾部。如果队列的尾指针为 NULL,表示队列为空,此时将 newnode 设置为队列的头指针和尾指针,即 pq->phead = pq->ptail = newnode

2.4 出队列

// 出队列
void QueuePop(Queue* pq)
{
  assert(pq);
 
  // 0个节点
  // 温柔检查
  //if (pq->phead == NULL)
  //  return;
 
  // 暴力检查 
  assert(pq->phead != NULL);
 
  // 一个节点
  // 多个节点
  if (pq->phead->next == NULL)
  {
    free(pq->phead);
    pq->phead = pq->ptail = NULL;
  }
  else
  {
    QNode* next = pq->phead->next;
    free(pq->phead);
    pq->phead = next;
  }
 
  pq->size--;
}

2.5 返回队头数据

QDataType QueueFront(Queue* pq)
{
  assert(pq);
 
  // 暴力检查 
  assert(pq->phead != NULL);
 
  return pq->phead->val;
}

2.6 返回队尾数据

QDataType QueueBack(Queue* pq)
{
  assert(pq);
 
  // 暴力检查 
  assert(pq->ptail != NULL);
 
  return pq->ptail->val;
}

四、队列的应用场景

队列在计算机科学中有许多应用场景,以下是一些常见的例子:消息队列:在分布式系统中,消息队列用于在不同的进程或节点之间传递消息。

  • 任务队列:在操作系统中,任务队列用于调度和执行任务。
  • 缓冲区:在输入输出操作中,队列可以用作缓冲区,暂存输入数据或输出数据。
  • 优先队列:优先队列是一种特殊的队列,其中元素按照某种优先级排序。在搜索引擎中,优先队列可以用于对搜索结果进行排序。

I'm Kevin, and we'll see you next time


目录
相关文章
|
1天前
|
前端开发 JavaScript 算法
JavaScript 中实现常见数据结构:栈、队列与树
JavaScript 中实现常见数据结构:栈、队列与树
|
3天前
|
存储 编译器 C语言
数据结构——顺序队列与链式队列的实现-2
数据结构——顺序队列与链式队列的实现
数据结构——顺序队列与链式队列的实现-2
|
3天前
|
存储 C语言
数据结构——顺序队列与链式队列的实现-1
数据结构——顺序队列与链式队列的实现
数据结构——顺序队列与链式队列的实现-1
|
3天前
|
存储 NoSQL C语言
数据结构——顺序栈与链式栈的实现-2
数据结构——顺序栈与链式栈的实现
数据结构——顺序栈与链式栈的实现-2
|
3天前
|
存储 C语言
数据结构——顺序栈与链式栈的实现-1
数据结构——顺序栈与链式栈的实现
数据结构——顺序栈与链式栈的实现-1
|
3天前
栈的基本应用
栈的基本应用
12 3
|
3天前
栈与队列理解
栈与队列理解
13 1
|
3天前
|
存储 算法
数据结构与算法 栈与队列
数据结构与算法 栈与队列
12 0
数据结构与算法 栈与队列
|
3天前
|
C++
数据结构(顺序队列 循环队列
数据结构(顺序队列 循环队列
10 0
|
3天前
|
C++
数据结构(共享栈
数据结构(共享栈
9 0