欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C语言实现静态循环队列

程序员文章站 2022-05-26 12:09:06
...

C语言实现静态队列

循环静态队列是一种长度固定,空间循环使用的队列。

C语言实现静态循环队列
为充分利用向量空间,克服”假溢出”现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表的方式来在实际编程应用中来实现。
具体操作过程见下图:
C语言实现静态循环队列
以下是简单代码实现:

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

//结构体
typedef struct Queue
{
    int * array;                //数组作为队列
    int front;                  //队列的头索引
    int tail;                   //队列的尾索引
}QUEUE,*PQUEUE;

//函数声明
void Init_queue(PQUEUE);
void In_queue(PQUEUE,int val);
void Out_queue(PQUEUE,int* val);
void Traverse_queue(PQUEUE);
bool Isempty(PQUEUE);
bool Isfull(PQUEUE);

//主函数
int main(void)
{
    QUEUE Q;
    int val,i;
    int array[] = {2,4,26,40,12,87,1,58,36};
    Init_queue(&Q);
    printf("要入队的值有:\n");
    for(i=0;i<sizeof(array)/4;i++)
    {
          printf("%4d",array[i]);
    }                         
    printf("\n");
    for(i=0;i<sizeof(array)/4;i++)
    {
         In_queue(&Q,array[i]);        //这里测试入队9个值,实际的队长只有8,队满是7个元素
    }
    printf("入队后的结果:\n");
    Traverse_queue(&Q);
    Out_queue(&Q,&val);
    printf("出队的元素是:%d\n",val);
    printf("出队后的结果:\n");
    Traverse_queue(&Q);
    return 0;
}

//初始化队列
void Init_queue(PQUEUE Q)
{
    Q->array = (int *)malloc(sizeof(int)*8);     //申请数组队列的动态空间
    if(Q->array == NULL)
    {
        printf("动态内存分配失败!\n");
        exit(0);
    }
    Q->front = 0;
    Q->tail = 0;
    return;
}

//入队
void In_queue(PQUEUE Q,int val)
{
   if(Isfull(Q))
   {
       printf("%4d入队失败!队列已满。\n",val);
   }else
   {
       Q->array[Q->tail] = val;
       Q->tail = (Q->tail+1)%8;
   }
}

//出队
void Out_queue(PQUEUE Q,int* val)
{
    if(Isempty(Q))
    {
         printf("出队失败!队列中没有元素。\n");
    }else
    {
        *val = Q->array[Q->front];
        Q->front = (Q->front+1)%8;            //头索引加一,如果到达最大索引,从0开始
    }
}

//遍历队列中的元素值
void Traverse_queue(PQUEUE Q)
{
    int val = Q->front;
    while(val != Q->tail)                    //从队列头开始一直遍历到队列尾元素
    {
        printf("%4d",Q->array[val]);
        val = (val+1)%8;
    }
    printf("\n");

}

//判断队列是否为空
bool Isempty(PQUEUE Q)
{
    if(Q->front ==  Q->tail)                 //把队头和队尾相同作为队列为空的判断条件
    {
        return true;
    }else
    {
        return false;
    }
}

//判断队列是否满
bool Isfull(PQUEUE Q)
{
    if((Q->tail+1)%8 == Q->front) //此处的算法意思是当队列尾再加一个元素就和队列头重合的时候代表队列已满     
    {
        return true;
    }else
    {
        return false;
    }
}