循环队列c语言_c 语言 循环队列 .c - CSDN
精华内容
参与话题
  • 循环队列的基本操作-C语言

    千次阅读 2019-06-24 11:54:45
    循环队列的基本操作一、循环队列二、循环队列的理解 一、循环队列 为充分利用向量空间,克服上述“假溢出”现象的方法是:将为队列分配的向量空间看成为一个首尾相接的圆环,并称这种队列为循环队列(Circular Queue)...

    一、循环队列

    为充分利用向量空间,克服上述“假溢出”现象的方法是:将为队列分配的向量空间看成为一个首尾相接的圆环,并称这种队列为循环队列(Circular Queue)。

    二、循环队列的理解

    例:设有循环队列QU[0,5],其初始状态是front=rear=0,各种操作后队列的头、尾指针的状态变化情况如下图所示。
    在这里插入图片描述
    在这里插入图片描述
    入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故队空和队满时头尾指针均相等。因此,无法通过front=rear来判断队列“空”还是“满”。
    ☞☞解决此问题的方法是:约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满。即:
    ◆ rear所指的单元始终为空。
    ◆ 循环队列为空:front=rear 。
    ◆ 循环队列满:(rear+1)%MAX_QUEUE_SIZE =front。

    二、循环队列的算法

    ①、循环队列–队列的顺序存储结构

    /******循环队列--队列的顺序存储结构******/
    #define MAXQSIZE 10 /*最大队列长度*/
    #define  OK   1
    #define  ERROR   -1
    typedef  int  Status ;
    typedef  int  ElemType ;
    typedef struct {
        ElemType *base;  /*初始化的动态分配存储空间*/
        int front;       /*头指针,若队列不为空,指向队列头元素*/
        int rear;        /*尾指针,若队列不为空,指向队列尾元素的下一个位置*/
    }SqQueue;
    

    ②、构造空循环队列

    /*构造一个空队列*/
    Status InitQueue(SqQueue Q){
        Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType));
        if(!Q.base) exit (0);           /*存储分配失败退出*/
        Q.front = Q.rear = 0;
        return OK;
    }
    

    ③、入队

     /*  将数据元素e插入到循环队列Q的队尾  */
    Status EnQueue(SqQueue Q, ElemType *e) {
        if ( ( Q.rear + 1 ) % MAXSIZE == Q.front ) /*判断队列是否满*/
        return ERROR;  /*队列满*/
        Q.base[Q.rear] = e;   /*  元素e入队  */
        Q.rear = ( Q.rear + 1 ) % MAXSIZE; /*  队尾指针向前移动  */
        return OK;      /*  入队成功,返回OK  */
    }
    

    ④、出队

    Status OutQueue(SqQueue Q, ElemType *e){
        if (Q.rear == Q.front )  
        return ERROR;                      /*队列为空,返回错误*/
        e = Q.base[Q.front];               /* 取队首元素 */
        Q.front = ( Q.front + 1 ) % MAXSIZE;/* 队首指针向前移动 */
        return OK;
    }
    

    ⑤、返回Q元素的个数,即队列的长度

    /*返回Q元素的个数,即队列的长度*/
    int QueueLength(SqQueue Q){
        int i;
        i=(Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; /*计算队中元素个数*/
        return(i);
    }
    

    ⑥、遍历

    void PrintQuence(SeQuence Q) {
        int i;
        i = (Q->Front + 1) % MAXQSIZE; /*队头加一开始遍历*/
        while (i != Q->rear) {
            printf("%c", Q->base[i]);
            i = (i + 1) % MAXQSIZE;
        }
        printf("%c",Q->base[i]);       /*队尾*/
        printf("\n");
    }
    

    应用

    1、桌上有一叠牌,从第一张牌(即位于顶面的牌)开始从上往下依次编号为1~n。当至少还剩三张牌时进行以下操作:把第一、二张牌扔掉,然后把当前状态下新的第一张放到整叠牌的最后。 输入n,输出每次扔掉的牌,以及最后剩下的牌。 输入输出样例如下:
    输入4
    第一次:扔掉1,2
    从顶向底最后剩下:4,3

    Queue.h

    #include<stdio.h>
    #include<stdlib.h>
    #define OK 1
    #define ERROR -1
    #define MAX 100
    typedef int QElemType;
    typedef struct
    {
        QElemType *data;
        int front;//队头
        int rear;//队尾
    }SqQueue;
     /*初始化*/
    int InitiQueue(SqQueue &Q)
    {
           Q.data=(QElemType*)malloc(MAX*sizeof(QElemType));
        if(!(Q.data))
           {
                  exit(0);
           }
        Q.front=Q.rear=0;
        return OK;
    }
     /*尾插法入队*/
    int EnQueue(SqQueue &Q,QElemType e)
    {
        if((Q.rear+1)%MAX== Q.front) //队列满
           {
                  return ERROR;
           }
        Q.data[Q.rear]=e;
        Q.rear=(Q.rear+1)%MAX;
        return  OK;
    }
     /*出队*/
    int DeQueue(SqQueue &Q,QElemType &e){
        if(Q.front == Q.rear)
           {
                  return ERROR;
           }
        e=Q.data[Q.front];
        Q.front=(Q.front+1)%MAX;
        return OK;
    }
    /*纸牌*/
    int Playing_Cards(SqQueue &Q,QElemType &e)
    {
        int n,i=1;
           int number=1;//计数
        printf("请输入的数量:  ");
        scanf("%d",&n);
           printf("牌的编号为: ");
        for(i=1;i<=n;i++)
           {
            EnQueue(Q,i);
                  printf(" %d ",i);
        }
           printf("\n");
        while(1)
           {
     
                  DeQueue(Q,e);  
                  printf("第 %d 次删除掉:%d ",number++,e);
                  if(Q.front==Q.rear)
                         break;
                  DeQueue(Q,e);
                  printf("%2d \n",e);
            if(Q.front==Q.rear)
                         break;
            DeQueue(Q,e);     //新的第一张出队
            if(Q.front==Q.rear)
                         break;
            if(Q.front+1==Q.rear&&n%2==0)//保留偶数编号牌
                         break;
            EnQueue(Q,e);//把牌放到整叠牌的最后
           }
     
        printf("从顶向底最后剩下:");
           if(Q.front+1== Q.rear)
           {
                  printf("%2d ",Q.data[Q.rear-1]);
            printf("%2d ",Q.data[Q.front-1]);
           }
           else
                  printf("%2d ",Q.data[Q.rear-1]);
           printf("\n");
           return OK;
    }
     
    

    Queue.c

    #include"Queue.h"
    int main()
    {
    	int e=1;
    	SqQueue Q;
    	InitiQueue(Q);
    	int choice;
    	Playing_Cards(Q,e);	
    	while(true){
    		InitiQueue(Q);
    	printf("请问是否继续?1/是,2/否 :\n");
    	scanf("%d",&choice);
    	if(choice == 1)
    	{
    		Playing_Cards(Q,e);	
    	}
    	else return 0;
    	}
    	return 0;
    }
    
    

    运行结果

    在这里插入图片描述

    展开全文
  • 循环队列c语言版)

    2019-07-27 21:28:25
    C语言循环队列 #ifndef QUEUE #define QUEUE #define maxsize 4 typedef struct { int data[maxsize]; int front; int rear; }*Queue, Node; #endif #include&lt;stdio.h&gt; #include&lt;...

    C语言版循环队列

    #ifndef QUEUE
    #define QUEUE
    
    #define maxsize 4
    
    typedef struct {
    	int data[maxsize];
    	int front;
    	int rear;
    }*Queue, Node;
    
    #endif
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    void initQueue(Queue queue)
    {
    	queue->front = 0;
    	queue->rear = 0;
    }
    
    bool isEmpty(Queue queue)
    {
    	if (queue->front == queue->rear) {
    		return true;
    	}
    	return false;
    }
    
    bool isFull(Queue queue)
    {
    	if ((queue->rear + 1) % maxsize == queue->front) {
    		return true;
    	}
    	return false;
    }
    
    bool Enqueue(Queue queue, int num)
    {
    	if (isFull(queue)) {
    		return false;
    	}
    	queue->data[queue->rear] = num;
    	queue->rear = (queue->rear + 1) % maxsize;
    	return true;
    }
    
    bool Dequeue(Queue queue, int *x)
    {
    	if (isEmpty(queue)) {
    		return false;
    	}
    	*x = queue->data[queue->front];
    	queue->front = (queue->front + 1) % maxsize;
    	return true;
    }
    
    int QueueLength(Queue queue)
    {
    	return (queue->rear - queue->front + maxsize) % maxsize;
    }
    
    int main(void)
    {
    	Queue queue;
    
    	queue = (Queue)malloc(sizeof(Node));
    
    	initQueue(queue);
    
    	int choose;
    
    	bool flag = true;
    	while (flag) {
    		printf("请输入您要进行的操作:\n1:入队\n2.出队\n");
    		scanf("%d", &choose);
    		if (choose == 1) {
    			int num;
    			printf("请输入您要入队的数据:");
    			scanf("%d", &num);
    			if (Enqueue(queue, num)) {
    				printf("%d入队成功!\n", num);
    			}
    			else {
    				puts("入队失败");
    			}
    			puts("--------------------");
    		}
    		else
    		{
    			int num;
    			if (Dequeue(queue, &num)) {
    				printf("%d已出队列\n", num);
    			}
    			else {
    				puts("出队失败");
    			}
    			puts("---------------------");
    		}
    		printf("长度:%d\n", QueueLength(queue));
    	}
    
    }
    

    输出结果
    在这里插入图片描述

    展开全文
  • 队列-循环队列-C语言实现

    千次阅读 2018-12-25 16:30:43
    //循环队列完成 #include&lt;malloc.h&gt; #include&lt;stdlib.h&gt; #include&lt;stdbool.h&gt; typedef struct Queue{ int *pBase; //代表数组的首地址 int front;//代表的数组的下标 ...
    #include<stdio.h> //循环队列完成
    #include<malloc.h>
    #include<stdlib.h>
    #include<stdbool.h>
    typedef struct Queue{
        int *pBase; //代表数组的首地址
        int front;//代表的数组的下标
        int rear;
    }QUEUE;
    void init(QUEUE *);
    bool en_queue(QUEUE*,int val);
    void traverse_queue(QUEUE *);
    bool full_queue(QUEUE *pQ);
    bool out_queue(QUEUE *,int *);
    bool empt_queue(QUEUE *);
    int main(void)
    {
        QUEUE Q;
        int val;
        init(&Q);
        en_queue(&Q,1);
        out_queue(&Q,&val);
        en_queue(&Q,2);
        out_queue(&Q,&val);
        en_queue(&Q,3);
        en_queue(&Q,4);
        en_queue(&Q,5);
        en_queue(&Q,6);
        en_queue(&Q,7);
        en_queue(&Q,8);
        traverse_queue(&Q);
        if(out_queue(&Q,&val)){
            printf("succes,%d\n",val);
        };
       out_queue(&Q,&val);
        return 0;  
    }
    void init(QUEUE *pQ){
        //代表数组的第一个元素地址,长度为6,近似理解pBase为一个数组
        pQ->pBase =(int *)malloc(sizeof(int)*6);
        pQ->front =0;
        pQ->rear=0;
    }
    //入队 rear指向队尾的下个元素
    bool en_queue(QUEUE *pQ,int val){
        if( full_queue(pQ)){
            return false;
        }
        else{
            //先把数值赋给最后一个元素
            pQ->pBase[pQ->rear]= val;
            //rear的值后移,因为是循环链表长度为6,5个数据
            pQ->rear=(pQ->rear+1)%6;
            return true;
        }
    }
    //出队 注意出列为队头front+1
    bool out_queue(QUEUE *pQ,int *pVal){
        if(empt_queue(pQ)){
            return false;
        }else{
            *pVal =pQ->pBase[pQ->front];
            pQ->front =(pQ->front+1)%6;
        }
    }
    //判断链表是否为空
    bool full_queue(QUEUE *pQ){
        //队尾元素+1是否等于队头元素,因为是循环链表
        if((pQ->rear+1)%6==pQ->front)
        {
        return true;
        }
        else
        {
        return false;
        }
    }
    //遍历
    void traverse_queue(QUEUE *pQ){
        int i =pQ->front;
        while(i!=pQ->rear){
            printf("%d\n",pQ->pBase[i]);
            i=(i+1)%6;
        };
        return;    
    }
    //判断队列为空
    bool empt_queue(QUEUE *pQ){
        if(pQ->front == pQ->rear){
            return true;
        }
        else{
            return false;
        }
    }
    

     

    展开全文
  • 队列有两种,一种叫做循环队列(顺序队列),另一种叫做链式队列。 这一篇讲的是循环队列,链式队列在另外一篇文章中 循环数组 循环队列使用的是数组,但是这个数组比较特别,为循环数组。为什么要使用循环数组呢? ...

    队列的一些说明

    队列的定义

    队列,一种特殊的线性表

    特点:只允许在一端输入,在另一端输出。输入端称为队尾,输出端称为队头

    因此,队列,又称为先进先出表(FIFO),类似于生活中的排队,先来的排在前头,后来的排在后头,一个一个办理业务。

    队列有两种,一种叫做循环队列(顺序队列),另一种叫做链式队列。

    这一篇讲的是循环队列,链式队列在另外一篇文章中

    链式队列讲解与C++实现

    循环数组

    循环队列使用的是数组,但是这个数组比较特别,为循环数组。为什么要使用循环数组呢?

    可以想象一下,假如我们使用通常的数组。

    那么在使用过程中,我们是从后面加入数据,从前面移除数据。那么随着出队和入队的进行,数组会整体向右平移,因为数组前面的元素因为出队变成了空白,变得不可使用。造成空间的浪费。

    如果每出队一次,都将数组向左平移一次,又会很麻烦,造成时间上的浪费。综上,我们使用循环队列,就是将队首和队尾黏在一起。类似于一个⚪;
    循环数据
    那么知道了循环数组后,我们应该考虑下,队首和队尾怎么放置,才能使我们循环队列能够使用。

    不同的队首和队尾的初始化,将导致我们判断队列是否已满以及队列是否为空的方法的不同

    (1)front(队首)和rear(队尾)初始化均为0。那么,在这种情况下,front会永远指向队首元素,而rear会指向队尾元素的下一格。
    (2)front(队首)和rear(队尾)错开。比如 front 初始为0,rear初始为5。在这种情况下front会永远指向队首元素,rear会永远指向队尾元素。

    因此,在判断队列是否已满与非空时,初始化不同,判断方式不同。或者干脆就不用front与rear的位置来判断队列是否已满与非空。多加一个参数Size,表示队列的现有容积也行。

    另外,如何在代码实现过程中将正常数组变成循环数组呢?

    很简单,取余即可

    C语言实现循环队列

    定义结构体

    struct Queue{ //结构体 
     int *data;   
     int capacity; //最大容积 
     int front;  //表头 
     int rear;  //表尾 
     //int size; //size表示队列的现有容量, 
    };

    队列的初始化

    void init(struct Queue *pq,int capacity){ //队列的初始化 
     pq->capacity=capacity;
     pq->data=(int*)malloc(sizeof(int)*(capacity+1));
     pq->front = 0;  //初始化的不同,会导致后面判断队列是否为空以及是否已满的不同 
     pq->rear = 0;
    }

    判断队列是否已满

    int isFull(const struct Queue *pq){  //判断队列是否已满
     if((pq->rear + 1)%(pq->capacity+1) == pq->front) return 1;
     else return 0;
    }

    判断队列是否为空

    int isEmpty(const struct Queue *pq){ //判断是否为空 
     return pq->front == pq->rear;
    }

    入队操作,x表示插入的元素

    int enQueue(struct Queue *pq,int x){ //入队操作 
     if(isFull(pq)) return 0;
     else{
      pq->data[pq->rear] = x;
      pq->rear = (pq->rear+1) % (pq->capacity+1);
      return 1;  //成功返回1,失败返回0 
     } 
    }

    出队操作,同时返回出队的值给px

    int deQueue(struct Queue *pq,int *px){  //出队操作 
     if(isEmpty(pq)) return 0;
     else {
      *px = pq->data[pq->front];
      pq->front = (pq->front+1) % (pq->capacity+1);
      return 1;  //成功返回1,失败返回0 
     }
    }
    

    完整代码

    #include<stdio.h>
    #include<stdlib.h>
    using namespace std;
    //循环队列 
    struct Queue{ //结构体 
     int *data;   
     int capacity; //最大容积 
     int front;  //表头 
     int rear;  //表尾 
     //int size; //size表示队列的现有容量, 
    };
    
    void init(struct Queue *pq,int capacity){ //队列的初始化 
     pq->capacity=capacity;
     pq->data=(int*)malloc(sizeof(int)*(capacity+1));
     pq->front = 0;  //初始化的不同,会导致后面判断队列是否为空以及是否已满的不同 
     pq->rear = 0;
    }
    
    int isFull(const struct Queue *pq){  //判断队列是否已满
     if((pq->rear + 1)%(pq->capacity+1) == pq->front) return 1;
     else return 0;
    }
    
    int isEmpty(const struct Queue *pq){ //判断是否为空 
     return pq->front == pq->rear;
    }
    
    int enQueue(struct Queue *pq,int x){ //入队操作 
     if(isFull(pq)) return 0;
     else{
      pq->data[pq->rear] = x;
      pq->rear = (pq->rear+1) % (pq->capacity+1);
      return 1;  //成功返回1,失败返回0 
     } 
    }
    
    int deQueue(struct Queue *pq,int *px){  //出队操作 
     if(isEmpty(pq)) return 0;
     else {
      *px = pq->data[pq->front];
      pq->front = (pq->front+1) % (pq->capacity+1);
      return 1;  //成功返回1,失败返回0 
     }
    }
    
    int main()
    {
     struct Queue q; 
     init(&q,4);
     enQueue(&q,11);
     enQueue(&q,22);
     enQueue(&q,33);
     enQueue(&q,44);
     enQueue(&q,55);
     
     int x;
     deQueue(&q,&x);
     printf("%d\n",x);
      deQueue(&q,&x);
     printf("%d\n",x);
      deQueue(&q,&x);
     printf("%d\n",x);
      deQueue(&q,&x);
     printf("%d\n",x);
      deQueue(&q,&x);
     printf("%d\n",x);
    } 
    
    展开全文
  • c语言实现循环队列

    千次阅读 2019-07-04 13:39:49
    接口参考严蔚敏老师的...循环队列如何达到循环状态,接口函数实现的过程最好画图来形象的展示,实现后一个个调试,因为一不小心就可能出错误。 实现环境:linux 下面是实现过程 数据结构: typedef struct {...
  • C语言——循环队列

    千次阅读 2018-12-27 12:50:10
    循环队列 遵循先进先出(FIFO) 浪费一个空间,让循环队列更好的判断满/空,更好运用循环队列 黑色代表空时状态,红色代表满时状态 下面代码: #include &amp;amp;amp;lt;stdio.h&amp;amp;amp;gt; ...
  • 循环队列-C语言

    2020-04-25 09:25:13
    循环队列-C语言 具体代码 #include<stdio.h> #include<stdlib.h> #define MAXSIZE 10 typedef struct Queue{ int head; int rear; int data[MAXSIZE]; int size; }Queue; void Init(Queue *Q){ ...
  • 转载:http://blog.csdn.net/lpp0900320123/article/details/20694409生活中有很多队列的影子,比如打饭排队,买火车票排队问题等,可以说与...静态队列一般用数组来实现,但此时的队列必须是循环队列,否则会造成巨...
  • 循环队列C语言实现

    2019-08-07 21:43:41
    title: 循环队列 tags: 循环队列 grammar_cjkRuby: true 采用单向循环队列,实现, 使用void指针,扩展性更好,可以用于存储不同的数据结构,不单单是int,各种struct都行 可以自定义扩容算法, AddCapacity目前是...
  • 全国计算机等级考试——C语言二级 题库

    千次阅读 多人点赞 2019-01-19 12:29:14
    计算机C语言二级考试(题库11) 一、选择题 2、下列叙述中正确的是( ) A)循环队列中的元素个数随队头指针与队尾指针的变化而动态变化 B)循环队列中的元素个数随队头指针的变化而动态变化 C)循环队列中的元素个数随...
  • C语言循环队列(数组实现)

    千次阅读 2018-07-16 20:45:39
    #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; typedef struct queue_arr { int * data; int front; int rear;...//初始化队列 que * InitQueue() { que * q = (que *)mal...
  • //循环队列的基本操作 #include #define MaxSize 50 typedef int ElemType; //定义循环队列结构体 typedef struct  { ElemType data[MaxSize]; int front,rear; }SqQueue; //初始化 void ...
  • 同样,队列作为一种特殊的线性表,也同样存在两种存储方式。 那就是顺序队列、链式队列两种 这里主要介绍顺序队列,链式队列我在上一篇博客中详细介绍了(因为用的比较多)。想看链式队列的话大家可以参考 ...
  • C语言循环数组做FIFO队列--一些认识

    万次阅读 2013-01-06 11:43:19
    C语言循环数组做FIFO队列 在做通信时,FIFO队列queue是非常好用的,先完成接收通信把接收的数据存在队列里;然后再进行先进先出逐项处理。 C语言循环数组,通过读位置和写位置循环来实现FIFO队列功能。即...
  • C语言实现对队列的基本操作

    万次阅读 2018-01-29 18:48:52
    (1)定义循环队列:rear指针指向队列的最后一个元素所在位置,front指针则指向第一个元素的前一个位置。并且rear和front都只能单方向移动。 (2)入队操作:先判断队列是否溢出->在队尾插入需要插入的元素作为新的...
  • 数据结构中循环队列的使用
  • #include #include typedef struct queue { int data; struct queue *link; }QUEUE; void EnQueue(QUEUE **head,QUEUE**tail,int x) { //从队尾tail进队 ... p=(QUEUE*)malloc(sizeo
  • 利用循环队列打印杨辉三角(c语言实现)

    万次阅读 多人点赞 2018-08-29 16:01:22
    #include&lt;stdio.h&gt; #include&lt;malloc.h&gt; #include&lt;stdlib.h&gt; #define MAXQSIZE 200 typedef int QElemType; typedef struct { QElemType *base;...voi...
  • C语言实现顺序队列

    千次阅读 2018-08-11 09:47:08
    在顺序队列中,通常让队尾指针rear指向刚进队的元素的位置,让队首指针front指向刚出队的元素的位置。因此,元素进队的时候rear指针要向后移动,元素出队的时候front指针也要向后移动。这样经过一系列的操作后,两个...
  • C语言 数据结构 三、 创建一个字符循环队列,实现字符元素入队列、出队列、显示队列元素等操作。要求为用户提供选择式菜单
1 2 3 4 5 ... 20
收藏数 29,794
精华内容 11,917
关键字:

循环队列c语言