【数据结构】 循环队列的基本操作 (C语言版)

发布时间:2024年01月24日

目录

一、顺序队列

1、顺序队列的定义:

2、顺序队列的优缺点:

二、循环队列

1、循环队列的定义:

2、循环队列的优缺点:

三、循环队列的基本操作算法(C语言)???

1、宏定义

??2、创建结构体

3、循环队列的初始化?

4、循环队列的销毁

5、循环队列的清空

6、求循环队列的长度

7、循环队列的判空

8、求队头元素

9、循环队列入队

10、循环队列出队

11、遍历队列元素

四、循环队列的基本操作完整代码(C语言)

? 五、运行结果


一、顺序队列

1、顺序队列的定义:

顺序队列是由一维数组实现的队列,其中队头元素的下标为0,队尾元素的下标为n-1(n为数组大小),队列的大小在创建时确定,且在队列的生命周期内保持不变。

2、顺序队列的优缺点:

顺序队列的优点:

  1. 空间利用率高:由于数组的大小在创建时确定,因此可以预先分配足够的空间,避免了频繁的内存申请和释放操作,提高了空间利用率。
  2. 存取速度快:由于队列元素在内存中连续存储,因此可以根据下标直接访问队头元素和队尾元素,存取速度快。

顺序队列的缺点:

  1. 不适合处理动态扩展的数据:顺序队列的空间大小在创建时确定,因此无法动态扩展,对于需要处理大规模数据的情况不太适用。
  2. 容易发生假溢出:由于顺序队列的队头和队尾元素不断向后移动,当队列满时,如果继续入队操作,会导致假溢出,即无法再进行入队操作。
  3. 无法充分利用内存的连续性优势:由于顺序队列是基于数组实现的,因此无法充分利用内存的连续性优势,因为队头和队尾元素可能分散在不同的内存位置。

二、循环队列

1、循环队列的定义:

循环队列是一种线性数据结构,它将队列的元素存储在一个连续的数组中,并通过使用循环指针来管理队列的插入和删除操作。循环队列的特点在于,当队列为空时,头尾指针指向同一位置;当队列满时,头尾指针也指向同一位置。?

2、循环队列的优缺点:

循环队列的优点:

  1. 空间利用率高:循环队列使用固定大小的数组来存储元素,无需动态分配内存,因此可以充分利用存储空间。
  2. 时间复杂度稳定:在循环队列中,插入和删除操作具有固定的时间复杂度,这使得循环队列在需要频繁进行插入和删除操作的场景中表现优异。
  3. 无需额外的空间:由于循环队列使用数组实现,因此无需额外的空间来存储元素,从而降低了空间复杂度。

循环队列的缺点:

  1. 队列大小固定:循环队列的大小是固定的,因此在处理大量数据时,可能需要预先分配大量存储空间。如果实际数据量超过预分配的空间,可能会导致数据丢失或程序崩溃。
  2. 判断队列是否为空或满的判断逻辑较复杂:在循环队列中,判断队列是否为空或满的判断逻辑相对复杂。需要同时考虑头尾指针的位置和当前队列的状态。如果处理不当,可能会导致误判或错过一些特殊情况。
  3. 插入和删除操作需要移动元素:虽然循环队列在插入和删除操作时具有固定的时间复杂度,但在实际操作中,仍然需要移动元素以保持队列的连续性和循环性。如果数据量大或者数据不均匀分布,可能会影响操作效率。

三、循环队列的基本操作算法(C语言)???

1、宏定义
#define OK 1
#define ERROR 0
#define OVERFLOW -1

#define MAXSIZE 100

typedef int QElemType;
typedef int Status;
??2、创建结构体
//创建结构体
typedef struct {
    QElemType *base;
    int front;
    int rear;
} SqQueue;
3、循环队列的初始化?
//初始化
Status InitQueue(SqQueue &Q) {
    //构造一个空队列
    Q.base = new QElemType[MAXSIZE];
    if (!Q.base) {
        exit(OVERFLOW);
    }
    Q.front = Q.rear = 0;
    return OK;
}
4、循环队列的销毁
//销毁队列
Status DestroyQueue(SqQueue &Q) {
    if (Q.base) {
        delete Q.base;
    }
    Q.base = NULL;
    Q.front = Q.rear = 0;
    return OK;
}
5、循环队列的清空
//清空队列
Status ClearQueue(SqQueue &Q) {
    Q.front = Q.rear = 0;
    return OK;
}
6、求循环队列的长度
//求长度
Status QueueLength(SqQueue Q) {
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;

}
7、循环队列的判空
Status QueueEmpty(SqQueue Q) {
    if (Q.front == Q.rear) {
        return true;
    } else {
        return false;
    }
}
8、求队头元素
//求队头元素
Status GetHead(SqQueue Q, QElemType &e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    e = Q.base[Q.front];
    return OK;
}
9、循环队列入队
//循环队列入队
Status EnQueue(SqQueue &Q, QElemType e) {
    if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXSIZE;
    return OK;
}
10、循环队列出队
//循环队列出队
Status DeQueue(SqQueue &Q, QElemType &e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
    return OK;
}
11、遍历队列元素
//遍历队列
void DisplayQueue(SqQueue Q) {
    int i = Q.front;
    printf("队列元素为: ");
    while (Q.front != Q.rear && (i + MAXSIZE) % MAXSIZE != Q.rear) {
        printf("%d ", Q.base[i]);
        i++;
    }
}
四、循环队列的基本操作完整代码(C语言)
#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define OVERFLOW -1

#define MAXSIZE 100

typedef int QElemType;
typedef int Status;

//创建结构体
typedef struct {
    QElemType *base;
    int front;
    int rear;
} SqQueue;

