[学习笔记]循环队列和队列的链式结构

先来说下队列.其实就是线性表的变种.遵循先进先出,即删除数据的位置为头结点,新增数据的位置为尾结点.恩,就是这么简单...

好了,按照在线性表的顺序存储我们知道了如果我们删除一个数据的话那么时间复杂度为0(N),既然我们现在知道了我们每次删除的都是头结点,咱们定义一个int性的front来存储头结点的下标,那么我们的复杂度就是0(1)了不是,增加数据也就简单了,搞一个int型的rear来存储尾结点的下标,然后增加数据的时间复杂度也为0(1)了,Wow,cool...但是...咱们就想了啊,如果加入在一个可以存储10个数据的队列里,先一口气插入了10个数据,接下来,我们删除前9个数据,那么现在front和rear的值都是9了对不对,好了,我们再新增一个数据,额,都到了数组末尾了,sorry.不能新增了...可是...可是...前面空了9个位置啊亲!咋就不能灵活点嘛!于是乎就有了循环队列.即rear到达了数组末尾的时候再新增数据rear值移到0即数组开头不就行了!好了,有个问题又来了,咱们如何判断队列是满了呢?当rear==front的时候?嘿嘿,那你估计一辈子都插不进数据了,咱们刚开始的时候不是rear就等于front嘛...那咱们再设一个bool型的flag,初始化的时候flag=0表示队列空,然后当满的时候flag设置为1,这样不就解决了问题了嘛,赞一个,确实可以如此,不过也可以这样,那就是咱们留一个位置来不放数据,即(rear+1)%MAXSIZE==Front的时候表示队列满了.ok,上数据结构和代码:

队列结构:

typedef struct{
    char Data[MAXSIZE];
    int Front;
    int Rear;
}Queue;

1.初始化:

BOOL InitializeQueue(Queue *Q)
{
    Q->Rear=Q->Front=0;

    return true;
}

2.插入数据:

BOOL InsertDataQueue(Queue *Q,char InsertData)
{    
    if(Q->Front==(Q->Rear+1)%MAXSIZE)//if the queue is full,return false
        return false;
    
    Q->Data[Q->Rear]=InsertData;
    Q->Rear=(Q->Rear+1)%MAXSIZE;//position of rear move to next adress,move to the head if the Q->Rear+1 is equal to MAXSIZE

    return true;
}

3.删除数据:

BOOL DeleteDataQueue(Queue *Q,char *DeleteData)
{
    if(Q->Front==Q->Rear)//if the queue is empty, return false
        return false;

    *DeleteData=Q->Data[Q->Front];
    Q->Data[Q->Front]=0;
    Q->Front=(Q->Front+1)%MAXSIZE;

    return true;
}

4.取得队列头数据:

BOOL GetHead(Queue Q,char *HeadData)
{
    if(Q.Rear==Q.Front)
        return false;
    *HeadData=Q.Data[Q.Front];

    return true;
}

5.队列长度:

int QueueLength(Queue Q)
{
    return (Q.Rear-Q.Front+MAXSIZE)%MAXSIZE;
}

6.清空队列:

BOOL ClearQueue(Queue *Q)
{
    int temp;

    if(Q->Rear==Q->Front)
        return false;

    Q->Front=Q->Rear=0;

    return true;
}

7.队列是否为空:

BOOL isQueueEmpty(Queue Q)
{
    if(Q.Rear==Q.Front)
        return true;

    return false;
}

写个完整的程序测试下:

#define true 1
#define false 0
#define BOOL int

#define MAXSIZE 27

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

int main(void)
{
    Queue Q;
    char InputData='a',DeleteData;
    int temp;

    if(false==InitializeQueue(&Q))
    {
        printf("Initialize queue fail!\n");

        return false;
    }
    printf("Initialize queue success!\n");

    for(temp=0;temp<MAXSIZE-1;temp++)
    {
        if(false==InsertDataQueue(&Q,InputData))
        {
            printf("Insert data  %c fail!\n",InputData);
        }
        printf("Insert data %c success!\n",InputData);
        InputData++;
    }
    printf("Success to create a queue which length is %d\n",QueueLength(Q));

    if(false==DeleteDataQueue(&Q,&DeleteData))
        printf("Fail to delete Data from the length!\n");
    printf("Success to delete the data %c,the length of new queue is %d\n",DeleteData,QueueLength(Q));

    if(false==ClearQueue(&Q))
        printf("Fail to Clear the queue's data!\n");
    printf("Success to clear the queue's data!the new length of queue is %d\n",QueueLength(Q));

    return 0;
}

运行截图:

Capture.PNG

接下来说下队列的链式结构,既然是链式结构了,那肯定就是线性表的链式存储的变体了,不错,就是尾结点插入,头结点删除.其它的没啥好说的,就是注意指针的运用,直接上数据结构和代码: