首页 > 其他分享 >数据结构：栈与队列-详解循环队栈

数据结构：栈与队列-详解循环队栈

时间：2023-10-30 15:37:48浏览次数：31  
标签：return 队列 printf int flag 详解 队栈 数据结构 循环

《详解循环队栈》

目录：

  1. 循环队列的定义及其特点
  2. 循环队列的实现
  3. 完整Demo
  4. 运行截图
  5. 小结
  6. 参考文献

一、循环队列的定义及其特点

　　队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。而循环队列是队列的一种特殊形式，循环队列（也被称为环形队列）是一种线性数据结构，其操作表现基于先进先出原则（FIFO），并且队尾被连接在队首之后形成一个循环。在循环队列固定大小，空间能够重复利用。

二、循环队列的实现

　　队列实现一般有两种数组队列和链式队列，数组队列在一般应用中都会将其头尾相连形成循环队列，因为普通的数组存在“假溢出的问题”。本文所讲述并实现的队列为没有头结点的循环队列。

　　1.结构体定义

　　　　本次顺序栈的代码中定义了队列最大容量，用于存储数据元素的指针，队头下标，队尾下标。

typedef int DataType;

typedef struct {
    
    int maxSize;//队列最大容量 
    DataType* data;//数据指针 
    int front;//队头下标 
    int rear;//队尾下标 
    
}CirclesQueue;

 

　　2.初始化

　　　　初始化时使用MaxSzie（最大容量）+ 1 * 单个DataType长度申请内存空间，同时将队头队尾下标指向0；此处加一是为了留出最后一个结点空间，用于避免队头队尾重合，头尾重合在循环队列里一般视为空队列，当然也可以另外定义一个flag标记来判断是否为满或空，这样就可以不用多申请一个结点，优化了内存占用。但本文的代码实现为什么不用呢？因为我懒得写。

/**
 * @brief 循环队列初始化
 *
 * @param Q 循环队列指针
 * @param MaxSize 队列最大长度
 *
 * @return 状态码：0为成功
 **/
int initCirclesQueue(CirclesQueue* Q, int MaxSize) {

    Q->data = (DataType*)malloc(sizeof(DataType) * (MaxSize + 1));

    if (!Q->data) {
        printf("%s", errorHint[0]);
        return errorCode[0];
    }
    Q->maxSize = (MaxSize + 1);
    Q->front = 0;
    Q->rear = 0;

    return 0;
}

 

　　3.入队

　　　　入队、出队操作比较简单，入队时先进行队列判满，如满即返回错误码，反之则将数据元素插入队尾，而后将队尾下标后移一位。此处需要注意的是要将队尾下标+1后对maxSize（队列最大容量）取余，避免下标溢出。

/**
 * @brief 循环队列入队
 *
 * @param Q 循环队列指针
 * @param x 入队数据元素
 *
 * @return 状态码：0为成功
 **/
int enqueue(CirclesQueue* Q, DataType* x) {
    int flag = isFullQueue(Q);
    if (!flag) {
        Q->data[Q->rear] = *x;
        Q->rear = ((Q->rear + 1) % Q->maxSize);
        return 0;
    }

    return flag;
}

 

　　4.出队

　　　　出队同入队一般，先进行队列判空，如空即返回错误码，反之则将传入的DataType指针指向队头所指的数据元素，而后将队头下标后移一位。此处需要注意的是要将队头下标+1后对maxSize（队列最大容量）取余，避免下标溢出。

/**
 * @brief 循环队列出队
 *
 * @param Q 循环队列指针
 * @param x 入队数据元素
 *
 * @return 状态码：0为成功
 **/
int dequeue(CirclesQueue* Q, DataType* x) {
    int flag = isEmptyQueue(Q);
    if (!flag) {
        *x = Q->data[Q->front];
        Q->front = ((Q->front + 1) % Q->maxSize);
        return 0;
    }

    return flag;
}

 

　　5.打印

　　　　打印时需先进行判空，为空即打印错误信息并返回错误码，反之则从队头下标开始遍历队列，直至队头下标+1 = 队尾下标。此处和出队一样需要注意循环中要将队头下标+1后对maxSize（队列最大容量）取余，避免下标溢出。

/**
 * @brief 循环队列打印
 *
 * @param Q 循环队列指针
 *
 * @return 状态码：0为成功
 **/
