精华内容
下载资源
问答
  • 循环队列–C语言实现–数据结构

    万次阅读 多人点赞 2017-06-22 16:36:45
    循环队列–C语言实现–数据结构目录循环队列C语言实现数据结构目录 要求 二 循环队列循环队列的算法设计 1 建立循环队列 2 置空队列 3 入队 4 出队 5 打印队 四 程序 1 程序的结构 2 程序源码 五 程序测试 1 ...

    循环队列–C语言实现–数据结构


    目录


    (一) 要求

    假设以数组sequ[m]存放循环队列的元素,同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示:队空的条件:sq->quelen==0;队满的条件:sq->quelen==m。


    (二) 循环队列

    定义:为充分利用向量空间,克服”假溢出”现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表的方式来在实际编程应用中来实现, 当然也可以利用顺序表来实现。顺序表就是我们熟悉的数组 eg. sun[]
    回顾:我们再来回顾一下关于顺序队列的重要知识点。队列通常与栈对应,栈是一种后进先出的单端(尾端)处理的数据结构;那么与之对应的队列是一种先进先出的双端(头尾两端)的数据结构。队列的特点就是在一段进行入队(存储数据)操作,在另一端进行出队(删除数据)操作。
    为什么设计循环队列:大家在处理队列的时候,会遇到如下情况。例如说:我们的队列空间能够容纳1000个元素。首先,格格入队1000个元素,队列上溢,此时为“真溢出”。那么现在我们进行出队操作,我们一直出队,一直出队, 知道1000个元素全部被删除,此时我们发现队列仍然处于“上溢”状态,why? 其实原因很简单,在非循环队列当中,无论我们的front指(偏移)到哪里,只要我们的rear指(偏移)向上阙,那么队列就是“满溢”的。这就造成了空间明明还被占据着,但是队列却已经无用武之地的窘境。对于空间有限的计算机来说,这无疑是一种浪费。也不是一个优秀的程序猿想要看到的。所以在这种情况下,循环队列诞生了。循环队列当中的“满溢”只有一种情况,那就是所有数据空降都被占领了。而不会存在非循环队列当中的“假溢出”现象。


    我们所常见的顺序循环队列通常有两种数据结构。

    结构一

    typedef struct
    {
        datatype sequ[m];
        //sequ[]为我们所建立的顺序表(sequence)
        int  front,rear;
        //front表示队列头的偏移量,rear表示队列的尾的偏移量
    }qu;//qu是队列(queue)的缩写

    这里写图片描述

    结构二

    typedef struct
    {
        datatype sequ[m];
        //sequ[]为我们所建立的顺序表(sequence)
        int  rear, quelen;
        //rear表示队列的尾的偏移量,quelen表示的是队列中元素的个数
    }qu;//qu是队列(queue)的缩写

    那通过观察这两种机构我们能够很容易的发现,数据结构并不是固定的。我们觉得那种算法比较更合理,我们觉得哪种数据结构方便我们设计算法,那么我们就建立哪种数据结构。在本文当中,我们采用第二种数据结构。显而易见的是,当我们采用第二种数据结构时,我们建立的一个队列指针(qu*sq)队空的条件:sq->quelen==0;队满的条件:sq->quelen==m。


    (三) 循环队列的算法设计


    在上面我们了解了循环队列的数据机构,但是仅仅学会了数据结构还远远不够。我们设计数据结构的目的是为了更好的存储数据,并利用数据。下面我们来看一看关于循环队列我们要掌握哪些最基本的算法(利用数据机构)。


    3.1 建立循环队列

    //建立队
    qu* creatqueue();//函数声明
    qu* creatqueue()//函数实现
    {
        qu *sq;
        sq=(qu*)malloc(sizeof(qu));
        return sq;  
    }

    3.2 置空队列

    //置空队
    void setnull(qu*);//函数声明
    void setnull(qu *sq)//函数实现
    {
        sq->rear = m - 1;
        sq->quelen = 0;
    }

    3.3 入队

    //入队
    void enqueue(qu*, datatype);//函数声明
    void enqueue(qu*sq, datatype x)//函数实现
    {
        if (sq->quelen == 5)
            printf("Errot! The queue will be overflow! \n");
        else if((sq->rear+1)==m)
        {
            sq->rear = (sq->rear + 1) % m;
            sq->sequ[sq->rear] = x;
            sq->quelen++;
            printf("过5入队成功!\n");
        }
        else
        {
            sq->rear++;
            sq->sequ[sq->rear] = x;
            sq->quelen++;
            printf("入队成功!\n");
        }
    }

    **算法流程图**


    3.4 出队

    //出队
    datatype *dequeue(qu*);//函数声明
    datatype *dequeue(qu*sq)//函数实现
    {
        datatype sun=0;
        if (sq->quelen == 0)
        {
            printf("Error! The queue will be under flow!\n");
            return 0;
        }
        else if ((sq->rear + 1) >= sq->quelen)
        {
            sq->quelen--;
            sun = sq->sequ[sq->rear - sq->quelen];
            return(&sun);
        }
        else    //  if(sq->rear < sq->quelen)
        {
            sq->quelen--;
            sun = sq->sequ[sq->rear - sq->quelen + m];
            return(&sun);
        }
    }
    

    **算法流程图**


    3.5 打印队

    //打印队
    void print(qu*);//函数声明
    void print(qu*sq)//函数定义
    {
        if (sq->quelen == 0)
            printf("Error! The queue is Null!\n");
        else if ((sq->rear + 1) >= sq->quelen)
        {
            int i = sq->rear + 1 - sq->quelen;
            for (i; i <= sq->rear; i++)
                printf("%d   ", sq->sequ[i]);
        }
        else
        {
            int t = sq->rear - sq->quelen + m +1;
            int time = 1;
            for (t; time <= (sq->quelen); time++)
            {
                printf("%d   ", sq->sequ[t]);
                t++;
                if (t == m)
                {
                    t = 0;
                    continue;
                }
                else
                {
                    continue;
                }
            }
        }
        printf("\n");
    }

    (四) 程序


    下面我们来设计一个程序测试我们的数据机构与算法


    4.1 程序的结构

    **程序结构**


    4.2 程序源码

    注意:该程序由Microsoft Visual Studio Enterprise 2015编译器进行调试。受制于编译器品牌及版本不同等不可抗因素造成的编译失败,请自行调整。

    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #define m 5
    
    //循环队列的结构类型定义
    typedef int datatype;
    typedef struct
    {
        datatype sequ[m];
        int  rear, quelen;
    }qu;
    
    //函数声明
    qu* creatqueue();
    void setnull(qu*);
    void enqueue(qu*, datatype);
    datatype *dequeue(qu*);
    void print(qu*);
    
    //主函数
    void main()
    {
        qu *sq= creatqueue();
    
        datatype x, *p;
        int key;
    
        setnull(sq);
        do
        {
            printf("1.Enter Queue   2.Delete Queue   3.clc display   4.print queue   -1.Quit:");
            scanf_s("%d", &key);
            switch (key)
            {
            case 1:  printf("Enter the Data:"); scanf_s("%d", &x);
                enqueue(sq, x);  break;
            case 2:  p = dequeue(sq);
                if (p != NULL) printf("%d\n", *p);
                break;
            case 3:system("cls"); break;
            case 4:print(sq); break;
            case -1: exit(0);
            }
        } while (1);
    }
    
    //建立队
    qu* creatqueue()
    {
        qu *sq;
        sq=(qu*)malloc(sizeof(qu));
        return sq;  
    }
    //置空队
    void setnull(qu *sq)
    {
        sq->rear = m - 1;
        sq->quelen = 0;
    }
    
    //入队
    void enqueue(qu*sq, datatype x)
    {
        if (sq->quelen == 5)
            printf("Errot! The queue will be overflow! \n");
        else if((sq->rear+1)==m)
        {
            sq->rear = (sq->rear + 1) % m;
            sq->sequ[sq->rear] = x;
            sq->quelen++;
            printf("过5入队成功!\n");
        }
        else
        {
            sq->rear++;
            sq->sequ[sq->rear] = x;
            sq->quelen++;
            printf("入队成功!\n");
        }
    }
    
    
    //出队
    datatype *dequeue(qu*sq)
    {
        datatype sun=0;
        if (sq->quelen == 0)
        {
            printf("Error! The queue will be under flow!\n");
            return 0;
        }
        else if ((sq->rear + 1) >= sq->quelen)
        {
            sq->quelen--;
            sun = sq->sequ[sq->rear - sq->quelen];
            return(&sun);
        }
        else    //  if(sq->rear < sq->quelen)
        {
            sq->quelen--;
            sun = sq->sequ[sq->rear - sq->quelen + m];
            return(&sun);
        }
    }
    
    //打印队列
    void print(qu*sq)
    {
        if (sq->quelen == 0)
            printf("Error! The queue is Null!\n");
        else if ((sq->rear + 1) >= sq->quelen)
        {
            int i = sq->rear + 1 - sq->quelen;
            for (i; i <= sq->rear; i++)
                printf("%d   ", sq->sequ[i]);
        }
        else
        {
            int t = sq->rear - sq->quelen + m +1;
            int time = 1;
            for (t; time <= (sq->quelen); time++)
            {
                printf("%d   ", sq->sequ[t]);
                t++;
                if (t == m)
                {
                    t = 0;
                    continue;
                }
                else
                {
                    continue;
                }
            }
        }
        printf("\n");
    }
    
    

    (五) 程序测试


    5.1 入队列

    **入队列及上溢检测**


    5.2 出队列

    出队列及下溢检测


    5.3 打印队列

    前面已经用到了打印队列,所以格格不再赘述,大家由5.2&5.3可知打印队列是成功的。


    (六) 源程序及封装软件下载

    下载地址


    格格是一枚智能专业的本科在校生,很愿意和各位大佬交流。如果大家有愿意交朋友的,可以加格格的QQ:446019725,声明是CSDN即可。



    展开全文
  • 准备写队列以下几类型:循环队列(顺序结构),链队列,循环队列(只有尾指针),字符队列(顺序结构循环队列循环队列存储结构typedef int QElemType; typedef struct{ QElemType *base; int front; int...

    准备写队列以下几种类型:循环队列(顺序结构),链队列,循环队列(只有尾指针),字符队列(顺序结构)


    一、循环队列

    循环队列存储结构

    typedef int QElemType;
    typedef struct{
        QElemType *base;
        int front;
        int rear;
    }SqQueue;
    

    实现循环语句

    可以把循环队列想象成一个圈

    这里写图片描述

    因为循环队列假如是数据能占所有位置,那么队满或者对空的语句都是front==rear,这样就不能判断了,所以需要空出一个位置出来即mansize-1个位置

    插入队列实现循环语句:Q.rear=(Q.rear+1)%maxsize;

    删除队头实现循环语句:Q.front=(Q.front+1)%maxsize;

    判断队列满:(Q.rear+1)%maxsize==Q,front;

    判空:Q.front==Q.rear;

    注意:Q.front和Q.rear是指下标,例如取第一个元素值:Q.base[Q.front];

    demo

    #include <stdio.h>
    #define Maxsize 100
    typedef int QElemType;
    typedef struct{
        QElemType *base;
        int front;
        int rear;
    }SqQueue;
    int count=0;
    SqQueue QueueInit(SqQueue s)
    {
        s.base=(QElemType *)malloc(Maxsize*sizeof(QElemType));
        if(!s.base)
            printf("error");
        else{
            s.front=s.rear=0;
        }
        return s;
    }
    
    SqQueue InsertQueue(SqQueue s,QElemType e)
    {
        if((s.rear+1)%Maxsize==s.front)
            printf("error");
        else{
            s.base[s.rear]=e;
            s.rear=(s.rear+1)%Maxsize;
        }
        count++;
        return s;
    }
    
    SqQueue OutQueue(SqQueue s)
    {
        int e;
        if(s.rear==s.front)
            printf("error");
        else{
            e=s.base[s.front];
            s.front=(s.front+1)%Maxsize;
        }
        printf("%d",e);
        count--;
        return s;
    }
    
    int main()
    {
        SqQueue s,p;
        int e,i;
        s=QueueInit(s);
        for(i=0;i<4;i++)
        {
            s=InsertQueue(s,i+1);
        }
        p=s;
        for(i=0;i<count;i++)
        {
            printf("%d ",p.base[p.front]);
            p.front=(p.front+1)%Maxsize;
        }
        printf("\n");
        s=OutQueue(s);
        printf("\n");
        p=s;
        for(i=0;i<count;i++)
        {
            printf("%d ",p.base[p.front]);
            p.front=(p.front+1)%Maxsize;
        }
        return 0;
    }
    

    二、链队列

    存储结构

    typedef int QElemType;
    typedef struct QLNode{
        QElemType data;
        struct QLNode *next;
    }QNode,*QueuePtr;
    
    typedef struct{
        QueuePtr front;
        QueuePtr rear;
    }LinkQueue;
    

    demo

    #include <stdio.h>
    #include <malloc.h>
    typedef int QElemType;
    typedef struct QLNode{
        QElemType data;
        struct QLNode *next;
    }QNode,*QueuePtr;
    
    typedef struct{
        QueuePtr front;
        QueuePtr rear;
    }LinkQueue;
    
    void InitQueue(LinkQueue *Q)
    {   //printf("ss");
        Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));
       // printf("ss");
        Q->front->next=NULL;
    }
    
    void InsertQueue(LinkQueue *Q,int e)
    {
        QueuePtr p;
        p=(QueuePtr)malloc(sizeof(QNode));
        p->data=e;
        p->next=NULL;
        Q->rear->next=p;
        Q->rear=p;
    
    }
    
    void OutQueue(LinkQueue *Q)
    {
        QueuePtr p;
        int e;
        if(Q->front==Q->rear)
            printf("error");
        p=Q->front->next;
        e=p->data;
        Q->front->next=p->next;
        printf("%d",e);
        if(Q->rear==p)
            Q->rear=Q->front;
        free(p);
    
    }
    
    int main()
    {
        LinkQueue Q;
        QueuePtr p;
        int i;
        //printf("s");
        InitQueue(&Q);
        //printf("s");
        for(i=0;i<4;i++)
        {
            InsertQueue(&Q,i+1);
        }
       // printf("s");
        p=Q.front->next;
        for(i=0;i<4;i++)
        {
            printf("%d ",p->data);
            p=p->next;
        }
        printf("\n");
        OutQueue(&Q);
        printf("\n");
        p=Q.front->next;
         for(i=0;i<3;i++)
        {
            printf("%d ",p->data);
            p=p->next;
        }
        return 0;
    }
    

    三、循环队列(只有尾指针)

    这个问题即用链式存储结构

    存储结构

    typedef int QElemType;
    typedef struct Lnode{
        int data;
        struct Lnode *next;
    }Node,*SqQueue;
    

    demo

    #include <stdio.h>
    #include <malloc.h>
    #define Maxsize 100
    typedef int QElemType;
    typedef struct Lnode{
        int data;
        struct Lnode *next;
    }Node,*SqQueue;
    int count=0;
    SqQueue QueueInit(SqQueue rear)
    {
        rear=(SqQueue)malloc(sizeof(Node));
        if(!rear)
            printf("error");
        else{
            rear->next=rear;
        }
        return rear;
    }
    
    SqQueue InsertQueue(SqQueue rear,QElemType e)
    {
        SqQueue p;
        p=(SqQueue)malloc(sizeof(Node));
        p->data=e;
        p->next=rear->next;
        rear->next=p;
        rear=p;
        count++;
        return rear;
    }
    
    SqQueue OutQueue(SqQueue rear)
    {
        int e;
        SqQueue p;
        if(rear==rear->next)
            printf("error");
        else{
            p=rear->next->next;
            e=p->data;
            rear->next->next=p->next;
            if(rear==p)
            {
                rear=rear->next;
            }
            free(p);
        }
        printf("%d",e);
        count--;
        return rear;
    }
    
    int main()
    {
        SqQueue rear,p,q;
        int e,i;
        rear=QueueInit(rear);
        for(i=0;i<4;i++)
        {
            rear=InsertQueue(rear,i+1);
        }
        p=rear->next->next;
        for(i=0;i<4;i++)
        {
            printf("%d ",p->data);
            p=p->next;
        }
        printf("\n");
        rear=OutQueue(rear);
        printf("\n");
        q=rear->next->next;
        for(i=0;i<3;i++)
        {
            printf("%d ",q->data);
            q=q->next;
        }
        return 0;
    }
    

    四、字符队列(顺序结构)

    字符队列和普通没什么区别,但最重要一点就是字符输入时,会把空格或回车也放入缓存区,导致我想输入4个字符,却只能输入两个,解决办法就是加getchar();


    demo

    #include <stdio.h>
    #define Maxsize 1000
    typedef char QElemType;
    typedef struct{
        QElemType *base;
        int front;
        int rear;
    }SqQueue;
    int count=0;
    SqQueue QueueInit(SqQueue s)
    {
        s.base=(QElemType *)malloc(Maxsize*sizeof(QElemType));
        if(!s.base)
            printf("error");
        else{
            s.front=s.rear=0;
        }
        return s;
    }
    
    SqQueue InsertQueue(SqQueue s,QElemType e)
    {
        if((s.rear+1)%Maxsize==s.front)
            printf("error");
        else{
            s.base[s.rear]=e;
            s.rear=(s.rear+1)%Maxsize;
            count++;
        }
    
        return s;
    }
    
    SqQueue OutQueue(SqQueue s)
    {
        char e;
        if(s.rear==s.front)
            printf("error");
        else{
            e=s.base[s.front];
            s.front=(s.front+1)%Maxsize;
            count--;
        }
        printf("%c",e);
        return s;
    }
    int main()
    {
        SqQueue s,p;
        char a;
        int i;
        int l;
    
        s=QueueInit(s);
        for(l=0;l<4;l++)
        {
            scanf("%c",&a);
            getchar();//注意
            s=InsertQueue(s,a);
        }
        p=s;
        for(i=0;i<4;i++)
        {
            printf("%c",p.base[p.front]);
            p.front=(p.front+1)%Maxsize;
        }
        return 0;
    }
    
    展开全文
  • 数据结构循环队列

    千次阅读 2017-12-26 17:54:23
    今天学习循环队列,在学习循环队列之前,我们得先知道什么是队列呀,然后才可以继续往下学习。 首先我们回顾下队列的相关知识。 队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。 ...

    继续学习数据结构。今天学习循环队列,在学习循环队列之前,我们得先知道什么是队列呀,然后才可以继续往下学习。

    首先我们回顾下队列的相关知识。

    队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。

    队列是一种先进先出的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端称为队头。


    队列同样是一种线性表,队列也有类似线性表的各种操作,不同的是插入的数据是在队尾进行,删除数据只能在队头进行。

    那么我们同样可以使用顺序存储结构去实现队列。试想下我们使用使用数组进行队列的插入删除操作,会有什么效果呢?

    如果我们将队列的元素限制在数组的前n个单元,那么在队尾追加元素不需要移动任何元素,时间复杂度O(1),但是从队头也就是下标为0删除一个元素,每个元素都要向前移动一个位置,时间复杂度为O(n)。

    当然也可以不将队头设置在下标为0的位置,队头队尾用动态指针进行指向,删除元素后front指针指向数组中间时,继续添加元素队尾指针会指向队外了,虽然数组还有空闲元素,但是显示队列已满,这种就是假溢出。就好比我们上公交车,上车后,发现车后面没有位置,但是前面还有位置,难道我们还得下去么,我们肯定会去前面找位置坐下呗。

    所以解决假溢出的办法就是后面满了,就再从头开始,也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列那么此时问题又来了,当空队列时,front=rear,现在队列满了front=rear,那么如何判断此时的队列究竟是空还是满呢?

    这里有2种方法

    方法一:设置标志位,flag,当front=rear,且flag= 0时为队列为空,当front=rear,且flag=1时为队列满。

    方法二:front=rear时队列为空,当队列满时,我们修改其条件,保留一个元素空间,也就是说,队列满时,数组中还有一个空闲单元。不允许出现将数组全部填充满。如图:


    删除3个元素又添加3个元素后的指向


    我们重点来讨论第二种方法。当队列满的时候,rear可能比front大,也可能比front小(当rear超圈时)。队列满的条件是(rear+1)%QueueSize == front.我们继续看一下队列的长度(队列中元素的个数)当rear>front是时,队列的长度为rear-front,当rear<front时,队列长度 = QueueSize-front + rear – 0 = rear-front + QueueSize 可改成通用(rear-front+QueueSize)/QueueSize  

    知道上面的知识后,现在来实现循环队列的代码就不难了。

    循环队列的顺序存储结构代码:

    typedef structSeqQueue

    {

             EleType data[QUEUESIZE];

             int front;//头结点下标

             int rear;//尾结点下标

    } SeqQueue;

    下面是整个的代码:

    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <stdlib.h>
    #define QUEUESIZE 10
    #define ERROR 0 
    #define OK 1 
    #define TRUE 1 
    #define FALSE 0
    #define EleType int 
    #define Status int
    //循环队列数据结构
    typedef struct SeqQueue 
    {
    	EleType data[QUEUESIZE];
    	int front;//头结点下标
    	int rear;//尾结点下标
    } SeqQueue;
    /*
    初始化循环队列
    */
    Status InitSeqQueue(SeqQueue* queue)
    {
    	if (!queue)
    	{
    		return ERROR;
    	}
    	queue->front = queue->rear = 0;
    	return OK;
    }
    /*
    清空队列
    */
    Status ClearSeqQueue(SeqQueue* queue)
    {
    	if (!queue)
    	{
    		return ERROR;
    	}
    	queue->front = queue->rear = 0;
    	return OK;
    }
    /*
    判断循环队列是否为空
    */
    Status EmptySeqQueue(SeqQueue* queue)
    {
    	if (!queue)
    	{
    		return ERROR;
    	}
    	if (queue->front == queue->rear)
    	{
    		return TRUE;
    	}
    	return FALSE;
    }
    /*
    循环队列的元素个数
    */
    int LengthSeqQueue(SeqQueue* queue)
    {
    	if (!queue)
    	{
    		return ERROR;
    	}
    	if (queue->front == queue->rear)
    	{
    		return 0;
    	}
    	//留的那个空单元不算做元素个数 
    	return (queue->rear - queue->front + QUEUESIZE)% QUEUESIZE;
    }
    /*
    获取循环队列头元素
    */
    Status GetHead(SeqQueue* queue)
    {
    	if (!queue)
    	{
    		return ERROR;
    	}
    	if (queue->front == queue->rear)
    	{
    		return ERROR;
    	}
    	return queue->data[queue->front];
    }
    /*
    往队尾添加元素
    */
    Status AddQueue(SeqQueue* queue,EleType e)
    {
    	//队满或空指针
    	if (!queue)
    	{
    		return ERROR;
    	}
    	//刚好队尾再走一个单元就到队头,说明栈满了。
    	if ((queue->rear + 1) % QUEUESIZE == queue->front)
    	{
    		return ERROR;
    	}
    	queue->data[queue->rear] = e;
    	queue->rear = (queue->rear + 1) % QUEUESIZE;//若到队尾转到数组头部
    	return OK;
    }
    /*
    队头删除元素
    */
    Status DelQueue(SeqQueue* queue,EleType *e)
    {
    	//空指针
    	if (!queue)
    	{
    		return ERROR;
    	}
    	//队空
    	if (queue->front == queue->rear)
    	{
    		return ERROR;
    	}
    	*e = queue->data[queue->front];
    	queue->front = (queue->front + 1) % QUEUESIZE;//若到队尾转到数组头部
    	return OK;
    }
    void PrintfQueue(SeqQueue* queue)
    {
    	//空指针
    	if (!queue)
    	{
    		return ERROR;
    	}
    	//队空
    	if (queue->front == queue->rear)
    	{
    		return ERROR;
    	}
    	int begin = queue->front;
    	while (begin!=queue->rear)
    	{
    		printf("%d,", queue->data[begin]);
    		if (begin < QUEUESIZE-1)
    		{
    			begin++;
    		}
    		else
    		{
    			begin = begin + 1 - QUEUESIZE;
    		}
    
    	}
    	printf("\n");
    	return;
    }
    int main(int argc, char *argv[])
    {
    	SeqQueue queue;
    	InitSeqQueue(&queue);
    	AddQueue(&queue, 1);
    	AddQueue(&queue, 2);
    	AddQueue(&queue, 3);
    	AddQueue(&queue, 4);
    	AddQueue(&queue, 5);
    	AddQueue(&queue, 6);
    	AddQueue(&queue, 7);
    	AddQueue(&queue, 8);
    	AddQueue(&queue, 9);
    	printf("展示队列元素:");
    	PrintfQueue(&queue);
    	printf("队列元素个数:%d\n", LengthSeqQueue(&queue));
    	EleType e1, e2;
    	DelQueue(&queue, &e1);
    	printf("删除队头元素:%d\n", e1);
    	DelQueue(&queue, &e2);
    	printf("删除队头元素:%d\n", e2);
    	printf("现在的队头元素:%d\n", GetHead(&queue));
    	printf("展示队列元素:");
    	PrintfQueue(&queue);
    	printf("队列元素个数:%d\n", LengthSeqQueue(&queue));
    	AddQueue(&queue, 10);
    	AddQueue(&queue, 11);
    	printf("继续添加2个元素10,11\n");
    	printf("展示队列元素:");
    	PrintfQueue(&queue);
    	//此时 front指向下标为2的元素,rear指向下标为1的元素
    	printf("front:%d,rear:%d\n", queue.front, queue.rear);
    
    	return 0;
    }
    



    验证结果截图:


    这样循环队列就不用像顺序存储的线性表那样频繁的移动元素位置,而在用通过下标的移动和循环来操作。这样时间性能比较高。但是仍然面临的是顺序存储结构都会面临的问题数组长度不够的情况。

    展开全文
  • 循环队列的顺序存储结构Java

    千次阅读 2019-12-19 16:33:54
    循环队列的顺序存储结构 在上次,我们讲到的是,队列的顺序存储结构也是由ArrayList实现的,从此就可以看出,在入队时候的时间复杂度为O(1),但是在出队时候的时间复杂度为O(n),这是因为,每次在出队后要将数组后面...

    循环队列的顺序存储结构

    在上次,我们讲到的是,队列的顺序存储结构也是由ArrayList实现的,从此就可以看出,在入队时候的时间复杂度为O(1),但是在出队时候的时间复杂度为O(n),这是因为,每次在出队后要将数组后面的有效元素前移一位
    所以,这里就会用到循环队列,显然,这种队列也是顺序存储结构,在这个循环队列中也会去实现接口Queue。
    首先,我们要想到的是如何将一般的队列改变为循环队列。

    • 和之前一般的队列的顺寻存储结构一样,默认初始数组容量为10(循环队列的数组实际容量为11,这是因为要空出一个数组空间,至于为什么,将在后面进行解释);
    • 定义一个头指针front和尾指针rear,用这两个指针去维护循环队列中元素的入队和出队;
    • 定义一个size,去统计当前循环队列中的元素的有效个数;

    现在,我们先看一下循环队列是如何入队和出队的。
    初始时:
    在这里插入图片描述

    入队一个元素:
    在这里插入图片描述

    出队一个元素:
    在这里插入图片描述
    这样,front和rear指针就可以很轻松的去维护循环队列的入队和出队,并且它们的时间复杂度都为O(1),但是要注意特殊情况的存在,比如,当数组的0角标没有元素但7角标也有元素的时候,rear指针就要移动到front的前面,如下图所示:

    在这里插入图片描述

    这个时候很明显,循环队列已经满了,所以我们就会想到,如何判断循环队列什么时候为满,什么时候为空?

    其实,利用它的周期性可以很明显的得出结论:
    队列为满的时候:(rear+1)%n == front; (n为数组的总长度;如上图:(0+1)%8等于1也就是等于front指向的位置)
    如果出现这种情况,如下图示:
    在这里插入图片描述

    因为,我们每次的出队,front指针都会向后面移动一位,而rear指针是不会移动的,如果我们将上图的两个元素全部出队列,会出现这样的情况:
    在这里插入图片描述

    很显然,判断队列为空也为:(rear+1)%n == front;

    这样的话就会重复,所以这就是我们之前说,为什么要在创建循环队列数组的时候多创建一个元素空间的原因了。
    因此,判断队列为空的条件就为:rear == front;
    如下图:
    在这里插入图片描述

    如上图,我们现在入队一个元素:
    在这里插入图片描述

    每次在入队的时候,将rear指针始终指向队尾最后一个元素的空间。
    并且每次入队的时候,rear的变化也要注意:rear = (rear+1)%n;

    说了这么多,我们就来看一下具体的代码实现。
    首先和我们之前一样,先来看看它的顺序存储结构:

    package DS01.动态数组;
    import java.util.Iterator;
    /**
     * @author 七夏
     * @param <E>
     * @version 1.0
     * 循环队列:如果我们默认创建一个为容量为10的的循环队列时,我们须在该循环队列容量的基础上再加1,
     * 这是为了在判断循环队列是否为空时,起到作用
     *
     * 循环队列为满时的条件:(rear+1)%data.length 等于 front
     * 循环队列为空时的条件:front == rear
     * 元素每次进队时,队头front每次更新:front = (front+1)%data.length
     * 元素每次出队时,队尾rear每次更新:rear = (rear+1)%data.length
     * 函数 E getRear() 在获取队尾元素时的方法为:data[(rear-1+data.length)%data.length]
     */
    public class ArrayQueueLoop<E> implements Queue<E>{
    	//设置默认初始容量(后面会加1)
        private static final int DEFAULT_CAPACITY = 10;
        private E[] data;
        private int front;
        private int rear;
        private int size;
    
        public ArrayQueueLoop(){
            this(DEFAULT_CAPACITY);
        }
        public ArrayQueueLoop(int capacity){
            if(capacity <= 0){
                throw new IllegalArgumentException("指定容量错误:"+capacity);
            }
            data = (E[])(new Object[capacity+1]);//加1,让数组多出一个空间
            front = 0;
            rear = 0;
            size = 0;
        }
    }
    

    现在,看一下入队代码:

    	@Override
        public void enqueue(E e) {
        	//判断队列是否满
            if((rear + 1)%data.length == front){
                //扩容
                resize(data.length*2-1);
            }
            data[rear] = e;
            //更新rear队尾指针位置
            rear = (rear+1)%data.length;
            size++;
        }
    

    出队:

    	@Override
        public E dequeue() {
            if(isEmpty()){
                throw new IllegalArgumentException("队列为空");
            }
            //拿出对头元素
            E res = data[front];
            //更新front对头指针位置
            front = (front+1)%data.length;
            size--;
            //缩容
            if(size <= (data.length-1)/4 && (data.length-1)/2 >= 10){
                resize(data.length/2+1);
            }
            return res;
        }
    

    扩容:

    	private void resize(int newLen) {
            E[] newData = (E[])(new Object[newLen]);
            int p = front;
            int i = 0;
            while(true){
                newData[i] = data[p];
                i++;
                p = (p+1)%data.length;
                //如果p指针等于rear队尾指针时,结束循环
                if(p == rear){
                    break;
                }
            }
            /*
            上述while循环相当于下述for循环
            for(int i = 0,p = front;p != rear;i++,p = (p+1)%data.length){
    			newData[i] = data[p];
    		}
            */
            front = 0;
            rear = size;
            data = newData;
        }
    

    实现iterator方法:
    和之前都大致类似,在这里,我们在内部类中首先定义一个p指针,用来遍历循环队列,在hasNext函数中,只要p指针不等于rear队尾指针,说明该循环队列“尚不为空”(当前指向的元素后面还有元素);next函数中,创建res变量获取当前元素,之后将更新p指针的位置,最终返回res。

    	@Override
        public Iterator<E> iterator() {
            return new ArrayQueueLoopIterator();
        }
        private class ArrayQueueLoopIterator implements Iterator<E>{
            int p = front;
            @Override
            public boolean hasNext() {
                return p != rear;
            }
    
            @Override
            public E next() {
                E res = data[p];
                //更新p指针的指向位置
                p = (p+1)%data.length;
                return res;
            }
        }
    

    其他方法:
    在这些方法中,我们要注意toString方法和getRear方法,在getRear方法中,我们直接返回data[(rear-1+data.length)%data.length]。

    	@Override
        public int getSize() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            return size == 0 && front == rear;
        }
        @Override
        public E getFront() {
            if(isEmpty()){
                throw new IllegalArgumentException("队列为空");
            }
            return data[front];
        }
    
        @Override
        public E getRear() {
            if(isEmpty()){
                throw new IllegalArgumentException("队列为空");
            }
            return data[(rear-1+data.length)%data.length];
        }
    
        @Override
        public void clear() {
            data = (E[])(new Object[DEFAULT_CAPACITY+1]);
            front = 0;
            rear = 0;
            size = 0;
        }
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append(String.format("ArrayQueue: %d/%d \n",getSize(),data.length-1));
            sb.append('[');
            if(isEmpty()){
                sb.append(']');
            }else{
                for (int i = front; i != rear; i = (i+1)%data.length) {
                    sb.append(data[i]);
                    if((i+1)%data.length == rear){
                        sb.append(']');
                    }else{
                        sb.append(',');
                    }
                }
            }
            return sb.toString();
        }
    
    展开全文
  • 数据结构-队列之循环队列

    千次阅读 2018-10-22 10:44:06
    将顺序队列臆造为个环状的空间,即把存储队列元素的表从逻辑上看成个环,称为循环队列。 当队首指针q.front=MaxSize-1后,再前进个位置就自动归0,可以通过除法取余运算(%)来实现。 初始时:q.front = q....
  • 线性结构_循环队列

    千次阅读 2017-03-19 15:42:34
    1、静态队列为什么必须是循环队列:队列的结构是先进先出的,循环队列可对内存重复使用,减少对内存的浪费。 2、循环队列需要几个参数来确定:2个参数:front和rear 3、循环队列各个参数的含义 这两个
  • 数据结构--循环队列

    千次阅读 2019-06-29 15:39:42
    文章目录顺序存储结构循环队列代码实现注意 顺序存储结构 所谓顺序存储结构就是用组地址连续的存储单元依次存放从队头到队尾的元素。 声明两个指针rear、front分别用来指示队尾元素的下位置和队头元素的位置。 ...
  • JAVA循环队列

    千次阅读 2017-09-15 15:25:44
    、JAVA 中已经自带了 Queue、DQueue、ArrayList、LinkedList 等常用的数据结构,为什么还要单独实现循环队列? 之所以使用自定义循环队列,出发点还是基于我们在实际应用中对于数据处理各种各样的需求。使用...
  • 循环队列是对队列的一种改进,它比队列适用的范围更广,例如Linux内核当中的环形缓冲区就是基于循环队列来设计的。本文主要任务是通过C语言来实现一个循环队列的数据结构,以及对循环队列的基本操作。 1、循
  • 数据结构与算法——循环队列

    千次阅读 2015-05-14 21:43:49
    今天总结循环队列什么是队列?  队列跟栈差不多,也是一种操作受限的线性表,只允许在线性表的一端进行插入操作,在另一端进行删除操作。插入的一端称为队尾,删除的一端...什么是循环队列?  循环队列就是,当
  • 队列,循环队列什么用空个元素的位置 队列介绍 1)队列是个有序列表,可以用数组或是链表表示。 2)遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出。 front及rear分别记录队列前后端...
  • 一种先进先出的线性表(FIFO)。允许插入的一端称为队尾,允许删除的一端称为队头。我们在《栈的顺序存储结构》中发现,栈操作的top指针在Push时增大而在Pop时减小,栈空间是可以重复利用的,而队列的front、rear...
  • 数据结构 第7讲 循环队列

    千次阅读 多人点赞 2018-04-09 11:02:31
    数据结构 第7讲 循环队列过了段时间,小张再也受不了这种"起早贪黑"的有车生活。为了解决胡同停车问题,小张跑了无数次居委会,终于将挡在胡同口的建筑清除,这样住在胡同尽头的小张,就可以早早回家停...
  • 1、也是一种操作受限的线性表,规定只能在一端插入,一端删除,有先进先出的特点。 2、顺序队列,队首指针指向队首元素,队尾指针指向队尾元素的前一个元素,此时队列为空的判定条件是 Q.front == Q.rear == 0; ...
  • 队列结构也是平时非常常见的一种受限的线性数据结构。它跟栈结构一样都是受限的数据结构,区别就是...数据结构——队列一什么是队列二、队列结构的方法三、用代码实现一个队列结构(1)创建一个构造函数(2)实现enq
  • 数据结构——循环队列PTA习题

    千次阅读 2020-12-17 23:39:58
    文章目录单选题题解函数题6-1 另类循环队列 (20分)输入样例:输出样例:代码6-2 双端队列 (25分)输入样例:输出样例:代码编程题7-1 堆栈模拟队列 (25分)输入格式:输出格式:输入样例:输出样例:代码模拟队列直接用...
  • 队列的顺序存储结构循环队列

    千次阅读 2016-11-12 10:31:54
    队列一种先进先出(First In First Out)的线性表,简称FIFO.允许插入的一端称为队尾,允许删除的一端称为队头。 队列的顺序存储结构使用数组的实现,假设数组长度为N,这时删除队头元素的时候,这个元素后面的每...
  • 【数据结构】设计循环队列

    千次阅读 2018-10-15 09:20:47
    循环队列一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通...
  • 数据结构循环队列C语言实现(详细)

    千次阅读 多人点赞 2020-05-25 23:59:25
    队列有两种,一种叫做循环队列(顺序队列),另一种叫做链式队列。 这一篇讲的是循环队列,链式队列在另外一篇文章中 循环数组 循环队列使用的是数组,但是这个数组比较特别,为循环数组。为什么要使用循环数组呢? ...
  • 循环队列及C语言实现<>

    千次阅读 2016-09-21 22:34:11
    循环队列是为了充分利用内存,进行数据操作的一种基本算法。具体实现方式可划分为:链式队列和静态队列,这里所谓的静态是指在一片连续的内存区域进行数据操作。本文只讲述静态队列,也是最简单的实现方式,静态队列...
  • 数据结构--java语言实现循环队列

    千次阅读 2019-05-24 22:29:42
    循环队列一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通...
  • 数据结构笔记3.3 顺序队列是用顺序表实现的(即依托于数组),这里实现的是循环队列... 为了能够充分利空间,所以用循环队列,即在逻辑上把数组的队结构看成个环。具体实现:实现的方式还是十分巧妙地,运用两个指
  • 一种先进先出(FIFO)的线性表,只允许在队尾进行插入,在队首进行删除 顺序存储的队列写起来跟顺序实现的栈很像,也是采用数组存储数据,但是在不断入队列和出队列过程中,数据会不断后移,所以会造成大量的空间...
  • 队列一种线性的数据结构【线性数据结构:数组、栈、队列】 相比数组,队列对应的数据操作是数组的子集。 只能从一端(队尾)添加元素,只能从另一端(队首)取出元素。   数组队列 代码实现 Array数组类 ...
  • 1.顺序队列的常用基本操作及条件判断 队空: Q.front=Q.rear 队满: Q.rear=Maxlen 求队长: Q.rear-Q.front 入队: 1)新元素按 rear 指示位置加入 2)rear = rear + 1队尾指针加一 出队: 1)将front...
  • 循环队列和链队列的比较
  • 队列也是线性表的一种特殊形式,它只允许在线性表的一端进行插入,而在另一端进行删除,也就是所谓的先入先出 用顺序存储的结构实现队列,假如队列有n个元素,则必须建立大于n的数组,因为队列要求在一端插入,而在...
  • 队列——顺序存储结构循环队列

    千次阅读 2013-05-31 11:27:16
    什么小甲鱼上节课说队列的实现上我们更愿意用链式存储结构来存储? 我们先按照应有的思路来考虑下如何构造队列的顺序存储结构,然后发掘都遇到了什么麻烦。 我们假设队列有n个元素,则顺序存储的队列需...
  • 【数据结构循环队列

    千次阅读 2017-03-16 16:55:34
    循环队列的设计是为了避免“虚溢出”的现象。所谓“虚溢出”是指在利用数组构建队列时,当尾指针指向数组末尾时,即便数组前端仍有剩余空间,但是却无法向队列中添加新元素的“虚假溢出”的现象。图示如下:循环队...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 187,082
精华内容 74,832
关键字:

循环队列是一种什么结构