//初始化
Status InitQueue(SqQueue &Q) {
    //构造一个空队列
    Q.base = new QElemType[MAXSIZE];
    if (!Q.base) {
        exit(OVERFLOW);
    }
    Q.front = Q.rear = 0;
    return OK;
}

//销毁队列
Status DestroyQueue(SqQueue &Q) {
    if (Q.base) {
        delete Q.base;
    }
    Q.base = NULL;
    Q.front = Q.rear = 0;
    return OK;
}

//清空队列
Status ClearQueue(SqQueue &Q) {
    Q.front = Q.rear = 0;
    return OK;
}

//求长度
Status QueueLength(SqQueue Q) {
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;

}

//判空
Status QueueEmpty(SqQueue Q) {
    if (Q.front == Q.rear) {
        return true;
    } else {
        return false;
    }
}

//求队头元素
Status GetHead(SqQueue Q, QElemType &e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    e = Q.base[Q.front];
    return OK;
}

//循环队列入队
Status EnQueue(SqQueue &Q, QElemType e) {
    if ((Q.rear + 1) % MAXSIZE == Q.front) return ERROR;
    Q.base[Q.rear] = e;
    Q.rear = (Q.rear + 1) % MAXSIZE;
    return OK;
}

//循环队列出队
Status DeQueue(SqQueue &Q, QElemType &e) {
    if (Q.front == Q.rear) {
        return ERROR;
    }
    e = Q.base[Q.front];
    Q.front = (Q.front + 1) % MAXSIZE;
    return OK;
}

//遍历队列
void DisplayQueue(SqQueue Q) {
    int i = Q.front;
    printf("队列元素为: ");
    while (Q.front != Q.rear && (i + MAXSIZE) % MAXSIZE != Q.rear) {
        printf("%d ", Q.base[i]);
        i++;
    }
}

//功能菜单列表
void show_help() {
    printf("******* 功能菜单列表 *******\n");
    printf("1----入队------------------\n");
    printf("2----求循环队列长度----------\n");
    printf("3----出队------------------\n");
    printf("4----取队头元素-------------\n");
    printf("5----清空循环队列-----------\n");
    printf("6----销毁循环队列-----------\n");
    printf("7----判断循环队列是否为空-----\n");
    printf("8----批量插入元素------------\n");
    printf("9----显示队列元素------------\n");
    printf("10----退出------------------\n\n");
}

int main() {
    SqQueue sq;

    //初始化
    Status rInitStack = InitQueue(sq);
    if (rInitStack == OK) {
        printf("循环队列初始化成功!\n");
    } else {
        printf("循环队列初始化失败!\n");
    }


    while (1) {

        //功能菜单列表
        show_help();

        int flag;
        printf("请输入所需的功能编号:\n");
        scanf("%d", &flag);

        switch (flag) {
            case 1: {//入队
                Status EnQueueindex;
                printf("请输入插入元素(请在英文状态下输入例如:1): \n");
                scanf("%d", &EnQueueindex);
                Status rEnQueue = EnQueue(sq, EnQueueindex);
                if (rEnQueue == OK) {
                    printf("向循环队列入队%d成功!\n", EnQueueindex);
                } else {
                    printf("向循环队列入队失败!\n");
                }
            }
                break;
            case 2: {//求循环队列的长度
                int length = QueueLength(sq);
                printf("循环队列的长度为:%d。 \n\n", length);
            }
                break;
            case 3: {//出队
                Status DeQueueindex;
                Status rDeQueue = DeQueue(sq, DeQueueindex);
                if (rDeQueue == OK) {
                    printf("向循环队列出队%d成功!\n", DeQueueindex);
                } else {
                    printf("向循环队列出队失败!\n");
                }
            }
                break;
            case 4: {//求队头元素
                Status topData;
                Status rGetHead = GetHead(sq, topData);
                if (rGetHead == OK) {
                    printf("向循环队列获取队头元素:%d\n", topData);
                } else {
                    printf("向循环队列获取队头元素失败!\n");
                }
            }
                break;
            case 5: { //清空
                Status rClearStack = ClearQueue(sq);
                if (rClearStack == OK) {
                    printf("循环队列清空成功!\n");
                } else {
                    printf("循环队列清空失败!\n");
                }
            }
                break;
            case 6: {//销毁
                Status rDestroyStack = DestroyQueue(sq);
                if (rDestroyStack == OK) {
                    printf("循环队列销毁成功!\n");
                } else {
                    printf("循环队列销毁失败!\n");
                }
            }
                break;
            case 7: {///判空
                Status ClearStatus = QueueEmpty(sq);
                if (ClearStatus == true) {
                    printf("循环队列为空!\n\n");
                } else {
                    printf("循环队列不为空!\n\n");
                }
            }
                break;
            case 8: {//批量插入
                int on;
                printf("请输入想要插入的元素个数:\n");
                scanf("%d", &on);
                QElemType array[on];
                for (int i = 1; i <= on; i++) {
                    printf("向循环队列第%d个位置插入元素为:", i);
                    scanf("%d", &array[i]);
                }

                for (int i = 1; i <= on; i++) {
                    Status InsertStatus = EnQueue(sq, array[i]);
                    if (InsertStatus == OK) {
                        printf("向循环队列第%d个位置插入元素%d成功!\n", i, array[i]);
                    } else {
                        printf("向循环队列第%d个位置插入元素%d失败!\n", i, array[i]);
                    }
                }
            }
                break;
            case 9: {//输出链表元素
                DisplayQueue(sq);
                printf("\n");
            }
                break;
            case 10: {//退出程序
                return 0;
            }
                break;
            default: {
                printf("输入错误,无此功能,请检查输入:\n\n");
            }
        }
    }

    return 1;
}

? 五、运行结果

文章来源:https://blog.csdn.net/weixin_56814370/article/details/135789680
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。