首页 > 数据库 > Sybase > 正文
数据结构-队列静态顺序存储结构
2015-04-29       个评论    来源:王照陆博客  
收藏    我要投稿

队列的基本概念

1 队列的基本概念
队列(Queue):也是运算受限的线性表。是一种先进先出(First In First Out ,简称FIFO)的线性表。只允许在表的一端进行插入,而在另一端进行删除。
队首(front) :允许进行删除的一端称为队首。
队尾(rear) :允许进行插入的一端称为队尾。
  例如:排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。
队列中没有元素时称为空队列。在空队列中依次加入元素a1, a2, …, an之后,a1是队首元素,an是队尾元素。显然退出队列的次序也只能是a1, a2, …, an ,即队列的修改是依先进先出的原则进行的

队列的抽象数据类型定义

ADT Queue{
数据对象:D ={ ai|ai∈ElemSet,  i=1, 2, …, n, n >= 0} 
数据关系:R = {<ai-1, ai> | ai-1, ai∈D,  i=2,3,…,n } 约定a1端为队首,an端为队尾。
基本操作:
Create():创建一个空队列;
EmptyQue():若队列为空,则返回true ,否则返回flase ;
   ??
InsertQue(x) :向队尾插入元素x;
DeleteQue(x) :删除队首元素x;
    } ADT Queue

队列的静态顺序存储结构

在非空队列里,队首指针始终指向队头元素,而队尾指针始终指向队尾元素的下一位置。
顺序队列中存在“假溢出”现象。因为在入队和出队操作中,头、尾指针只增加不减小,致使被删除元素的空间永远无法重新利用。因此,尽管队列中实际元素个数可能远远小于数组大小,但可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假溢出。

循环队列

循环队列:将为队列分配的向量空间看成为一个首尾相接的圆环,并称这种队列为循环队列(Circular Queue)。
特点:
克服上述“假溢出”现象,充分利用向量空间
出队、入队操作,队首、队尾指针仍要加1,朝前移动
当队首、队尾指针指向向量上界(MAX_QUEUE_SIZE-1)时,其加1操作的结果是指向向量的下界0

2  入队操作
Status Insert_CirQueue(SqQueue  Q , ElemType  e)
  /*  将数据元素e插入到循环队列Q的队尾  */
{  if  ((Q.rear+1)%MAX_QUEUE_SIZE== Q.front)
return  ERROR;      /*  队满,返回错误标志    */
Q.Queue_array[Q.rear]=e ;   /*  元素e入队  */
Q.rear=(Q.rear+1)% MAX_QUEUE_SIZE ; 
/*  队尾指针向前移动  */
return OK;        /*  入队成功    */
}
2  入队操作(正确)
Status Insert_CirQueue(SqQueue  *Q , ElemType  e)
  /*  将数据元素e插入到循环队列Q的队尾  */
{  if  ((Q->rear+1)%MAX_QUEUE_SIZE== Q-> front)
return  ERROR;      /*  队满,返回错误标志    */
Q-> Queue_array[Q-> rear]=e ;   /*  元素e入队  */
Q-> rear=(Q-> rear+1)% MAX_QUEUE_SIZE ; 
/*  队尾指针向前移动  */
return OK;        /*  入队成功    */
}
3  出队操作
Status Delete_CirQueue(SqQueue  Q, ElemType  *x )
   /*  将循环队列Q的队首元素出队  */
{   if  (Q.front== Q.rear)
return ERROR ;       /*  队空,返回错误标志    */
*x=Q.Queue_array[Q.front] ;  /* 取队首元素 */
Q.front=(Q.front+1)% MAX_QUEUE_SIZE ;
     /*  队首指针向前移动  */
return OK ;
}
3  出队操作(正确)
Status Delete_CirQueue(SqQueue  *Q, ElemType  *x )
   /*  将循环队列Q的队首元素出队  */
{   if  (Q-> front== Q-> rear)
return ERROR ;       /*  队空,返回错误标志    */
*x= Q-> Queue_array[Q-> front] ;  /* 取队首元素 */
Q-> front=(Q-> front+1)% MAX_QUEUE_SIZE ;
     /*  队首指针向前移动  */
return OK ;
}
点击复制链接 与好友分享!回本站首页
上一篇:数据结构-逻辑结构和存储结构
下一篇:Java从入门到精通——数据库篇MongoDBGridFS文件系统
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训
版权所有: 红黑联盟--致力于做实用的IT技术学习网站