循环顺序队列

循环顺序队列结构体声明

typedef struct loopQueue{//尾进头出
    data_t data[N];
    int front;//指向队头元素，相当于“头”，出队的地方
    int rear;//指向队尾元素的下一个位置，相当于“尾”，入队的地方
}loopq,*LOOPQ;

循环顺序队列的偏移

(q->front+1)%N

(q->rear+1)%N

循环顺序队列的操作

基本操作：创建、入队、出队、遍历（打印）、求队列长度

创建一个循环队列

LOOPQ create()
{
    LOOPQ q = (LOOPQ)malloc(sizeof(loopq));
    //bzero(q->data,sizeof(data_t)*N);//warning：bzero不兼容隐式声明
    memset(q->data,0,sizeof(data_t)*N);
    q->front = q->rear = 0;
    return q;
}

注意：LOOPQ q = (LOOPQ)malloc(sizeof(loopq));与LOOPQ q = (LOOPQ)malloc(sizeof(LOOPQ));的区别，后者LOOPQ是结构体指针的类型大小，动态分配空间会出错

判断队是否为满

int isFull(LOOPQ q)
{
    return (q->rear+1)%N == q->front ? 1 : 0;
}

尾（rear）触到头（front）

入队

void push(LOOPQ q,data_t val)
{
    if(isFull(q)){
        printf("队满\n");
        return;
    }
    q->data[q->rear] = val;
    q->rear = (q->rear+1)%N;
}

rear先插入数据（入队），后向后移一位

判断队是否为空

int isEmpty(LOOPQ q)
{
    return q->rear == q->front ? 1 : 0;
}

尾（rear）等于头（front）

出队

data_t pop(LOOPQ q)
{
    data_t data;
    if(isEmpty(q))
    {
        printf("队空\n");
        return -1;
    }
    data = q->data[q->front];
    q->front = (q->front+1)%N;
    return data;
}

q->front往后移位，原先的数据仍存在分配的数组空间中，只是已经不属于队列了

遍历（打印）

void printLoopQ(LOOPQ q)
{
    int i;
    if(isEmpty(q))
    {
        printf("队空\n");
        return;
    }
    if(q->front<=q->rear-1)
    {
        for(i=q->front;i<=q->rear-1;i++)
        {
            printf("%d ",q->data[i]);
        }
        putchar(10);
    }
    else
    {
        for(i=q->front;i<=N-1;i++)
        {
            printf("%d ",q->data[i]);
        }
        for(i=0;i<=q->rear-1;i++)
        {
            printf("%d ",q->data[i]);
        }
        putchar(10);
    }
}

存在两种情况

1、rear在front的右边，从外侧往数组里看，数据是一串连续的数据

2、rear在front的左边，从外侧往数组里看，数据被分成了2段，分居两端

3、把握for循环的初始值和结束条件

求队列长度

int loopQueueSize(LOOPQ q)
{
    return (q->rear+N-q->front)%N;
}

1、rear的值存在小于front的情况：此时rear-front<0；

N-front为数组后端的数据个数，rear-0为数组前端的数据个数，此时，rear-0+N-front为数据总个数

2、rear大于front时，此时rear-front即为数据总个数；

对N取模总结：（ (表达式+N)%N ）

a、若表示式为大于等于0且小于N的正整数，则取模后的结果为表达式本身的值

b、若表达式小于0且大于等于-N的负整数，则取模后的结果为N+表达式

示例

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 6
typedef int data_t;
typedef struct loopQueue{//尾进头出
    data_t data[N];
    int front;//指向队头元素，相当于“头”，出队的地方
    int rear;//指向队尾元素的下一个位置，相当于“尾”，入队的地方
}loopq,*LOOPQ;

LOOPQ create();
int isFull(LOOPQ q);
void push(LOOPQ q,data_t val);
int isEmpty(LOOPQ q);
data_t pop(LOOPQ q);
void printLoopQ(LOOPQ q);
int loopQueueSize(LOOPQ q);

