数据结构——循环队列（数组）_循环队列代码

一、循环队列的定义

二、循环队列图示

 

三、循环队列使用规则 

为解决队满和队空的判断条件相同。

我们 采用  损失一个单元不用的方法

即当循环队列元素的个数是MAXSIZE-1时，就认为队列已满（front指向空的单元）

这样循环队列的队满条件就变成 ：

(rear+1)%MAXSIZE==front

循环队列的队空条件依旧是：

front==rear

 

四、循环队列的代码 

#define MAXSIZE 4     
 
typedef int DataType;
typedef struct
{
    DataType data[MAXSIZE];  //实际上只能存MAXSIZE-1 个数据
    int front;
    int rear;
}SeqQueue;
 
//损失一个单元不用，即当循环队列中元素个数是MAXSIZE-1时，就认为队列已经满了
//front指向那个不使用的单元
//循环队列的队满的条件就是(rear+1)%MAXSIZE==front
//队空的条件是  front==rear
 
//初始化队列
void InitQueue(SeqQueue* Q)//初始化队列函数
{
    Q->front = Q->rear = 0;//指针初始化
}
 
//判断是否为空
int  EmptyQueue(SeqQueue* Q)//判断队空函数
{
    if (Q->front == Q->rear)//队列为空
        return 1;
    else
        return 0;
}
 
//判断是否为满
int  FullQueue(SeqQueue* Q)//判断队满函数
{
    if (Q->front == (Q->rear + 1) % MAXSIZE)//队尾指针加上1，再取余MAXSIZE的值如果等于队头指针，说明队列为满
        return 1;
    else
        return 0;
}
 
//入队操作
void InQueue(SeqQueue* Q, DataType x)//入队函数
{
    if (FullQueue(Q))
    {
        printf("队列已满,无法继续入队\n");
        return;
    }
    else
    {
        Q->rear = (Q->rear + 1) % MAXSIZE;//更新队尾指针rear,队尾指针加1再取余MAXSIZE,将数组形成一个循环
        Q->data[Q->rear] = x;//将入队的数据放到队列数组，更新后的rear所指向的位置
    }
}
 
//出队操作
void DeQueue(SeqQueue* Q)//出队函数
{
    if (EmptyQueue(Q))
    {
        printf("队列已空,无法继续出队\n");
        return;
    }
    else
    {
        Q->front = (Q->front + 1) % MAXSIZE; //更新队头指针front, 队头指针加1再取余MAXSIZE, 将数组形成一个循环
    }
}
 
//取队头操作
DataType GetFront(SeqQueue* Q)//取队头函数
{
    if (EmptyQueue(Q))
    {
        printf("队列已空,无队头元素\n");
        return 0;
    }
    else
    {
        int t;  //因为front指向的位置无元素，队头元素在front指向的后一位
        t = (Q->front + 1) % MAXSIZE; //将 队头指针加1再取余MAXSIZE 的值赋给t
        return Q->data[t]; //返回数组中下标为t的元素
    }
}
 
void ShowQueue(SeqQueue* Q)//显示队中元素函数
{
    int p = Q->front;
    if (p == Q->rear)
        printf("队列为空，无元素！\n");
    else
    {
        printf("\n从队头起队列中的个元素为：");
        while (p != Q->rear)
        {
            printf("%5d", Q->data[(p + 1) % MAXSIZE]);
            p++;        
            p %= MAXSIZE; //使得p能从数组的首位地址重新遍历，形成循环，打印出所有的数组元素
 
        }
    }
}

五、循环队列的函数使用

1.入队函数：InQueue

int main()
{
    SeqQueue SQ;
    InitQueue(&SQ);//初始化
    InQueue(&SQ, 3);//入队
    InQueue(&SQ, 4);//入队
    InQueue(&SQ, 5);//入队
    //插入3次，满了
   
    InQueue(&SQ, 5);//第四次插入不了
 
    ShowQueue(&SQ);//打印数组中所有的值
    return 0;
}

 结果：

插入3次，满了。第四次插入不了

 

 2.取队头函数GetFront

int main()
{
    SeqQueue SQ;
    InitQueue(&SQ);//初始化
    InQueue(&SQ, 3);//入队
    InQueue(&SQ, 4);//入队
    InQueue(&SQ, 5);//入队
    //插入3次，满了
   
    printf("循环队列中的元素依次是:");
    ShowQueue(&SQ);//打印数组中所有的值
    printf("\n");
 
    DataType x = GetFront(&SQ);//取队头元素
    printf("\n队头元素是：%d \n", x);
    return 0;
}

结果：

 

3.出队函数DeQueue

int main()
{
    SeqQueue SQ;
    InitQueue(&SQ);//初始化
    InQueue(&SQ, 3);//入队
    InQueue(&SQ, 4);//入队
    InQueue(&SQ, 5);//入队
    //插入3次，满了
   
    printf("循环队列中的元素依次是:");
    ShowQueue(&SQ);//打印数组中所有的值
    printf("\n\n");
 
    DeQueue(&SQ);//出队一次
    InQueue(&SQ,99);//出队之后，再入队一次
    printf("操作后循环队列中的元素依次是:");
    ShowQueue(&SQ);//打印数组中所有的值
 
    return 0;
}

结果；

出队之后，再入队一次，打印新的循环队列

六、心得体会

1. 队列是一种运算受限制的线性表，插入在队尾，删除在队头。
2. 队列的逻辑结构和线性表也相同，数据元素之间存在一对一的关系，它的主要特性是先进先出
3. 循环队列是队列的一种顺序表示和实现方法。与顺序栈类似，在队列的顺序存储结构中，用一组地址连续的存储单元依次存放从队头到队尾的元素。
4. 由于队列中队头和队尾的位置都是动态变化的，因此需要附设两个指针front和rear，分别知识队头元素和队尾元素在数组中的位置。
5. 普通的顺序队列会有假溢出，一个巧妙的办法就是将顺序队列的数组看成一个环状的空间，即规定最后一个单元的后继为第一个单元，我们形象地称之为循环队列。