投稿
  1. 高性能架构探索首页
  2. C/C++

数据结构-环形队列 C和C++的实现

admin • • C/C++ • 阅读 170

队列：

含义：是一种先入先出（FIFO）的数据结构。

当我们把数据一个一个放入队列中。当我们需要用到这些数据时，每次都从队列的头部取出第一个数据进行处理。就像排队进场一样，先排队的人先进场。

结构如下图所示

数据结构-环形队列 C和C++的实现

环形队列：

含义：它是在写程序时候一种队列的特殊表达方式，把队列数据组中的最后一个元素和第一个元素相连构成环，所以称为环形队列。

优点：环形队列在C/C++编程中首元素出队后不需要把队列所有元素向前移动，而取代把把队首指针向后移动，由于其环形结构，在插入元素后队尾指针会循环到队首原来的位置。相对普通队列的出队操作减少了大量的运算量。

C语言

程序清单：

本例中包含三个文件：

（插入图片）

Queue.h:
数据结构-环形队列 C和C++的实现数据结构-环形队列 C和C++的实现

#ifndef _QUEUE_H
#define _QUEUE_H
typedef unsigned char uint8_t;
typedef int Elem;

typedef struct circlequeue
{
    int iLength;
    int iSize;
    int iHead;
    int iTail;
    Elem *Datas; 
}Queue;

uint8_t  Queue_Init(Queue* queue,int size);
uint8_t Queue_Delete(Queue *queue);
uint8_t isQueueEmpty(Queue *queue);
uint8_t isQueueFull(Queue *queue);
int Queue_size(Queue *queue);
uint8_t Queue_push(Queue *queue,Elem data);
Elem Queue_front(Queue *queue);
Elem Queue_back(Queue *queue);
uint8_t Queue_pop(Queue *queue);
void Queue_printf(Queue *queue);

#endif

View Code

Queue.c:
数据结构-环形队列 C和C++的实现数据结构-环形队列 C和C++的实现

#include <stdlib.h>
#include <stdio.h>
#include "Queue.h"


/*******************************************************/
/*******************************************************/
/**********************创建队列*************************/
/*******************************************************/
/*******************************************************/
uint8_t  Queue_Init(Queue* queue,int size)
{    
    queue->iSize = size;
    queue->iLength = 0;
    queue->iTail=0;
    queue->iHead=0;
    queue->Datas = (Elem *)malloc(size*sizeof(Elem));
    return 1;
}
/*******************************************************/
/*******************************************************/
/**********************删除队列*************************/
/*******************************************************/
/*******************************************************/
uint8_t Queue_Delete(Queue *queue)
{
    free(queue->Datas);
    return 1;
}
/*******************************************************/
/*******************************************************/
/*********************队头队尾操作**********************/
/*******************************************************/
/*******************************************************/
static void QueueTailAdd(Queue *queue)
{
    queue->iTail++;
    queue->iTail = queue->iTail % queue->iSize;
}
static void QueueHeadAdd(Queue *queue)
{
    queue->iHead ++;
    queue->iHead = queue->iHead % queue->iSize;
}
/*******************************************************/
/*******************************************************/
/***********************队列判空************************/
/*******************************************************/
/*******************************************************/
uint8_t isQueueEmpty(Queue *queue)
{
    if(queue->iLength == 0)
    {
        return 1;
    }
    return 0;    
}
/*******************************************************/
/*******************************************************/
/***********************队列判满************************/
/*******************************************************/
/*******************************************************/
uint8_t isQueueFull(Queue *queue)
{
    if(queue->iLength>=queue->iSize)
    {
        return 1;
    }
    return 0;
}
/*******************************************************/
/*******************************************************/
/*******************返回队列现有长度********************/
/*******************************************************/
/*******************************************************/
int Queue_size(Queue *queue)
{
    return queue->iLength;
}
/*******************************************************/
/*******************************************************/
/********************往队尾放入元素*********************/
/*******************************************************/
/*******************************************************/
uint8_t Queue_push(Queue *queue,Elem data)
{
    if(isQueueFull(queue))
    {
        return 0;
    }

    queue->Datas[queue->iTail] = data; 
    QueueTailAdd(queue);
    queue->iLength++;
    return 1;
}
/*******************************************************/
/*******************************************************/
/************获取队头第一个元素（不删除）***************/
/*******************************************************/
/*******************************************************/
Elem Queue_front(Queue *queue)
{
    if(isQueueEmpty(queue))
    {
        return 0;
    }

    return queue->Datas[queue->iHead];
}
Elem Queue_back(Queue *queue)
{
    if(isQueueEmpty (queue))
    {
        return 0;
    }
    return queue->Datas[queue->iTail];
}
/*******************************************************/
/*******************************************************/
/******************删除队列第一个元素*******************/
/*******************************************************/
/*******************************************************/
uint8_t Queue_pop(Queue *queue)
{
    if(isQueueEmpty(queue))
    {
        return 0;//queue empty
    }

    QueueHeadAdd(queue);
    queue->iLength--;
    return 1;
}
/*******************************************************/
/*******************************************************/
/*****************打印队列中的全部元素******************/
/*******************************************************/
/*******************************************************/
void Queue_printf(Queue *queue)
{
    int i;
    int temp = queue->iHead;
    printf("queue datas:rn");
    for(i=0;i<queue->iLength;i++)
    {
        printf("%d ",queue->Datas[temp++%queue->iSize]);
    }
    printf("rn");
}