int printQueue(CirclesQueue* Q) {
    int flag = isEmptyQueue(Q);
    if (!flag) {
        int coordinates = Q->front;

        printf("循环队列：");
        while (coordinates != Q->rear) {
            printf(" %d", Q->data[coordinates]);
            coordinates = ((coordinates + 1) % Q->maxSize);
        }
        printf("\n");
        return 0;
    }

    return flag;
}

 

三、完整Demo

　　welcome.h（欢迎字符图案）：

char *welcome[] = {
    "                                    \n",
    "                                             4&(\n",
    "                                           ` ~&&\\yM#1\n",
    "                                            ,_'Q!!NMW&\n",
    "                                            WCb 7N@4D Q%,,\n",
    "                                            PM'*MDk#M0p,\n",
    "                                                ]@J0&e~~4r' ,+bQEQ\n",
    "                                                 F8I&#'   _&B$$bW#&$\n",
    "                                                  &0A1   L#DE&E~!Q&Q,\n",
    "                                     _=,        ,#0RN1  _T@0$'   ZN$Q.   grNq5\n",
    "                                     ^ 'd     ,0K0pK^  g*Q0g'    #Q4p&,/g9X*&#,_/ (q\n",
    "                                      TA1   ,sDQWh4^  x&NM0` _   #FQ#K#fA#   `*K#XWP~-\n",
    "                                       ^&p,wNMM0qD: /HE#EN' ..#g)~ '@NG0Qx,    `=X*\n",
    "                                      '  '43$'hEk##m0D04f_g  ~^ ~   `-00**0\n",
    "                                               =0#ONq2W0BF^#, _            p,,\n",
    "                                                 `  ^''~    ~b''        **R3`\n",
    "                                                          ow,F         +#F~'\n",
    "                                                          /-9!          `\\ \n",
    "                                                           R\n"
    };
View Code

　　circlesQueue.h（结构体与函数声明）：

/*
    CirclesQueue
*/ 

typedef int DataType;

typedef struct {
    
    int maxSize;//队列最大容量 
    DataType* data;//数据指针 
    int front;//队头下标 
    int rear;//队尾下标 
    
}CirclesQueue;

int initCirclesQueue(CirclesQueue* Q, int MaxSize);

int enqueue(CirclesQueue* Q, DataType* x);

int dequeue(CirclesQueue* Q, DataType* x);

int isFullQueue(CirclesQueue* Q);

int isEmptyQueue(CirclesQueue* Q);

int printQueue(CirclesQueue* Q);
View Code

　　circlesQueue.c（函数实现）：

#include <stdio.h>
#include "circlesQueue.h"
#include <malloc.h>
#include "error.h"

/**
 * @brief 循环队列初始化
 *
 * @param Q 循环队列指针
 * @param MaxSize 队列最大长度
 *
 * @return 状态码：0为成功
 **/
int initCirclesQueue(CirclesQueue* Q, int MaxSize) {

    Q->data = (DataType*)malloc(sizeof(DataType) * (MaxSize + 1));

    if (!Q->data) {
        printf("%s", errorHint[0]);
        return errorCode[0];
    }
    Q->maxSize = (MaxSize + 1);
    Q->front = 0;
    Q->rear = 0;

    return 0;
}

/**
 * @brief 循环队列入队
 *
 * @param Q 循环队列指针
 * @param x 入队数据元素
 *
 * @return 状态码：0为成功
 **/
int enqueue(CirclesQueue* Q, DataType* x) {
    int flag = isFullQueue(Q);
    if (!flag) {
        Q->data[Q->rear] = *x;
        Q->rear = ((Q->rear + 1) % Q->maxSize);
        return 0;
    }

    return flag;
}

/**
 * @brief 循环队列出队
 *
 * @param Q 循环队列指针
 * @param x 入队数据元素
 *
 * @return 状态码：0为成功
 **/
int dequeue(CirclesQueue* Q, DataType* x) {
    int flag = isEmptyQueue(Q);
    if (!flag) {
        *x = Q->data[Q->front];
        Q->front = ((Q->front + 1) % Q->maxSize);
        return 0;
    }

    return flag;
}

/**
 * @brief 循环队列判满
 *
 * @param Q 循环队列指针
 *
 * @return 状态码：0为不为满
 **/
