顺序队列及循环队列（C语言）

一、顺序队列

1、头文件SqQueue.h

#include <stdio.h>
#define MAXSIZE 100

typedef struct SqQuene
{
    int rear;
    void* data[MAXSIZE];
}SqQuene;

void InitQuene(SqQuene*);
int QueneEmpty(SqQuene*);
int QueneLength(SqQuene*);
void GetFront(SqQuene*, void**);
void EnQuene(SqQuene*, void*);
void DeQuene(SqQuene*, void**);
void ClearQuene(SqQuene*);

2、相关操作函数文件SqQueue.c

#include <stdio.h>
#include <string.h>
#include "SqQuene.h"

void InitQuene(SqQuene* sq)
{
    sq->rear = -1;
    memset(sq->data, 0, sizeof(sq->data));
}

int QueneEmpty(SqQuene* sq)
{
    if(sq->rear == -1)
        return 1;
    return 0;
}

int QueneLength(SqQuene* sq)
{
    return sq->rear + 1;
}

void ClearQuene(SqQuene* sq)
{
    sq->rear = -1;
}

void GetFront(SqQuene* sq, void** e)
{
    if(sq->rear == -1)
    {
        printf("队列为空，无法出队！\n");
        return;
    }

    *e = sq->data[0];
}

void EnQuene(SqQuene* sq, void* e)
{
    if(sq->rear == MAXSIZE - 1)
    {
        printf("队列已满，无法入队！\n");
        return;
    }

    sq->rear++;
    sq->data[sq->rear] = e;
}

void DeQuene(SqQuene* sq, void** e)
{
    if(sq->rear == -1)
    {
        printf("空队列，无法出队！\n");
        return;
    }

    *e = sq->data[0];

    int i = 1;
//该循环用于解决假溢出现象，但是开销比较大，更好的办法是建立循环队列
    for(i = 1; i <= sq->rear; i++)
    {
        sq->data[i-1] = sq->data[i];
    }

    sq->rear--;
}

3、主函数测试文件main.c

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

typedef struct stu
{
    int id;
    int age;
}Student;

int main()
{
    SqQuene sq;
    InitQuene(&sq);

    Student s[10];
    int i = 0;
    for(i = 0; i < 10; i++)
    {
        s[i].id = i;
        s[i].age = i + 20;
    }

    for(i = 0; i < 10; i++)
    {
        EnQuene(&sq, &s[i]);
    }

    printf("The size of Quene: %d\n", QueneLength(&sq));

    while(!QueneEmpty(&sq))
    {
        Student* tmp;
        GetFront(&sq, (void**)&tmp);
        printf("当前队头元素值为：%d, %d\n", tmp->id, tmp->age);
        //printf("当前队头的元素值为：id = %d, age = %d\n", tmp->id, tmp->age);

        DeQuene(&sq, (void**)&tmp);
        printf("当前出队的元素值为：id = %d, age = %d\n", tmp->id, tmp->age);
        printf("\n");
    }

    EnQuene(&sq, &s[0]);

    ClearQuene(&sq);
    printf("The size of Quene: %d\n", QueneLength(&sq));

    return 0;
}

二、循环队列

1、头文件circle_queue.h

#include <stdio.h>
#define MAXSIZE 10

typedef struct cqueue
{
    int front;
    int rear;
    void* data[MAXSIZE];
}cqueue;

void InitQueue(cqueue*);
int QueueEmpty(cqueue*);
int QueueLength(cqueue*);
void GetFront(cqueue*, void**);
void EnQueue(cqueue*, void*);
void DeQueue(cqueue*, void**);
void ClearQueue(cqueue*);

2、相关操作函数circle_queue.c

#include "circle_queue.h"
#include <string.h>

void InitQueue(cqueue* cq)
{
    cq->front = -1;
    cq->rear = -1;
    memset(cq->data, 0, sizeof(cq->data));
}

int QueueEmpty(cqueue* cq)
{
    if(cq->front == cq->rear)
        return 1;

    return 0;
}

int QueueLength(cqueue* cq)
{
    return (cq->rear - cq->front + MAXSIZE) % MAXSIZE;
}

void GetFront(cqueue* cq, void** e)
{
    if(QueueEmpty(cq))
    {
        printf("空队列！\n");
        return;
    }

    *e = cq->data[cq->front + 1];
}

void EnQueue(cqueue* cq, void* e)
{
    if((cq->rear + 1) % MAXSIZE == cq->front)
    {
        printf("队满！\n");
        return;
    }

    cq->rear = (cq->rear + 1) % MAXSIZE;
    cq->data[cq->rear] = e;
}

void DeQueue(cqueue* cq, void** e)
{
    if(QueueEmpty(cq))
    {
        printf("空队列！\n");
        return;
    }

    *e = cq->data[cq->front + 1];
    cq->front = (cq->front + 1) % MAXSIZE;
}

void ClearQueue(cqueue* cq)
{
    while(!QueueEmpty(cq))
    {
        void* tmp;
        DeQueue(cq, &tmp);
    }
}

3、主函数测试文件main.c

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

typedef struct stu
{
    int id;
    int age;
}student;

int main()
{
    cqueue cq;
    InitQueue(&cq);

    student s[MAXSIZE];
    int i = 0;


    //最多只能存放MAXSIZE - 1个数据
    for(i = 0; i < MAXSIZE - 1; i++)
    {
        s[i].id = i;
        s[i].age = i + 20;
        EnQueue(&cq, (void*)&s[i]);
    }
    printf("当前队列长度为：%d\n", QueueLength(&cq));

    for(i = 0; i < 5; i++)
    {
        student* tmp;
        GetFront(&cq, (void**)&tmp);
        printf("当前队头元素为：id = %d, age = %d\n", tmp->id, tmp->age);
        DeQueue(&cq, (void**)&tmp);
        printf("当前出队元素为：id = %d, age = %d\n", tmp->id, tmp->age);
        printf("\n");
    }

    printf("当前队列长度为：%d\n", QueueLength(&cq));

    for(i = 0; i < 5; i++)
    {
        EnQueue(&cq, (void*)&s[i]);
    }
    printf("当前队列长度为：%d\n", QueueLength(&cq));

    ClearQueue(&cq);
    printf("当前队列长度为：%d\n", QueueLength(&cq));

    return 0;
}