找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索
查看: 3668|回复: 0
打印 上一主题 下一主题
收起左侧

循环队列的实现-C语言教程

[复制链接]
跳转到指定楼层
楼主
ID:99624 发表于 2015-12-20 02:52 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
     // 循环队列的实现源码:
#include"stdio.h"
#include"stdlib.h"

//这是一个静态队列的例程
#define MAXSIZE 10   //队列的最大容量
typedef char ElemType;  //定义一个队列元素类型,这种编程思路很好,程序有扩展空间
//声明一个有关循环队列的数据块,注意每个元素的意义!
struct Queue
{
   ElemType *base;//数据类型头指针
   int front;  //队头(front)进行队列元素删除操作的数组指针索引,很巧妙!
   int rear;  //队尾(rear)进行队列元素插入操作的数组指针索引,很巧妙!
};

//创建队列或曰初始化队列
void Queue_Iinit(Queue * q)
{
 //   q= new Queue;
  q->base=(ElemType *)malloc(MAXSIZE*sizeof(ElemType));//
  if(!q->base)
  {
    printf("内存分配失败!\n");
exit(1);
  }
  q->front=q->rear=0;
  //这一步很重要!将队头和队尾指针索引q->front,q->rea都赋值为0,即同时指向数组第一个元素

}
//入队操作,入队从队尾rear处开始
void InsertQueue(Queue * q,ElemType e)
{
  if((q->rear+1)%MAXSIZE==q->front)//先判断队列是否已满,因为入队从队尾rear处开始,所以先判断rear指针索引
/*
  表达式(q->rear+1)%MAXSIZE也叫取模运算,该表达式能确保(q->rear+1)%MAXSIZE的结果小于MAXSIZE!
  这样可以确保数组指针不越界。为什么要rear加1呢?腾出一个数据的空闲空间。
  这种算法很技巧!

  */
  {
     printf("队列已满!\n");
     return;
  
  }
  q->base[q->rear]=e;//
  q->rear=((q->rear+1)%MAXSIZE);//这一步既实现了指针前移同时还实现了指针不越界!技巧!

}
//出队操作,出队是从队头front处开始
void DeleteQueue(Queue * q,ElemType *e)
{
    if(q->front==q->rear)//已空,说明队列元素已经删除完毕
    {
 printf("老大,队列已空!\n");
 return;
}
 //   *(e++)=q->base[q->front];//完成此步还不够!还需要指针索引移位!注意赋值方法!
*e=q->base[q->front];//完成此步还不够!还需要指针索引移位!注意赋值方法!
    q->front=(q->front+1)%MAXSIZE; //指针指向下一个空闲空间,确保不越界
    
  
 
}

//判断队列是否为空
bool EmptyQueue(Queue * q)  
{  
    if(q->front==q->rear)    //判断是否为空  
{  
        printf("队列已空!\n");
return true; 
}
    else  
        return false;  
}  
//判断队列是否为满
bool FullQueue(Queue * q) 
{  
   if((q->rear+1)%MAXSIZE==q->front)   //判断循环链表是否满,留一个预留空间不用  
   {
 printf("队列已满!\n");
  return true; 
   } 
    else  
        return false;  
}  
/*********************************************** 
输出每一个元素
************************************************/  
void TraverseQueue(Queue * q)  
{  
    int i=q->front;  
    printf("队中的元素是:\n");  
    while( (i%MAXSIZE)!=q->rear )  //注意,这里没有加1,打印每一个元素
    {  
        printf("%c\n ",q->base[i]);  
        i++;  
    }  
    printf("\n");  

}  
void main()
{
  
    Queue q;
char c;
   
    Queue_Iinit(&q);

printf("请输入循环队列元素,以#作为结束符\n");
 
scanf("%c",&c);//注意!本句表示一次输入一个字符
  
InsertQueue(&q,c);
    
/*
  注意:比如输入“1110010#”再按下回车键,字符串“1110010#”就以一次一个字符的顺序输入到PC键盘缓冲区即入栈;
  出栈时是以“后进先出”的顺序出栈,刚好最后入栈的字符就是二进制的最低位。对于栈的操作一定要注意入栈出栈顺序
*/ 

while(c!='#')
{

     scanf("%c",&c);//这里为什么还要此句呢?因为scanf()一次只能输入一个字符,所以必须循环输入
      InsertQueue(&q,c);
}
getchar();//改变键盘输入缓存指针,即将回车键读出来,这样可以避免“\r”字符(回车键)输出

TraverseQueue(&q);
    printf("开始出队命令!\n"); 

 
   
    while(1)
{
    
DeleteQueue(&q,&c);
   printf("出队:%c\n ",c);
if( EmptyQueue( &q))
break;
 
}

}
///////////////////////////////////----GKXW------------2015年11月14日18:47:4////////////////////////////////////////////////////

         我想,看完本篇内容uc/os-ii操作系统的“消息队列”部分内容就可以轻松理解了。关于循环队列,我的理解是:既节省了内存空间,同时在时间复杂度和空间复杂度上大大提高了效率。至于算法我们都是站在巨人的肩膀上学习学习再学习,很难想象如果没有现成的代码,我们要实现循环队列的操作该有多难。 关于循环队列算法真的非常精妙!学习本文能感受到C语言的魅力。

         队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。在队列这种数据结构中,最先插入的元素将是最先被删除的元素;反之最后插入的元素将最后被删除的元素,因此队列又称为“先进先出”(FIFO—first in first out)的线性表。 队列分为链式队列和静态队列;静态队列一般用数组来实现,但此时的队列必须是循环队列,否则会造成巨大的内存浪费;链式队列是用链表来实现队列的。 

       由于队列有元素出列,front就向后移动,所以队列前面的空间就空了出来。为了更合理的利用空间,人们想了一个办法:将队列的首尾相连接。这样当rear移动到
front处时,会再从0开始循环。那当什么时候队列满呢?当rear等于front的时候。可是队列为空的时候也是同样的条件,那不就没法判断了吗?又有人提出了这样的想法:牺牲一个存储空间,front前面不存数据,当rear在front前面的时候就是满了,如图:


//////////////////////-------GKXW-----作者为本文付出很大心血,转载请署名!-------////////////////////////////////


分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
收藏收藏2 分享淘帖 顶1 踩
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|小黑屋|51黑电子论坛 |51黑电子论坛6群 QQ 管理员QQ:125739409;技术交流QQ群281945664

Powered by 单片机教程网

快速回复 返回顶部 返回列表