int main(int argc, char const *argv[])
{
    LOOPQ q = create();
    printf("start:\n");
    push(q,1);
    printLoopQ(q);
    push(q,2);
    printLoopQ(q);
    push(q,3);
    printLoopQ(q);
    push(q,4);
    printLoopQ(q);
    push(q,5);
    printLoopQ(q);
    push(q,6);//队满
    printLoopQ(q);
    printf("出队：%d\n",pop(q));//1
    printLoopQ(q);//2 3 4 5
    printf("出队：%d\n",pop(q));//2
    printLoopQ(q);//3 4 5
    printf("出队：%d\n",pop(q));//3
    printLoopQ(q);//4 5
    printf("出队：%d\n",pop(q));//4
    printLoopQ(q);//5
    printf("出队：%d\n",pop(q));//5
    printLoopQ(q);//队空
    printf("出队：%d\n",pop(q));//队空返回-1
    printLoopQ(q);//队空

    push(q,1);
    printLoopQ(q);
    push(q,2);
    printLoopQ(q);
    push(q,3);
    printLoopQ(q);
    push(q,4);
    printLoopQ(q);
    push(q,5);
    printLoopQ(q);
    push(q,6);//队满
    printLoopQ(q);
    printf("出队：%d\n",pop(q));//1
    printLoopQ(q);//2 3 4 5
    push(q,7);
    printLoopQ(q);//2 3 4 5 7
    printf("队长：%d\n",loopQueueSize(q));
    return 0;
}
//创建一个循环队列
LOOPQ create()
{
    LOOPQ q = (LOOPQ)malloc(sizeof(loopq));
    //bzero(q->data,sizeof(data_t)*N);
    memset(q->data,0,sizeof(data_t)*N);
    q->front = q->rear = 0;
    return q;
}
//判断队是否为满：尾（rear）触到头（front）
int isFull(LOOPQ q)
{
    return (q->rear+1)%N == q->front ? 1 : 0;
}
//入队：rear先入队后位移
void push(LOOPQ q,data_t val)
{
    if(isFull(q)){
        printf("队满\n");
        return;
    }
    q->data[q->rear] = val;
    printf("插入：%d\n",q->data[q->rear]);
    printf("q->rear=%d ",q->rear);
    q->rear = (q->rear+1)%N;
    printf("--> q->rear=%d\n",q->rear);
}
//判断队是否为空：尾（rear）等于头（front）
int isEmpty(LOOPQ q)
{
    return q->rear == q->front ? 1 : 0;
}
//出队：front位移
data_t pop(LOOPQ q)
{
    data_t data;
    if(isEmpty(q))
    {
        printf("队空\n");
        return -1;
    }
    data = q->data[q->front];
    q->front = (q->front+1)%N;
    printf("q->front=%d\n",q->front);
    return data;
}
//遍历（打印）
void printLoopQ(LOOPQ q)
{
    int i;
    if(isEmpty(q))
    {
        printf("队空\n");
        putchar(10);
        return;
    }
    if(q->front<=q->rear-1)
    {
        printf("队列：");
        for(i=q->front;i<=q->rear-1;i++)
        {
            printf("%d ",q->data[i]);
        }
        putchar(10);
        putchar(10);
    }
    else
    {
        printf("队列：");
        for(i=q->front;i<=N-1;i++)
        {
            printf("%d ",q->data[i]);
        }
        for(i=0;i<=q->rear-1;i++)
        {
            printf("%d ",q->data[i]);
        }
        putchar(10);
        putchar(10);
    }
}
//求队列长度
int loopQueueSize(LOOPQ q)
{
    return (q->rear+N-q->front)%N;
}

结果

start:
插入：1
q->rear=0 --> q->rear=1
队列：1

插入：2
q->rear=1 --> q->rear=2
队列：1 2

插入：3
q->rear=2 --> q->rear=3
队列：1 2 3

插入：4
q->rear=3 --> q->rear=4
队列：1 2 3 4

插入：5
q->rear=4 --> q->rear=5
队列：1 2 3 4 5

队满
队列：1 2 3 4 5

q->front=1
出队：1
队列：2 3 4 5

q->front=2
出队：2
队列：3 4 5

q->front=3
出队：3
队列：4 5 

q->front=4
出队：4
队列：5

q->front=5
出队：5
队空

队空
出队：-1
队空

插入：1
q->rear=5 --> q->rear=0
队列：1

插入：2
q->rear=0 --> q->rear=1
队列：1 2

插入：3
q->rear=1 --> q->rear=2
队列：1 2 3

插入：4
q->rear=2 --> q->rear=3
队列：1 2 3 4

插入：5
q->rear=3 --> q->rear=4
队列：1 2 3 4 5

队满
队列：1 2 3 4 5

q->front=0
出队：1
队列：2 3 4 5

插入：7
q->rear=4 --> q->rear=5
队列：2 3 4 5 7

队长：5

本文链接：https://shengto.top/data_structure/158.html

转载时须注明出处及本声明

Last modification：2021 年 03 月 26 日 02 : 19 : 18
© 允许规范转载