【算法与数据结构】队列的实现详解

简介: 【算法与数据结构】队列的实现详解

📝队列的概念及结构

1.队列的概念:

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 新添加的元素添加到队尾,只能从队头取出元素。

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

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

  1. 队列特征如下:

入队(Enqueue):通过尾指针添加元素到队列尾部,即向队列中插入元素。


出队(Dequeue):通过头指针删除队列头部元素,即从队列中移除元素。


空队列:当头指针和尾指针相同时,表示队列为空。


满队列:当尾指针指向队列容量最大位置时,表示队列已满。


常用的队列结构包括数组和链表实现:

数组实现队列:使用一维数组存储元素,头指针和尾指针分别指向数组的下标位置。


链表实现队列:每个元素使用一个节点存储,头节点和尾节点通过指针链接实现队列。

🌠 队列的顺序实现

头文件:Queue_order.h

# define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

typedef int QDataType;

typedef struct Queue
{
  QDataType data[MAX_SIZE];
  int front;
  int rear;
  int size;//记录队列中元素数量
}Queue;

//初始化队列
void InitQueue(Queue* pq);
//入队操作
void EnQueue(Queue* pq,int value);
//出队
QDataType DeQueue(Queue* pq);
//获取队首元素
QDataType FrontQueue(Queue* pq);
//获取队尾元素
QDataType RearQueue(Queue* pq);

//获取队列中有效元素个数
QDataType SizeQueue(Queue* pq);
//队列是否为空
QDataType IsEmpty(Queue* pq);
//队列是否为满
QDataType IsFull(Queue* pq);
//销毁队列
void DestroyQueue(Queue* pq);

🌉初始化

//初始化队列
void InitQueue(Queue* pq)
{
  pq->front = -1;
  pq->rear = -1;
  pq->size = 0;
}

front和rear都指向-1,表示队列中没有数据。size为0,表示队列中没有元素。

🌠入队

//入队
void EnQueue(Queue* pq, int value)
{
  if (pq->front == MAX_SIZE - 1)
  {
    printf("队列满了,入队操作失败");//检查队列是否已满,如果front指针指向的下一个位置就是MAX_SIZE-1,表示队列已满,打印错误信息并返回。
    return;
  }
  if (pq->front == -1)
  {//如果front为-1,表示队列为空,将front指针置0。
    pq->front = 0;
  }
  pq->rear++;//如果front为-1
  pq->data[pq->rear] = value;//表示队列为空
  pq->size++;//加完了别忘了size++
}

🌉出队

//出队
QDataType DeQueue(Queue* pq)
{
  if (-1 == IsEmpty)
  {
    printf("队列为空!");
    return -1;//返回一个特定的值表示队列为空
  }
  int value = pq->data[pq->front];
  pq->front++;
  pq->size--;
  return value;
}

检查满是为了防止入队越界,front-1时,表示队列为空,需要将front置0,rear后移一位指向新的元素位置,将元素值写入data数组,size计数增加。

🌠获取队列首元素

//获取队首元素
QDataType FrontQueue(Queue* pq)
{
  if (-1 == IsEmpty)
  {
    printf("队列为空!");
    return -1;//返回一个特定的值表示队列为空
  }
  return pq->data[pq->front];
}

🌉获取队列尾部元素

//获取队列尾部元素
QDataType RearQueue(Queue* pq)
{
  if (0 == IsEmpty)
  {
    printf("队列为空!");
    return -1;//返回一个特定的值表示队列为空
  }
  return pq->data[pq->rear];
}

🌠获取队列中有效元素个数

//获取队列中有效元素个数
QDataType SizeQueue(Queue* pq)
{
  return pq->size;
}

🌉 队列是否为空

//队列是否为空
QDataType IsEmpty(Queue* pq)
{
  if (pq->front == -1 || (pq->front > pq->rear))
  {
    //队列为空
    return -1;
  }
  else
  {
    //队列不为空
    return 1;
  }
  
}

注意:在队列中,如果 front 指针大于 rear 指针,表示队列为空。这是因为 front 指针指向队列的第一个元素,而 rear 指针指向队列的最后一个元素。如果 front 指针大于 rear 指针,意味着队列中没有元素,或者已经出队了所有的元素。

考虑一个队列中有一个元素的情况。初始时 front 和 rear 都指向该元素,而当该元素出队时,front 指针会被移动到下一个位置,这时 front 指针就比 rear 指针大,表示队列已经为空。

🌠查看队列是否为满

//查看队列是否为满
QDataType IsFull(Queue* pq)
{
  return (pq->rear == MAX_SIZE - 1);
}

🌉销毁队列

//销毁队列
void DestroyQueue(Queue* pq)
{
  InitQueue(pq);//重新初始化队列,清空元素并释放内存
}

🌠测试

源文件Test.c

# define _CRT_SECURE_NO_WARNINGS 1
#include"Queue_order.h"

