一看就懂之与栈结构(FILO)相对的——队列结构(FLFO)

简介: 一、什么是队列,什么是FIFO​ 队列允许在一端进行插入操作,在另一端进行删除操作的线性表,队列是与栈相对的一个数据结构,栈的特点是先进后出,而队列的特点是先进先出,进行插入操作的一端叫队尾,进行删除的一端叫队头。正如队列的名字一样,我们假设有一个队列(正在排队的一列队伍),一群人,人们依次进入队列进行排队。

一、什么是队列,什么是FIFO

队列允许在一端进行插入操作,在另一端进行删除操作的线性表,队列是与相对的一个数据结构,栈的特点是先进后出,而队列的特点是先进先出,进行插入操作的一端叫队尾,进行删除的一端叫队头。

正如队列的名字一样,我们假设有一个队列(正在排队的一列队伍),一群人,人们依次进入队列进行排队。

插入模拟图349e85fe0d084fd4a22965f112132ec7.gif

显然先排队的必然先出来,依次取出,和放入的顺序一样,这就是队列(FIFO)。

删除模拟图

74bc004281f243979a3bf2fa2075069d.gif

从程序化的角度来讲,应该有两个标记,一个标记着队头,一个标记着队尾,队头用来删除数据,队尾则用来插入数据。

二、使用C模拟实现以及解析队列

队列有两种实现方式,一种是使用数组来实现,另一种是使用链表来实现,由于队列需要对头部进行插入操作,使用数组效率方面会大打折扣,所以选择使用链表来实现队列是较优的选择。

1.结构体的定义

使用链表实现队列首先我们需要定义一个链表,其次由于需要在链表的头和尾进行插入以及删除操作,所有要定义两个指针分别记录下头和尾,再加入一个size来记录链表的大小。

typedef int QDataType;
typedef struct QListNode
{
  struct QlistNode* next;
  QDataType data;
}QNode;
typedef struct Queue
{
  QNode* front;
  QNode* tail;
  int size;
}Queue;

2.队列的创建及销毁

由于函数内有对参数指针的引用,加上assert预防程序崩溃,易于调试,摧毁的时候需要每个结点每个结点的进行销毁,因为链表的空间都是从堆中申请出来的,不进行释放会造成内存泄漏,全部释放之后再将指针制空。

void QueueInit(Queue* q)
{
  assert(q);
  q->front = NULL;
  q->tail = NULL;
  q->size = 0;
}
void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->front;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  q->front = NULL;
  q->tail = NULL;
  q->size = 0;
}

3.实现插入操作

每次插入需要申请一块新节点,如果链表为空第一次进行插入(及链表为空),需要将头和尾全部指向新节点,如果不是第一次插入(不为空),则将tail指向新节点。然后对size进行++。

bool QueueEmpty(Queue* q)
{
  return q->front == NULL;
}
void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode *temp = (QNode*)malloc(sizeof(QNode));
  if (temp == NULL)
  {
    perror("malloc error");
    return;
  }
  QNode* Newnode = temp;
  Newnode->data = data;
  Newnode->next = NULL;
  if (QueueEmpty(q))
  {
    q->front = q->tail = Newnode;
  }
  else
  {
    q->tail->next = Newnode;
    q->tail = q->tail->next;
  }
  q->size++;
}

4.队列删除操作

如果为空,不能进行删除,如果不为空释放掉头结点,将头结点指向原来头结点的下一个,这里需要注意如果头结点下一个为空,就不能只将头结点指向下一个(空),还需要将尾结点置空。

void QueuePop(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  QNode* next = q->front->next;
  free(q->front);
  q->front = next;
  if (next == NULL)
    q->tail == NULL;
  q->size--;
}

5.获取栈中有效元素个数以及头元素尾元素

返回对应变量即可。

int QueueSize(Queue* q)
{
  assert(q);
  return q->size;
}
QDataType QueueFront(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  return q->front->data;
}
QDataType QueueBack(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  return q->tail->data;
}

源代码分享

//Queue.h
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <malloc.h>
typedef int QDataType;
typedef struct QListNode
{
  struct QlistNode* next;
  QDataType data;
}QNode;
typedef struct Queue
{
  QNode* front;
  QNode* tail;
  int size;
}Queue;
void QueueInit(Queue* q);
void QueuePush(Queue* q, QDataType data);
void QueuePop(Queue* q);
QDataType QueueFront(Queue* q);
QDataType QueueBack(Queue* q);
int QueueSize(Queue* q);
bool QueueEmpty(Queue* q);
void QueueDestroy(Queue* q);
//Queue.c
#include "Queue.h"
void QueueInit(Queue* q)
{
  assert(q);
  q->front = NULL;
  q->tail = NULL;
  q->size = 0;
}
void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->front;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  q->front = NULL;
  q->tail = NULL;
  q->size = 0;
}
bool QueueEmpty(Queue* q)
{
  return q->front == NULL;
}
void QueuePush(Queue* q, QDataType data)
{
  assert(q);
  QNode *temp = (QNode*)malloc(sizeof(QNode));
  if (temp == NULL)
  {
    perror("malloc error");
    return;
  }
  QNode* Newnode = temp;
  Newnode->data = data;
  Newnode->next = NULL;
  if (QueueEmpty(q))
  {
    q->front = q->tail = Newnode;
  }
  else
  {
    q->tail->next = Newnode;
    q->tail = q->tail->next;
  }
  q->size++;
}
void QueuePop(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  QNode* next = q->front->next;
  free(q->front);
  q->front = next;
  if (next == NULL)
    q->tail == NULL;
  q->size--;
}
int QueueSize(Queue* q)
{
  assert(q);
  return q->size;
}
QDataType QueueFront(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  return q->front->data;
}
QDataType QueueBack(Queue* q)
{
  assert(q);
  assert(!QueueEmpty(q));
  return q->tail->data;
}
//test.c
#include "Queue.h"
void test()
{
  Queue pq;
  QueueInit(&pq);
  QueuePush(&pq,1);
  QueuePush(&pq,2);
  QueuePush(&pq,3);
  QueuePush(&pq,4);
  QueuePush(&pq,5);
  QueuePush(&pq,6);
  QNode* cur = pq.front;
  while (cur)
  {
    QNode* next = cur->next;
    printf("%d ", cur->data);
    cur = next;
  }
  printf("\n");
  QueuePop(&pq);
  QueuePop(&pq);
  QueuePop(&pq);
  cur = pq.front;
  while (cur)
  {
    QNode* next = cur->next;
    printf("%d ", cur->data);
    cur = next;
  }
  printf("\n");
  QueueSize(&pq);
  printf("%d", QueueFront(&pq));
  printf("%d", QueueBack(&pq));
  QueueDestroy(&pq);
}
int main()
{
  test();
}

d7d3c9764adc43d09c554697b8c3b851.gif

✨本文收录于数据结构理解与实现

下几期会继续带来栈与堆的练习题。如果文章对你有帮助记得点赞收藏关注。











相关文章
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
32 1
|
24天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
45 5
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
48 0
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
191 9
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
51 4
|
2月前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
48 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
2月前
初步认识栈和队列
初步认识栈和队列
65 10