int isFullQueue(CirclesQueue* Q) {

    if (((Q->rear + 1) % Q->maxSize) == Q->front) {
        printf("%s", errorHint[1]);
        return     errorCode[1];
    }

    return 0;
}

/**
 * @brief 循环队列判空
 *
 * @param Q 循环队列指针
 *
 * @return 状态码：0为不为空
 **/
int isEmptyQueue(CirclesQueue* Q) {
    if (Q->rear == Q->front) {
        printf("%s", errorHint[2]);
        return errorCode[2];
    }

    return 0;
}

/**
 * @brief 循环队列打印
 *
 * @param Q 循环队列指针
 *
 * @return 状态码：0为成功
 **/
int printQueue(CirclesQueue* Q) {
    int flag = isEmptyQueue(Q);
    if (!flag) {
        int coordinates = Q->front;

        printf("循环队列：");
        while (coordinates != Q->rear) {
            printf(" %d", Q->data[coordinates]);
            coordinates = ((coordinates + 1) % Q->maxSize);
        }
        printf("\n");
        return 0;
    }

    return flag;
}
View Code

　　main.c（主函数）：

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include "welcome.h"
#include "circlesQueue.h"

int main(int argc, char *argv[]) {

    for (int i = 0; i < 19; i++) {
        printf("%s", welcome[i]);
        for (int j = 0; j <= 100000000; j++) {
            for (int m; m <= 100000000; m++) {
                ;
            }
        }
    }

    int operate;
    int maxSize;
    char verify;
    DataType data;
    CirclesQueue Q;

    printf("\n\n本应用程序为数据结构-循环队列演示程序，用于课程实践与研究。由季老师指导，日月同珲开发。\n\n");
    do {
        printf("<---------------------------------------------------循环队列演示程序-------------------------------------------------->\n");
        printf("0. 退出程序\n");
        printf("1. 初始化循环队列\n");
        printf("2. 打印循环队列\n");
        printf("3. 入队\n");
        printf("4. 出队\n");
        printf("5. 帮助\n");
        printf("请输入操作选项(0~5,0为退出)：");
        scanf("%d", &operate);
//        getchar();
        switch (operate) {
            case 1:
                printf("请输入循环队列最大容量：");
                scanf("%d", &maxSize);
//                getchar();
                if (!initCirclesQueue(&Q, maxSize)) {
                    printf("初始化完成\n\n");
                }
                break;
            case 2:
                printQueue(&Q);
                break;
            case 3:
                printf("请输入入队数据：");
                scanf("%d", &data);
                if (!enqueue(&Q, &data)) {
                    printf("元素%d入队成功！\n\n", data);
                }
                break;
            case 4:
                while (1) {
                    printf("出队操作无法完全恢复是否要出栈？(y/n)：");
                    getchar();
                    scanf("%c", &verify);
                    if (verify == 89 || verify == 121) {
                        if (!dequeue(&Q, &data)) {
                            printf("元素%d出队成功！\n\n", data);
                        }
                        break;
                    } else if (verify == 78 || verify == 110) {
                        printf("出队操作已取消\n\n");
                        break;
                    }
                }

                break;
            case 5:
                printf("本应用程序为数据结构-循环队列演示程序，用于课程实践与研究。由季老师指导，日月同珲开发。\n\n");
                break;
            case 0:
                return 0;
                break;
        }

    } while (operate != 0);

    return 0;
}
View Code

　　error.h（错误信息）：

int errorCode[] = {100001, 100002, 100003, 100004, 100005};

char* errorHint[] = {
    "ERROR[100001]：申请内存错误，初始化失败！\n\n",
    "ERROR[100002]：循环队列已满！\n\n",
    "ERROR[100003]：循环队列为空！\n\n",
    "ERROR[100004]：无可撤销操作！\n\n",
    "ERROR[100005]：申请内存错误，结点创建失败！\n\n",
};
View Code

 

四、运行截图

程序运行效果图

 

五、小结

　　队列的内容也是比较简单，只需注意在操作下标的时候要将下标对最大容量取余避免数组越界。

　　每周闲篇：本来是准备在这周将手上的这个APP结工的，又双叒叕因为计划外的N个状况打断了！莫名其妙还被劈头盖脸训了一顿，上次通话中压根没提材料细则吧？怎么又变成我的问题了？怎么老是有人喜欢把问题搞复杂？还推卸责任？

六、参考文献