int main()
{
  Queue Pq;
  InitQueue(&Pq);

  EnQueue(&Pq, 10);
  EnQueue(&Pq, 20);
  EnQueue(&Pq, 30);
  
  printf("Front element: %d\n", FrontQueue(&Pq));
  printf("Rear element: %d\n", RearQueue(&Pq));
  printf("Front element: %d\n", SizeQueue(&Pq));
  printf("Front element: %d\n", FrontQueue(&Pq));

  printf("Dequeued element: %d\n", DeQueue(&Pq));
  printf("Dequeued element: %d\n", DeQueue(&Pq));
  printf("Dequeued element: %d\n", DeQueue(&Pq));
  printf("Dequeued element: %d\n", DeQueue(&Pq)); // 尝试从空队列中出队

  printf("Queue size: %d\n", SizeQueue(&Pq));
  printf("Is queue empty? %s\n", IsEmpty(&Pq) ? "Yes" : "No");
}

🌉 顺序队列的假溢出


顺序队列的假溢出指的是,队列在结构上没有真正满溢,但是在逻辑上已经无法再插入新元素了。

在队尾指针已经指向数组的最后一个位置,但数组中仍然有空闲空间时,确实是队列溢出的情况,而不是假溢出。这种情况通常是由于没有充分利用队列所分配的存储空间所导致的,因此会造成队列操作的限制。


“假溢出” 通常用于表示队列中还有空闲空间,但因某种原因无法继续插入元素的情况,这可能是由于某些限制条件或错误的队列操作所导致的。例如,可能存在对队列的错误管理,使得无法正确地判断队列是否已满,导致了插入元素失败的情况。

举个例子:

在一个顺序队列中,队列大小为5,已包含四个元素 value1-2-3-4,rear在队尾4的位置。

当出队两个元素value1-2时,队列前面多出来了两位置

当你想再插入来两个数据时,队列确只能插入一个数据,但是队列其实不能插入数据了。

这是队列在结构上没有真正满溢,但是在逻辑上已经无法再插入新元素了。

怎么优化这个假溢出呢?两种常见的方法:


1.循环队列: 循环队列是一种特殊的顺序队列,通过将队列的数组视为一个循环的环形结构,使得在队列尾部插入元素时可以利用数组头部的空闲空间,从而解决了假溢出的问题。循环队列中,当队尾指针指向数组的末尾时,再插入元素时将其指向数组的起始位置,这样就形成了一个循环。通过这种方式,可以充分利用数组空间,避免了假溢出。

2.动态扩容: 动态扩容是在顺序队列满时,自动增加数组的大小以容纳更多元素。当队列满时,分配一个更大的数组,并将原有的元素复制到新数组中,然后释放原来的数组。这样可以确保队列始终有足够的空间来插入新的元素,从而避免假溢出。动态扩容的关键是选择适当的扩容策略,以及控制扩容时机,以避免频繁的扩容操作带来的性能开销。

🌠循环队列概念

循环队列是一种基于数组实现的队列数据结构,其特点是通过循环利用数组空间来实现队列的操作。循环队列的数组通常被看作一个环形的结构,队列的头部和尾部指针在数组中循环移动,使得当尾部指针到达数组末尾时,可以将其“循环”到数组的起始位置,从而避免了溢出或假溢出的情况。

循环队列看似循环,其实是固定数组不断往复的过程,我们可以模拟普通数组来实现:

如图:data 表示一个数据域,int 为类型,当然你也可以修改为任意自定义的类型,也可以是复杂的结构体类型。

MAX_SIZE :表示循环最大容量,可进行放数据的操作空间

rear代表尾指针,入队时移动。

front代表头指针,出队时移动。

size记录当前有效数据的多少


代码:

#define MAX_SIZE 5

typedef struct {
    int data[MAX_SIZE];
    int front; // 队列头指针
    int rear;  // 队列尾指针
    int size;  // 队列当前元素个数
} Cir_Queue;

🌉循环队列的初始化

对于循环队列来说,front从0开始是合理的,因为数据数组是环状结构,front从0开始可以实现队列元素的循环利用。

rear从0开始表示队列此时为空,front和rear指针都指向数组第一个位置。

将队列当前元素个数size清零,表示队列为空。

// 初始化队列
void initQueue(Cir_Queue* queue) 
{
    queue->front = 0;将队列头指针front设置为0。
    queue->rear = 0;将队列尾指针rear也设置为0。
    queue->size = 0;
}

🌠循环队列的入队操作

入队操作与顺序队列相同,只需将rear向后移动。但要注意,如果rear达到队列的上限,需从头开始移动。建议使用余数法,确保操作在队列空间内进行,避免一次错误导致整体崩溃。

要进行入队操作,得先判断队列是不是满了rear==front来判断队空,也可以用size。

// 入队操作
void enqueue(Cir_Queue* queue, int value) 
{
    if (queue->size == MAX_SIZE) 
    {
        printf("Queue is full. Enqueue operation failed.\n");
        return;
    }
    queue->data[queue->rear] = value;
    queue->rear = (queue->rear + 1) % MAX_SIZE; // 使用(rear+1)%MAX_SIZE更新rear指针,循环移动
    queue->size++;
}

