数据结构第四课 -----线性表之队列

简介: 数据结构第四课 -----线性表之队列

队列的定义

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

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

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


就相当于我们现实的排队一样

队列的实现方法:

1.数组队列

2. 链表队列

双向链表

两边没有太多规定

单向链表

下面我就用单链表来演示下

队列的设计

队列的结构

typedef int QDataType;
typedef struct QueueNode
{
  QDataType val;
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* head;
  QNode* tail;//尾节点和队尾
  int size;
} Queue;


这里有两个结构体,一个是链表节点的结构体,一个是队列的结构,这样设计可以在计算队列长度时的时间复杂度变成O(1),还要方便传参时不用频繁调用二级指针

初始化

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


插入(入队)

//插入
void QueuePush(Queue* pq, QDataType elemest)
{
  //创建节点
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc");
    return;
  }
  newnode->next = NULL;
  newnode->val = elemest;
  if (pq->tail == NULL)
  {
    pq->head = newnode;
    pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
  pq->size++;
}

我们这里是没有使用哨兵位,所以要判断head为空的情况下

删除(出队)

//删除
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  if (pq->head == pq->tail)
  {
    free(pq->head);
    pq->tail = NULL;
    pq->head = NULL;
  }
  else
  {
    QNode* node = pq->head;
    pq->head = pq->head->next;
    free(node);
  }
  pq->size--;

}

使用这种思路我们要注意head不能为空,还有就是只有一个节点的时候

一旦freel(head),tail就成了野指针了

队头

//队头
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->head->val;
}

队尾

//队尾
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->tail->val;
}


判断队列是否为空

//是否为空
bool QueueEmtry(Queue* pq)
{
  assert(pq);
  return pq->size == 0;
}

队列的长度

//长度
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}

释放

//释放
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* node = pq->head;
  while (node)
  {
    QNode* node1 = node;
    node = node->next;
    free(node1);
  }
  pq->tail = NULL;
  pq->size = 0;

}

总结

队列的大概简单的设计,如果想要设计数组队列可以去尝试一下

相关文章
|
27天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
123 9
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
初步认识栈和队列
初步认识栈和队列
61 10
|
2月前
|
存储 Java
数据结构第二篇【关于java线性表(顺序表)的基本操作】
数据结构第二篇【关于java线性表(顺序表)的基本操作】
33 6
|
2月前
|
存储 算法 定位技术
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
这篇文章主要介绍了稀疏数组和队列的概念、应用实例以及如何使用数组模拟队列和环形队列的实现方法。
23 0
数据结构与算法学习二、稀疏数组与队列,数组模拟队列,模拟环形队列
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索栈和队列的无尽秘密
【用Java学习数据结构系列】探索栈和队列的无尽秘密
32 2
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
17 0
|
2月前
探索数据结构:队列的的实现与应用
探索数据结构:队列的的实现与应用
|
2月前
|
存储 C语言
栈和队列题目练习
栈和队列题目练习
19 0