精华内容
下载资源
问答
  • 循环队列定义及操作

    千次阅读 2017-05-21 18:32:15
    #include #include #define MAXSIZE 50 typedef struct { int element[MAXSIZE]; int front; //队头指示器 int rear; //队尾指示器 } SeqQueue;...//初始化操作,将Q初始化为一个空的循环队列 bool En
    #include <stdio.h>
    #include <malloc.h>
    #define MAXSIZE 50
    
    typedef struct
    {
        int element[MAXSIZE];
        int front; //队头指示器
        int rear;  //队尾指示器
    } SeqQueue;
    
    void InitQueue(SeqQueue *Q);//初始化操作,将Q初始化为一个空的循环队列
    bool EnterQueue(SeqQueue *Q,int x);//入队,将元素x入队
    bool DeleteQueue(SeqQueue *Q,int *x);//出队,删除队列的队头元素,用x返回其值
    
    int main(void)
    {
        SeqQueue S;
        SeqQueue *s=&S;
        int x;
        int *a=&x;
        InitQueue(s);
        for(int i=1; i<=10; i++)
            EnterQueue(s,i);
        for(int i=1; i<=10; i++)
        {
            DeleteQueue(s,a);
            printf("%d ",x);
        }
        printf("\n");
        return 0;
    }
    
    void InitQueue(SeqQueue *Q)//初始化操作,将Q初始化为一个空的循环队列
    {
        Q->front=Q->rear=0;
    }
    
    bool EnterQueue(SeqQueue *Q,int x)//入队,将元素x入队
    {
        if((Q->rear+1)%MAXSIZE==Q->front)//尾指针加一追上头指针,队列已满
            return false;
        Q->element[Q->rear]=x;
        Q->rear=(Q->rear+1)%MAXSIZE;
        return true;
    }
    
    bool DeleteQueue(SeqQueue *Q,int *x)//出队,删除队列的队头元素,用x返回其值
    {
        if(Q->front==Q->rear)//队列为空
            return false;
        *x=Q->element[Q->front];
        Q->front=(Q->front+1)%MAXSIZE;//重新设置队头指针
        return true;//操作成功
    }
    

    展开全文
  • 1.顺序队列的常用基本操作及条件判断 队空: Q.front=Q.rear 队满: Q.rear=Maxlen 求队长: Q.rear-Q.front 入队: 1)新元素按 rear 指示位置加入 ...2.顺序队列类型定义 #define ...

    1.顺序队列的常用基本操作及条件判断

    队空:    Q.front=Q.rear
     队满:    Q.rear=Maxlen
     求队长:  Q.rear-Q.front
    

    入队: 1)新元素按 rear 指示位置加入
    2)rear = rear + 1队尾指针加一
    出队: 1)将front指示的元素取出。
    2)front = front + 1队头指针加一
    2.顺序队列的类型定义

    #define MAXLEN 100
       typedef struct
        	{datatype  Q[MAXLEN];
        	  int front=0;
        	  int rear=0;
            } SeqQueue,*P;
    

    问:什么叫“假溢出” ?如何解决?
    答:在顺序队中,当尾指针已经到了数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫“假溢出”。
    解决假溢出的途径———采用循环列队

    循环队列

    想象为一个首尾相接的圆环,并称这种向量为循环向量,存储在其中的队列称为循环队列。在这里插入图片描述

    新问题:在循环队列中,空队特征是Q.front=Q.rear;队满时也会有Q.front=Q.rear;判决条件将出现二义性!
    解决方案有三:
    ①使用一个计数器记录队列中元素个数(即队列长度);
    ②加设标志位,删除时置1,插入时置0,则可识别当前Q.front=Q.rear属于何种情况
    ③ 人为浪费一个单元,则队满特征可改为Q.front=(Q.rear+1)%MAXLEN;

    实际中常选用方案3(人为浪费一个单元):
    即front和rear二者之一指向实元素,另一个指向空闲元素。

    队空条件 :  Q.front =Q. rear       (初始化时:Q.front = Q.rear )
    队满条件: Q.front = (Q.rear+1) % N         (N=maxsize)
    队列长度(即数据元素个数):L=(N+Q.rear-Q.front)% N
     
    

    在这里插入图片描述
    例1:数组Q[n]用来表示一个循环队列,f 为当前队列头元素的前一位置,r 为队尾元素的位置。假定队列中元素的个数小于n,计算队列中元素的公式为:
    A) r-f (B)(n+f-r)% n
    (C)n+r-f (D) (n+r-f)% n
    要分析4种公式哪种最合理?
    当 r ≥f 时(A)合理;
    当 r < f 时(C)合理; 综合2种情况,以(D)的表达最为合理
    例2:在一个循环队列中,若约定队首指针指向队首元素的前一个位置。那么,从循环队列中删除一个元素时,其操作是 先 移动队首指针,后取出元素
    在这里插入图片描述
    在这里插入图片描述

    怎样构成循环队列?
    在循环队列中进行出队、入队操作时,头尾指针仍要加1,朝前移动。
    只不过当头尾指针指向向量上界(MAXLEN-1)时,其加1操作的结果是指向向量的下界0。
    加1操作的结是指向向量的下界0的办法

    *(front+1)%M       (rear+1)%M*
    

    在这里插入图片描述

    队空:Q.front =Q. rear
    队满:Q.front =(Q.rear + 1) % MAXLEN
    入队: Q.rear = (Q.rear + 1) % MAXLEN
    出队: Q.front = (front + 1) % MAXLEN;
    求队长:(Q.rear-Q.front+ MAXLEN)% MAXLEN

    - 3)循环队列的类型定义

    #define MAXLEN 100
    typedef struct
    	{datatype *data[MAXLEN];
    	  int front;
    	  int rear;
         int n;/*判队空,队满的另一方法*/
       } CseqQueue
    

    - 4)循环队列操作的实现

    ①初始化队列

    CseqQueue * IniQueue (CseqQueue *Q) 
    {                                                    //构造空队列
      Q= (CseqQueue *) malloc(sizeof(CseqQueue ));
      Q->rear = Q->front = 0;
      return Q;
    }
    

    在这里插入图片描述
    ②判队空

    int QueueEmpty (CseqQueue *Q ) 
    {
        return(Q->rear == Q->front);
    }
    
    

    ③判队满

    int QueueFull (CseqQueue *Q ) 
    {
        return((Q->rear+1) % MAXLEN == Q->front);
    }
    

    ④判队满

    int QueueFull (CseqQueue *Q ) 
    {
        return( (Q->n) == MAXLEN);
    }
    

    ⑤入队

    int InQueue (CseqQueue *Q, datatype x ) 
    {
        if (QueueFull (Q) ) 
              return 0;
       else 
          {Q->data[Q->rear] = x; 
            Q->rear = ( Q->rear+1) % MAXLEN; 
            Q->n++;
            return 1;
          }
     }
    

    ⑥出队

    int DeQueue (CseqQueue *Q, datatype *x ) 
    {
        if ( QueueEmpty (Q) ) 
            return 0;
       else
           {*x = Q->data[Q->front]; 
             Q->front = ( Q->front+1) % MAXLEN; 
             Q->n--;
             return 1;
          }
    }
    

    ⑦取队头

    int GetFront (CseqQueue *Q, datatype *x ) 
    {
         if ( QueueEmpty (Q) )
              return 0;
         *x = Q->data[Q->front];
         return 1;
    }
    

    ⑧求队列长度

    int QueueLength (CseqQueue  *Q)
    {
      return( (Q->rear – Q->front + MAXSIZE) % MAXSIZE);
    }
    

    链队列结构

    (1)链队列结构**
    链队列示意图在这里插入图片描述
    (2)链队列的描述
    和顺序队列类似,我们也是将这两个指针封装在一起,将链队列的类型LinkQueue定义为一个结构类型:

    typedef struct queuenode
          { datatype  data;
             struct queuenode *next;
           }queuenode;
       typedef struct
          {  queuenode  *front;
              queuenode  *rear;
           }Linkqueue;
    

    3)链队列上实现的基本运算
    1)构造一个空队列(带头结点空队列)

      void initqueue(Linkqueue  *q)
         { q.front=(queuenode *)malloc(sizeof(queuenode));
           q.rear=q.front
           q.front->next=q.rear->next= NULL;
         }
    

    在这里插入图片描述
    2)入队操作
    在这里插入图片描述
    入队操作算法

    void inqueue(Linkqueue  *q,datatype  x)
         {queuenode *p
          p=(queuenode * )malloc(sizeof(queuenode));
          p–>data=x;
          p–>next=NULL;
          q.rear–>next=p;
          q.rear=p;
         }
    

    3)队列的判空

    int queueempty(Linkqueue  *q)
        {
          return (q.front->next= =NULL &&
                      q.rear->next= =NULL);
         }
    
    1. 出队操作在这里插入图片描述
      4)出队操作算法

    Datatype dequeue(Linkqueue *q)
    { datatype x;
    queuenode *p
    if(queueempty(q))
    { printf(“队列为空”); return;}
    p=q.front–>next;
    x=p–>data;
    q.front–>next=p–>next;
    if(q.rear = =p) /删除的是尾结点/
    q.rear=q.front;
    free§;
    return x;
    }

    有什么问题请留言 会及时修改的

    展开全文
  • 循环队列的基本定义 : 顺序存储结构定义: typedef struct{ QElemType *base; int Front,Rear; }CQueue;   循环队列的基本操作: 1、初始化一个队列 2、清空一个队列 3、判断一个队列是否为空 4、求...

    循环队列的基本定义 :

    顺序存储结构定义:

    typedef struct{
        QElemType *base;
        int Front,Rear;
    }CQueue;

     


    循环队列的基本操作:

    1、初始化一个队列

    2、清空一个队列

    3、判断一个队列是否为空

    4、求队列的长度

    5、入队列操作

    6、出队列操作

    7、取队头元素

    8、历遍操作


    1、初始化一个队列

    void InitCQueue(CQueue &Q){
        Q.base=new QElemType [QueueSize];
        Q.Front=Q.Rear=0;
    }

    2、清空一个队列

    void ClearCQueue(CQueue &Q){
        delete [] Q.base;
        InitCQueue(Q);
    }

    3、判断一个队列是否为空

    bool QueueEmpty(CQueue Q){
        return Q.Front==Q.Rear?true:false;
    }

    4、求队列的长度

    int QueueLength(CQueue Q){
        return (Q.Rear-Q.Front+QueueSize)%QueueSize;
    }

    5、入队列操作

    void EnQueue(CQueue &Q,QElemType e){
        if((Q.Rear+1)%QueueSize == Q.Front){
            printf("error !!! Queue is full !!!");return ;
        }
        Q.base[Q.Rear]=e;
        Q.Rear=(Q.Rear+1)%QueueSize;
    }

    6、出队列操作

    void DeQueue(CQueue &Q,QElemType &e){
        if(Q.Front==Q.Rear){
            printf("error !!! Queue is empty !!!");return ;
        }
        e=Q.base[(Q.Front)%QueueSize];
        Q.Front=(Q.Front+1)%QueueSize;
    }

    7、取队头元素

    void GetHead(CQueue Q,QElemType &e){
        if(Q.Front==Q.Rear){
            printf("error !!! Queue is empty !!!");return ;
        }
        e=Q.base[Q.Front];
    }

    8、历遍操作

    void QueueTraverse(CQueue Q){
        for(int i=Q.Front;i!=Q.Rear;i=(i+1)%QueueSize){
            printf("%d%c",Q.base[i],(i+1)%QueueSize==Q.Rear?'\n':' ');
        }
    }

    完整的调试代码:

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #define QElemType int
    #define QueueSize 11
    using namespace std;
    typedef struct{
        QElemType *base;
        int Front,Rear;
    }CQueue;
    
    void InitCQueue(CQueue &Q){
        Q.base=new QElemType [QueueSize];
        Q.Front=Q.Rear=0;
    }
    void ClearCQueue(CQueue &Q){
        delete [] Q.base;
        InitCQueue(Q);
    }
    bool QueueEmpty(CQueue Q){
        return Q.Front==Q.Rear?true:false;
    }
    int QueueLength(CQueue Q){
        return (Q.Rear-Q.Front+QueueSize)%QueueSize;
    }
    void EnQueue(CQueue &Q,QElemType e){
        if((Q.Rear+1)%QueueSize == Q.Front){
            printf("error !!! Queue is full !!!");return ;
        }
        Q.base[Q.Rear]=e;
        Q.Rear=(Q.Rear+1)%QueueSize;
    }
    void DeQueue(CQueue &Q,QElemType &e){
        if(Q.Front==Q.Rear){
            printf("error !!! Queue is empty !!!");return ;
        }
        e=Q.base[(Q.Front)%QueueSize];
        Q.Front=(Q.Front+1)%QueueSize;
    }
    void GetHead(CQueue Q,QElemType &e){
        if(Q.Front==Q.Rear){
            printf("error !!! Queue is empty !!!");return ;
        }
        e=Q.base[Q.Front];
    }
    void QueueTraverse(CQueue Q){
        for(int i=Q.Front;i!=Q.Rear;i=(i+1)%QueueSize){
            printf("%d%c",Q.base[i],(i+1)%QueueSize==Q.Rear?'\n':' ');
        }
    }
    int main()
    {
        CQueue Q;
        InitCQueue(Q);
        int e;
        if(QueueEmpty(Q)){
            for(int i=0;i<10;i++){
                //printf("%d\n",i);
                EnQueue(Q,i);
            }
        }
        printf("Front : %d Rear : %d\n",Q.Front,Q.Rear);
        //printf("%d\n",Q.base[0]);
    
        QueueTraverse(Q);
        for(int i=0;i<9;i++){
            DeQueue(Q,e);
            printf("%d %d %d  F: %d R: %d\n",i,e,QueueLength(Q),Q.Front,Q.Rear);
        }
        GetHead(Q,e);printf("%d\n",e);
    
        for(int i=0;i<4;i++){
            //printf("%d\n",i);
            EnQueue(Q,i);
        }
        printf("Front : %d  Rear : %d\n",Q.Front,Q.Rear);
        for(int i=0;i<3;i++){
            DeQueue(Q,e);
            printf("%d %d %d  F: %d R: %d\n",i,e,QueueLength(Q),Q.Front,Q.Rear);
        }
        ClearCQueue(Q);
        if(QueueEmpty(Q)){
            printf("Front : %d  Rear : %d\n",Q.Front,Q.Rear);
        }
    
        return 0;
    }
    

     

    展开全文
  • #include using namespace std; /*循环队列类型定义*/ const int Queue_Size=100; typedef struct circlQueue { char *elem; int rear;

    #include <iostream>
    using namespace std;
     
    /*循环队列的类型定义*/
    const int Queue_Size=100;
     
    typedef struct circlQueue
    {
           char *elem;
           int rear;
           int front;
           int queueSize;
    }circlQueue;
     
     
     
    /*初始化*/
    void initQueue_C(circlQueue &Q)
    {
           Q.elem=new char[Queue_Size];
           Q.front=Q.rear=0;//首尾指针相等说明队列为空。
           Q.queueSize=Queue_Size;
    }
     
     
     
    /*销毁队列*/
    void destroyQueue_C(circlQueue &Q)
    {
           delete []Q.elem;
           Q.front=Q.rear=0;
           Q.queueSize=0;
    }
     
     
     
     /*求队列的长度*/
    int  lengthQueue_C(circlQueue &Q)
    {
           int length;
           length=(Q.rear-Q.front+Q.queueSize)%Q.queueSize;/*一般情况下,rear在front的上方,此种算法是用于
      rear已到front的下方,即已出现假溢出的情况。*/
           return length;
    }
     
     
    /*入队列*/
    void enterQueue_C(circlQueue &Q,char x)
    {
           if(((Q.rear+1)%Q.queueSize)==Q.front)//判断栈满的情况
                  cout<<"Queue OverFlow!";
           Q.elem[Q.rear]=x;
           Q.rear=(Q.rear+1)%Queue_Size;//尾指针应以此种方式加1,才会实现循环队列。
    }
     
    /*出队列*/
    char outputQueue_C(circlQueue &Q)
    {
           char e;
           if(Q.rear==Q.front)
                  cout<<"Queue Empty";
           e=Q.elem[Q.front];
           Q.front=(Q.front+1)%Q.queueSize;;//头指针应以此种方式加1,才会实现循环队列。
           return e;
    }
     
    void main()
    {
           circlQueue Q;
           initQueue_C(Q);
           enterQueue_C(Q,'a');
           enterQueue_C(Q,'b');
           enterQueue_C(Q,'c');
           cout<<outputQueue_C(Q)<<endl;
           cout<<outputQueue_C(Q)<<endl;
           destroyQueue_C(Q);
    }


    循环队列解决了队列“假溢出”的情况。


    展开全文
  • 队列实现循环队列

    千次阅读 2018-04-20 21:53:40
    二、实验内容仿照资料中顺序循环队列的例子,设计一个只使用队头指针和计数器的顺序循环队列抽象数据类型。其中操作包括:初始化、入队列、出队列、判断队列是否非空。编写主函数,验证所设计的顺序循环队列的正确性...
  • /*循环队列类型定义*/ const int Queue_Size= 100 ; typedef struct circlQueue { char *elem; int rear; int front; int queueSize; }circlQueue; /*初始化*/ void initQueue_C...
  • 循环队列两端的插入删除操作

    千次阅读 2019-07-11 18:58:45
    写出这样的循环队列类型定义+从队尾删除+从队头插入的算法*/ //私はあの弱い自分を認めない #ifndef PCH_H #define PCH_H #include<stdio.h> #include<iostream> #include<malloc.h> #include<...
  • 循环队列–C语言实现–数据结构

    万次阅读 多人点赞 2017-06-22 16:36:45
    循环队列–C语言实现–数据结构目录循环队列C语言实现数据结构目录 一 要求 二 循环队列循环队列的算法设计 1 建立循环队列 2 置空队列 3 入队 4 出队 5 打印队 四 程序 1 程序的结构 2 程序源码 五 程序测试 1 ...
  • 35 _ 队列1 _ 什么是队列 线性结构的两种常见应用之二 队列 定义:  一种可以实现“先进先出”的存储结构 36 _ 队列2 _ 队列的分类  ...学习循环队列必须要弄清楚的7个问题概述 静态队列  
  • 循环队列

    2014-11-18 17:25:11
    存储在其中的队列称为循环队列(Circular Queue)。 目录 1基本操作 2条件处理 3类型定义 4基本运算 1基本操作编辑 插入新元素,使用PASCAL语言:
  • 循环队列详解

    千次阅读 2018-10-07 03:15:51
    前面分析顺序队的时候,我们知道,顺序队存在”假溢出”的问题,这个问题有时会造成很大的内存浪费,循环队列就是为了解决这个问题而提出地一个很巧妙的办法.循环队列和顺序队列的主要区别在于:循环队列将顺序队列臆造成...
  • //_DataStructure_C_Impl: #include #include #include typedef char DataType; typedef struct snode{ //链式堆栈结点类型定义 ...typedef struct QNode{ //只有队尾指针的链式循环队列类型定义
  • 循环队列(顺序队列)

    千次阅读 2014-10-09 20:51:46
    队列定义
  • 文章目录一,队列的定义二,循环队列定义结构代码初始化队列长度入队列出队列 一,队列的定义 队列是只允许在一端进行插入操作,而在另一端进行删除操作的线性表 队列是一种先进先出的线性表,简称FIFO ...
  • 循环队列(Circular Queue)

    千次阅读 2016-05-28 18:09:41
    1.1 循环队列定义 为了能够充分地使用数组中的存储空间,克服”假溢出”现象,可以把数组的前端和后端连接起来,形成一个环形的表,即把存储队列元素的表从逻辑上看成一个环,成为循环队列(circular queue)。 1.2...
  • 队列只允许在表的一端进行插入(入队)、删除(出队)操作。允许插入的一端称为队尾,允许删除的一端称为队头。 &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;队列的基本操作包括: 初始化...
  • 循环队列的c语言实现

    千次阅读 2016-09-23 21:04:46
    一、什么是循环队列  1、基本概念  队列就是一个能够实现“先进先出”的存储结构,队列分为链式队列和静态队列。静态队列一般用数组来实现,但此时的队列必须是循环队列,否则会造成巨大的内存浪费;链式队列是用...
  • 队列 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作...队列的抽象数据类型定义: ADT Queue{ 数据对象:D={ai | ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系:R={< a(i-1) , ai ...
  • 循环队列的基本操作

    千次阅读 2017-04-18 09:15:28
    实验题目:循环队列的基本操作 • 【实验目的】 • 理解并掌握栈和队列的逻辑结构和存储结构; • 理解栈和队列的相关基本运算; • 编程对相关算法进行验证; 学会利用栈和队列解决实际问题 • 实验内容:编写...
  • 循环队列CircleQueue的使用

    千次阅读 2014-11-02 15:41:08
    循环队列CircleQueue 的使用
  • 普通队列,循环队列以及链队列的相关操作
  •  循环队列的提出主要是用于解决顺序队列的假溢出问题。解决假溢出的办法就是后面满了,再从头开始,头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。本文将从循环队列的顺序存储和链队列出发...
  • 09.循环队列与链队列

    千次阅读 2015-01-09 22:14:15
    一、队列与循环队列 1.队列 (1)队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。队列是一种先进先出(Fiirst In First Out)的线性表,简称FIFO。允许插入的一端称为队尾,允许删除的一端...
  • 前面分析顺序队的时候,我们知道,顺序队存在”假溢出”的问题,这个问题有时会造成很大的内存浪费,循环队列就是为了解决这个问题而提出地一个很巧妙的办法.循环队列和顺序队列的主要区别在于:循环队列将顺序队列臆造成...
  • 队列定义及其基本操作

    万次阅读 多人点赞 2016-12-20 23:52:44
    循环队列及其操作 链队列及其操作 1.队列的定义队列是限制结点插入操作固定在一端进行,而结点的删除操作固定在另一端进行的线性表. 队列犹如一个两端开口的管道.允许插入的一端称为队头,允许删除的一端称为队尾.队...
  • 栈、队列及循环队列

    千次阅读 2018-07-21 22:18:37
    栈,队列及循环队列,是数据结构中的重要的且常用的内容,最近在学习数据结构,于是作一篇笔记记录一下,希望以后复习有帮助  1.栈:  栈是限定仅在表尾进行插入或删除操作的线性表。我们把表尾称作栈顶(top),...
  • 无锁循环队列的应用

    千次阅读 2018-12-22 10:48:14
    存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表的方式来在实际编程应用中来实现。 正文 一, 无锁循环队列的条件处理 循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前...
  • 循环队列的基本实现

    千次阅读 2011-11-09 22:10:00
    完成对循环队列结构的定义,以及对循环队列的各种基本运算的实现(每种基本运算用一个函数来实现)。 基本运算包括: 初始化Init_sqqueue运算、 判队空Empty_sqqueue运算、 入队En_sqqueue运算、 出队De_sqqueue...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 151,958
精华内容 60,783
关键字:

循环队列类型定义