View Code

main.c(用于测试):
数据结构-环形队列 C和C++的实现数据结构-环形队列 C和C++的实现

#include <stdlib.h>
#include <stdio.h>
#include "Queue.h"


int main(void)
{
    int i;
    //queue(stack)
    Queue queue2[20];    
    //queue(heap)
    Queue *queue = (Queue*)malloc(sizeof(Queue)*20);
    //Queue Init
    Queue_Init(queue,20);
    Queue_Init(queue2,20);

    //queue1
    printf("insert datas:(0-19)rn");
    for(i=0;i<20;i++)
    {
        Queue_push(queue,i);
    }

    Queue_printf(queue);

    printf("delete datas(first 10):rn");
    for(i=0;i<10;i++)
    {
        Queue_pop(queue);
    }

    Queue_printf(queue);

    printf("first data:%drn",Queue_front(queue));

    printf("queuesize = %drn",Queue_size(queue));

    //queue2
    printf("rn");
    printf("insert datas to queue2:(0-190,10interval)rn");
    for(i=0;i<20;i++)
    {
        Queue_push(queue2,i*10);
    }

    Queue_printf(queue2);

    printf("delete datas(first 10):rn");
    for(i=0;i<10;i++)
    {
        Queue_pop(queue2);
    }

    Queue_printf(queue2);

    //delete queue
    printf("rn");
    printf("queue1 deletern");
    Queue_Delete(queue);
    free(queue);
    queue=0;

    printf("queue2 deletern");
    Queue_Delete(queue2);

    system("pause");
    return 0;
}

View Code

测试结果：

数据结构-环形队列 C和C++的实现

函数详解：

环形队列结构体：

在循环队列中，有以下参数

必要参数：

  • 数据 *Datas;
  • 对尾索引 iTail;
  • 队头索引 iHead;

可选参数：

  • 队列总大小 iSize;//队列最大存放量，防止不当操作造成堆栈溢出
  • 队列现在的长度 iLength;//储存现在的长度减少运算量（不定义此参数可以通过队头队尾索引差值计算长度）
typedef struct circlequeue
{
    int iLength;
    int iSize;
    int iHead;
    int iTail;
    Elem *Datas; 
}Queue;

创建队列：

  1. 设置队列的最大长度；
  2. 把队列中的其他参数清零；
  3. 为队列的数据区域申请内存；
uint8_t  Queue_Init(Queue* queue,int size)
{    
    queue->iSize = size;
    queue->iLength = 0;
    queue->iTail=0;
    queue->iHead=0;
    queue->Datas = (Elem *)malloc(size*sizeof(Elem));
    return 1;
}

入队操作：

数据结构-环形队列 C和C++的实现

  1. 判断队列是否已满，满则无法插入，返回0插入失败；
  2. 往队尾插入数据
  3. 队尾索引增加
  4. 队列长度增加
uint8_t Queue_push(Queue *queue,Elem data)
{
    if(isQueueFull(queue))
    {
        return 0;
    }

    queue->Datas[queue->iTail] = data; 
    QueueTailAdd(queue);
    queue->iLength++;
    return 1;
}

出队操作（分为两部分）

数据结构-环形队列 C和C++的实现

出队细分一、获取队头元素但不删除

  1. 判断队列是否为空，空则获取失败返回0；
  2. 返回队列中队头索引指向元素
Elem Queue_front(Queue *queue)
{
    if(isQueueEmpty(queue))
    {
        return 0;
    }

    return queue->Datas[queue->iHead];
}

出队细分二、删除队头的元素但不返回其值

  1. 判断队列是否为空，空则删除失败；
  2. 增加队头索引；
  3. 减少队列长度；
uint8_t Queue_pop(Queue *queue)
{
    if(isQueueEmpty(queue))
    {
        return 0;//queue empty
    }

    QueueHeadAdd(queue);
    queue->iLength--;
    return 1;
}

打印队列中的元素、

创建一个temp等于队头索引，后边打印中使用；

循环打印iLength（队列长度）个数据；

从队头(temp)指向的元素开始打印，每打印一个数据后temp++（指向下一个元素），（特别说明：temp%queue->iSize取余数，当temp索引超过最大长度时自动返回数组头开始打印，temp++%queue->iSize相当于两步1、temp%queue->iSize 2、temp++）

void Queue_printf(Queue *queue)
{
    int i;
    int temp = queue->iHead;
    printf("queue datas:rn");
    for(i=0;i<queue->iLength;i++)
    {
        printf("%d ",queue->Datas[temp++%queue->iSize]);
    }
    printf("rn");
}

C++语言

C++中思路和C基本类似，这里就不在赘述。上程序：

程序清单：

本部分包含三个文件：

（此处插入图）

原文链接: https://www.cnblogs.com/HongYi-Liang/p/7244022.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/257481

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年2月14日 上午10:56
下一篇 2023年2月14日 上午10:57

相关推荐