动态顺序队列 C语言-蒲公英云

动态顺序队列 C语言

数据结构c语言动态顺序队列的实现和表示

代码如下：

#include <stdio.h>
#include <stdlib.h>
#define InitSize 6
typedef struct
{ 
    int *base;//存储空间的基地址 
    int front;//头指针 
    int rear;//尾指针 
    int MAXSIZE;//队列存储最大值 
}SqQueue;
void InitQueue(SqQueue &Q)//初始化队列 
{ 
    Q.base = (int*)malloc(sizeof(int)*InitSize);//申请空间 
    if(Q.base == NULL)//判断申请的空间是否为空 
        printf("分配空间失败！\n");
    else
    { 
        Q.MAXSIZE = InitSize;//使队列最大值等于申请的空间 
        Q.front = Q.rear = 0; //头尾指针都指向0 
    }
}
void EnQueue(SqQueue &Q,int e)//进队 ，由于是循环队列，故少用一个元素空间，该函数在有MAXSIZE-1个元素时便已判断为满 
{ 
    if((Q.rear+1)%Q.MAXSIZE == Q.front)//判断队列是否为满 ，这里是循环队列队列满的条件是 (Q.rear+1)%MAXSIZE == Q.front 
        printf("队列已满！\n");
    else
    { 
        if(Q.rear == Q.MAXSIZE) //如果队尾超出最大值但队列又不满，便使其对最大值求余运算 
            Q.rear = Q.rear%Q.MAXSIZE;//对最大值求模 
        Q.base[Q.rear] = e;//使变量e的值入队 
        Q.rear++;//并使队尾加一 
    }
}
void DeQueue(SqQueue &Q)//出队 
{ 
    if(Q.front == Q.rear)//首先判断队列是否为空，队列为空的条件是 Q.front == Q.rear
        printf("队列为空！\n");
    else
    { 
        printf("%d\n",Q.base[Q.front]);//导出队头元素数据 
        Q.front++;//使队头加一 
        if(Q.front == Q.MAXSIZE)//在队列非空的情况下，如果队头等于最大值，也对最大值做求余运算 
            Q.front = Q.front%Q.MAXSIZE;
    }
}
int Length(SqQueue Q)//求当前队列的长度 
{ 
    if(Q.front<=Q.rear)//如果队头在队尾的前方，直接减就是队列的长 
        return Q.rear-Q.front;
    else//如果队头在队尾的后面，那么就需要队尾加上最大值，再减队头 
        return Q.rear+Q.MAXSIZE-Q.front;
}
void IncreaseSize(SqQueue &Q,int len)//动态增加队列的长 
{ 
    int a = Q.front,
        b = Length(Q),
        c = Q.MAXSIZE,//分别使最大值，队头还是队长赋值给变量，成为固定值 
        i;
    int *p;
    p = Q.base;//申请个指针使其指向队列基地址 
    Q.base = (int*)malloc(sizeof(int)*(InitSize+len));//重新申请队列Q的空间 
    Q.MAXSIZE = InitSize+len;//最大值为新申请空间的值 
    Q.front = Q.rear = 0;//初始化操作 
    for(i=0;i<b;i++)//利用循环使老的队列中的数据导入新的队列中 
    { 
        if((a+i) == c)
            a = (a+i)%c-i;
        Q.base[Q.rear++] = p[a+i];
    }    
} 
int main()
{ 
    int i;
    SqQueue Q;
    InitQueue(Q);//对队列的初始化 
    for(i=1;i<7;i++)//使数1,2,3,4,5,分别依次进队 
        EnQueue(Q,i);
    IncreaseSize(Q,1);
    EnQueue(Q,6); 
    printf("当前队列长： %d\n",Length(Q));//出队之前队列的长 
    DeQueue(Q);
    printf("当前队列长： %d\n",Length(Q));//出队之后队列的长 
    free(Q.base); //释放队列的基地址 
    return 0;
}