　　　　王海艳等.《数据结构（C语言）》第二版[M].北京:人民邮电出版社,2020:10~14.

标签：return,队列,printf,int,flag,详解,队栈,数据结构,循环
From： https://www.cnblogs.com/RYTH/p/17797652.html

相关文章

  • 一文详解如何从 Oracle 迁移数据到 DolphinDB
    Oracle是一个广泛使用的关系型数据库管理系统，它支持ACID事务处理，具有强大的安全性和可靠性，因此被广泛应用于各种企业级应用程序。但是，随着数据规模的增加和业务需求的变化，Oracle的一些限制和缺点也逐渐暴露出来。例如，Oracle的许可证费用昂贵，而且对于海量数据的处理能力较弱。......
  • 数据结构与算法 | 二分搜索（Binary Search）
    二分搜索（BinarySearch）文承上篇，搜索算法中除了深度优先搜索（DFS）和广度优先搜索（BFS），二分搜索（BinarySearch）也是最基础搜索算法之一。二分搜索也被称为折半搜索（Half-intervalSearch）也有说法为对数搜索算法（LogarithmicSearch），用于在已排序的数据集中查找特定元素。搜索过程从排序数......
  • 05数据结构(栈、队列、数组、链表)
    数据结构一、什么是数据结构计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。数据结构是为了更加方便的管理和使用数据，需要结合具体的业务场景来进行选择。一般情况下，精心选择的数据结构可以带来更高的运行或者存储效率。如何学习数据结构：每......
  • 算法：实现中序遍历（3种方法图例详解，小白也能看懂）
     中序遍历：左->中 ->右练习地址：力扣（LeetCode）官网-全球极客挚爱的技术成长平台1、递归法 #Definitionforabinarytreenode.classTreeNode(object):def__init__(self,val=0,left=None,right=None):self.val=valself.left=left......
  • 神经网络基础篇：详解导数（Derivatives）
    导数一个函数\(f(a)=3a\)，它是一条直线。下面来简单理解下导数。让看看函数中几个点，假定\(a=2\)，那么\(f(a)\)是\(a\)的3倍等于6，也就是说如果\(a=2\)，那么函数\(f(a)=6\)。假定稍微改变一点点\(a\)的值，只增加一点，变为2.001，这时\(a\)将向右做微小的移动。0.001的差别实在是太小了，不......
  • Chromium CC渲染层工作流详解
    1.Chromium的渲染流水线Blink—> Paint -> Commit ->(Tiling ->) Raster -> Activate -> Draw(Submit) —>VizBlink对接 cc 的绘制接口进行 Paint，Paint生成cc模块的数据源（cc::Layer），CC将数据源进行合成，经过一系列过程最终在 Draw 阶段将合成的结果(viz......
  • 数据结构之散列表与哈希函数初识
    一：概述一：为什么需要散列表*在我们的程序世界里，往往也需要在内存中存放这样一个“词典”，方便我们进行高效的查询和统计。*例如开发一个学生管理系统，需要有*通过输入学号快速查找对应学生的姓名的功能。*这里不必要每次都去查询数据库，而可以在内存中建立一个缓存表，这样做可以......
  • 数据结构与算法-cnblog
    数据结构与算法课程笔记树与二叉树树的深度与高度高度就可以理解为深度看层数：如果根结点第0，层数=深度=高度-1如果根结点第1，层数=深度=高度深度定义是从上往下的，高度定义是从下往上的......
  • Python数据结构——栈
    栈（Stack）是一种基本的数据结构，它遵循“后进先出”（Last-In-First-Out，LIFO）的原则，即最后放入栈的元素最先出栈。栈常用于管理函数调用、表达式求值、括号匹配等问题。本文将详细介绍Python中栈数据结构的使用，并提供示例代码来说明。什么是栈？栈是一种线性数据结构，它由一组元素组成，支持两......
  • 万字长文 | 业内 MySQL 线程池主流方案详解 - MariaDB/Percona/AliSQL/TXSQL/MySQL企
    作者：卢文双资深数据库内核研发本文首发于2023-05-0422:07:40http://dbkernel.com/2023/05/04/mysql-threadpool-main-solutions-details/#本文主要从功能层面对比percona-server、mariadb、阿里云AliSQL、腾讯TXSQL、MySQL企业版线程池方案，都基于MySQL8.0。至于源......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99