首页 > 代码库 > 队列。

队列。

2024-07-29 19:13:14   221人阅读

用模运算可简化为：i=(i+1)%MAX_QUEUE_SIZE ;

和时间有关的操作都与队列有关。

 

队列的顺序存储结构FIFO
设立一个队首指针front ，一个队尾指针rear ，分别指向队首和队尾元素。
◆ 初始化：front=rear=0。
◆ 入队：将新元素插入rear所指的位置，然后rear加1。
◆ 出队：删去front所指的元素，然后加1并返回被删元素。
◆ 队列为空：front=rear。
◆ 队满：rear=MAX_QUEUE_SIZE-1或front=rear。

 

静态顺序队列

#define MAX_QUEUE_SIZE 100typedef struct queue{      ElemType Queue_array[MAX_QUEUE_SIZE] ;      int front ;      int rear ;}SqQueue;

循环队列

循环队列需要的参数：2个参数。front rear
初始化：front 和rear的值都是0
队列非空：front代表的是队列的第一个元素
rear代表队列的最后一个有效元素的下一个元素。
队列空：front和rear的值都相等，但不一定是0.
◆ rear所指的单元始终为空。
◆ 循环队列为空：front=rear 。
◆ 循环队列满：(rear+1)%MAX_QUEUE_SIZE =front。

循环队列的初始化

 SqQueue Init_CirQueue(void){      SqQueue  Q ;    Q.front=Q.rear=0;      return(Q) ;}

入队操作
伪算法：将值放在r所代表的位置/r指针移动，r=(r+1)%数组的长度

Status Insert_CirQueue(SqQueue  Q , ElemType  e)                             {      if  ((Q.rear+1)%MAX_QUEUE_SIZE== Q.front)            return  ERROR;                              Q.Queue_array[Q.rear]=e ;                          Q.rear=(Q.rear+1)% MAX_QUEUE_SIZE ;                return OK;       }

出队

f=(f+1）%数组的长度

Status Delete_CirQueue(SqQueue  Q, ElemType  *x ) /*  将循环队列Q的队首元素出队  */  {       if  (Q.front+1== Q.rear)    return ERROR ;       /*  队空，返回错误标志    */    *x=Q.Queue_array[Q.front] ;  /* 取队首元素 */    Q.front=(Q.front+1)% MAX_QUEUE_SIZE ; /*  队首指针向前移动  */        return OK ;}

 

队列的链式表示和实现---它是限制仅在表头进行删除操作和表尾进行插入操作的单链表。

数据元素结点类型定义：

typedef struct Qnode{     ElemType    data ;    struct Qnode  *next ;}QNode ;

指针结点类型定义：

typedef struct link_queue{      QNode  *front ,  *rear ;}Link_Queue ;

⑴ 链队列的初始化

LinkQueue *Init_LinkQueue(void){      LinkQueue  *Q ;  QNode  *p ;    p=(QNode *)malloc(sizeof(QNode)) ; /* 开辟头结点 */    p->next=NULL ;    Q=(LinkQueue  *)malloc(sizeof(LinkQueue)) ;  /*  开辟链队的指针结点  */           Q.front=Q.rear=p ;     return(Q) ;}

(2) 链队列的入队操作---在已知队列的队尾插入一个元素e ，即修改队尾指针(Q.rear)。

Status  Insert_CirQueue(LinkQueue  *Q , ElemType  e) /*  将数据元素e插入到链队列Q的队尾  */     {       p=(QNode *)malloc(sizeof(QNode)) ;    if (!p)          return  ERROR;/*  申请新结点失败，返回错误标志 */    p->data=http://www.mamicode.com/e ;    p->next=NULL ;       /*  形成新结点 */    Q.rear->next=p ;     Q.rear=p ;  /*  新结点插入到队尾  */    return OK;}

(3)链队列的出队操作

Status  Delete_LinkQueue(LinkQueue  *Q, ElemType *x){       QNode *p ;    if(Q.front==Q.rear)          return ERROR ;    /*  队空  */    p=Q.front->next ;   /*  取队首结点  */    *x=p->data ;     Q.front->next=p->next ;      /*  修改队首指针  */    if (p==Q.rear)  Q.rear=Q.front ;  /*  当队列只有一个结点时应防止丢失队尾指针  */           free(p) ;       return OK ; }

(4)链队列的撤消

void  Destroy_LinkQueue(LinkQueue  *Q ) /*  将链队列Q的队首元素出队  */  {      while(Q.front!=NULL)    {         Q.rear=Q.front->next;    /*  令尾指针指向队列的第一个结点   */                 free(Q.front);      /*  每次释放一个结点  */ /*  第一次是头结点，以后是元素结点  */                Q.ront=Q.rear;}

 

队列。


联系
我们