检查队列是否已满,可通过判断size是否等于MAX_SIZE来确定。如果已满,则打印提示信息并返回;将数值value赋给data数组的rear索引位置,并使用(rear+1)%MAX_SIZE更新rear指针。这里使用模运算来实现rear指针的循环移动。当rear指向最后一个位置时,利用模运算使其指向第一个位置,实现循环利用数组。然后将size增加1,表示元素个数加1。

🌉 循环队列的出队操作

// 出队操作
int dequeue(Cir_Queue* queue)
 {
    if (queue->size == 0)
     {
        printf("Queue is empty. Dequeue operation failed.\n");
        return -1;
    }
    int value = queue->data[queue->front];
    queue->front = (queue->front + 1) % MAX_SIZE; // 循环移动
    queue->size--;
    return value;
}

使用(front+1)%MAX_SIZE更新front指针,这里也使用模运算实现front指针的循环移动。当front指向最后一个位置时,利用模运算让它指向第一个位置。

🌉 查看队首元素

// 查看队首元素
int front(Cir_Queue* queue) 
{
    if (queue->size == 0) 
    {
        printf("Queue is empty. Front operation failed.\n");
        return -1;
    }
    return queue->data[queue->front];
}

🌠查看队尾元素

// 查看队尾元素
int rear(Cir_Queue* queue) 
{
    if (queue->size == 0) 
    {
        printf("Queue is empty. Rear operation failed.\n");
        return -1;
    }
    return queue->data[(queue->rear - 1 + MAX_SIZE) % MAX_SIZE];
}

🌉查看队列是否为空

// 查看队列是否为空
int isEmpty(Cir_Queue* queue) 
{
    return (queue->size == 0);
}

🌠查看队列是否已满

// 查看队列是否已满
int isFull(Cir_Queue* queue) 
{
    return (queue->size == MAX_SIZE);
}

🌉 测试下循环队列

int main() {
    Cir_Queue queue;
    initQueue(&queue);

   
    enqueue(&queue, 10);
    enqueue(&queue, 20);
    enqueue(&queue, 30);
    enqueue(&queue, 40);
    

    printf("Front element: %d\n", front(&queue));

    printf("Dequeued element: %d\n", dequeue(&queue));
    printf("Dequeued element: %d\n", dequeue(&queue));
    printf("Dequeued element: %d\n", dequeue(&queue));
    enqueue(&queue, 80);
    enqueue(&queue, 90);
    printf("Front element: %d\n", front(&queue));
    printf("rear element: %d\n", rear(&queue));

    return 0;
}


🚩总结

感谢你的收看,如果文章有错误,可以指出,我不胜感激,让我们一起学习交流,如果文章可以给你一个小小帮助,可以给博主点一个小小的赞😘

相关文章
|
3天前
|
存储 监控 NoSQL
Redis处理大量数据主要依赖于其内存存储结构、高效的数据结构和算法,以及一系列的优化策略
【5月更文挑战第15天】Redis处理大量数据依赖内存存储、高效数据结构和优化策略。选择合适的数据结构、利用批量操作减少网络开销、控制批量大小、使用Redis Cluster进行分布式存储、优化内存使用及监控调优是关键。通过这些方法,Redis能有效处理大量数据并保持高性能。
22 0
|
2天前
|
缓存 算法 Java
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
|
2天前
|
前端开发 JavaScript 算法
JavaScript 中实现常见数据结构:栈、队列与树
JavaScript 中实现常见数据结构:栈、队列与树
|
3天前
|
存储 编译器 C语言
数据结构——顺序队列与链式队列的实现-2
数据结构——顺序队列与链式队列的实现
数据结构——顺序队列与链式队列的实现-2
|
3天前
|
存储 C语言
数据结构——顺序队列与链式队列的实现-1
数据结构——顺序队列与链式队列的实现
数据结构——顺序队列与链式队列的实现-1
|
3天前
|
机器学习/深度学习 算法 数据可视化
Python 数据结构和算法实用指南(四)(4)
Python 数据结构和算法实用指南(四)
10 1
|
3天前
|
机器学习/深度学习 存储 算法
Python 数据结构和算法实用指南(四)(3)
Python 数据结构和算法实用指南(四)
14 1
|
3天前
|
存储 算法 搜索推荐
Python 数据结构和算法实用指南(四)(2)
Python 数据结构和算法实用指南(四)
10 0
|
3天前
|
存储 算法 Serverless
Python 数据结构和算法实用指南(四)(1)
Python 数据结构和算法实用指南(四)
14 0
|
3天前
|
存储 NoSQL C语言
数据结构——顺序栈与链式栈的实现-2
数据结构——顺序栈与链式栈的实现
数据结构——顺序栈与链式栈的实现-2