算法与数据结构之七----顺序队列

/**************************************************************** 文件内容：队列之顺序队操作 版本V1.0 时间：2013-12-30 说明：队列也可以使用顺序表和链表来实现，本文主要讲顺利队列 1.为了防止假溢出，采用环形buf。环形buf 指针移到必需通过%来修正 2.在环形 buf中，为了区分是空队列还是满队列(因为这两种情况Rear指针都等于front），引入了num计数 3.队列就是先进先出的一个FIFO结构，在实际生活中最常见的模型，如先来先服务的排队   共享内存的buf，生产者与消费者模型等  ****************************************************************/  #include<stdio.h> #include<stdlib.h> //#define RELEASE_VERSION  //release版本开关 //#define TRIDiTION /*inlude<malloc.h> stdlib.h 包含malloc.h*/ #ifdef RELEASE_VERSION #define  Log  #else #define  Log  printf #endif #define MAX 15 /*为了提高程序的可移植性，千万不能使用裸露的数据类型*/ #ifndef UINT32  typedef unsigned int UINT32 ; #endif #ifndef INT32  typedef  int  INT32 ; #endif typedef struct Sequeue { INT32 data[MAX]; INT32 Front , Rear; INT32 num; }SeQueue ,* SQPointer; /**************************************************************** 函数功能：初始化顺序队列                        输入参数:  无 返回值： 顺序的队列的标头指针  说明：顺序队列是由顺序来实现，所有的操作方式都是跟顺序表一样，只是某些操作堆队列来说是 非法的。 作者:HFL  时间：2013-12-30  *****************************************************************/   SQPointer Init_Sequeue() { SQPointer s = NULL; s = (struct Sequeue * )malloc(sizeof (struct Sequeue)); if(NULL) { Log("malloc is failed\n"); } else { Log( "malloc is sucessed \n"); } s->Front = -1;     s->Rear = -1; s->num = 0 ; return s; } /**************************************************************** 函数功能：判断顺序队列是否为空队列                        输入参数:  无 返回值： 顺序的队列的标头指针  说明：顺序队列是由顺序来实现，所有的操作方式都是跟顺序表一样，只是某些操作堆队列来说是 非法的。 作者:HFL  时间：2013-12-30  *****************************************************************/  INT32 Is_Empty_Sequeue(SQPointer q) {   if (0 == q->num )   {  Log("sorry,the sequeue is NULL\n");  return 0;   }   else   {     return 1;   } } /**************************************************************** 函数功能： 判断顺序队列是否已经满                        输入参数:  无 返回值： 顺序的队列的标头指针  说明：顺序队列是由顺序来实现，所有的操作方式都是跟顺序表一样，只是某些操作堆队列来说是 非法的。 作者:HFL  时间：2013-12-30  *****************************************************************/  INT32 Is_Full_Sequeue(SQPointer q) {    if ( q->num == MAX )   {  Log("sorry,the sequeue is FULL\n");  return 0;   }   else   {     return 1;   } } /**************************************************************** 函数功能： 顺序队列入队列                       输入参数:  无 返回值： 顺序的队列的标准指针 说明：顺序队列是由顺序来实现，所有的操作方式都是跟顺序表一样，只是某些操作堆队列来说是 非法的。 作者:HFL  时间：2013-12-30  *****************************************************************/  INT32 FIFO_IN_Sequeue(SQPointer q,INT32 X) { if(!Is_Full_Sequeue(q)) {      return -1; } q->Rear = (q->Rear+1)%(MAX); q->num++ ;     q->data[q->Rear] = X; Log("The INTO %ddata is %d\n",q->Rear,q->data[q->Rear]); return 0; } /**************************************************************** 函数功能： 顺序队列出队列                       输入参数:  无 返回值： 顺序的队列的标准指针 说明：顺序队列是由顺序来实现，所有的操作方式都是跟顺序表一样，只是某些操作堆队列来说是 非法的。 作者:HFL  时间：2013-12-30  *****************************************************************/  INT32  FIFO_OUT_Sequeue(SQPointer q,INT32 *X ) {   if(!Is_Empty_Sequeue(q)) { *X  = 0 ;      return -1; } q->Front = (q->Front+1)%(MAX);     *X = q->data[q->Front]; // Log("The INTO %ddata is %d\n",q->Rear,q->data[q->Rear]); q->num--; return 0; } /**************************************************************** 函数功能： 顺序队列读队列顶元素                       输入参数:  无 返回值： 顺序的队列的标准指针 说明：顺序队列是由顺序来实现，所有的操作方式都是跟顺序表一样，只是某些操作堆队列来说是 非法的。 出队列会修改队列顶指针，而读队列顶元素，不需修改队列顶指针 作者:HFL  时间：2013-12-30  *****************************************************************/ INT32  Read_Sequeue(SQPointer q ) {   INT32 temp; if(!Is_Empty_Sequeue(q)) {      return -1; }     temp = q->data[q->Front];     return temp; }  void main() {  INT32 i = 0,Ret = -1; INT32 X; SeQueue * s = NULL;     Log("*******************************\n"); Log("*                             *\n"); Log("*   Init Sequeue is start !   *\n"); Log("*                             *\n"); Log("*******************************\n"); s= Init_Sequeue(); if (!s) { Log( "Init_Sequeue is failed!\n"); } else { Log( "Init_Sequeue is sucessed\n"); } Log("*******************************\n"); Log("*                             *\n"); Log("*    Into Sequeue is start !   *\n"); Log("*                             *\n"); Log("*******************************\n"); for(i=0;i<15;i++) { FIFO_IN_Sequeue(s,i+1); } Log("*******************************\n"); Log("*                             *\n"); Log("*   Output Sequeue is start ! *\n"); Log("*                             *\n"); Log("*******************************\n"); for(i=0;i<7;i++) {   FIFO_OUT_Sequeue(s,&X); Log("The OUTPUT data is %d\n",X); }     Log("*******************************\n"); Log("*                             *\n"); Log("*   Read Sequeue is start !   *\n"); Log("*                             *\n"); Log("*******************************\n"); Log("The OUTPUT data is %d\n",Read_Sequeue(s)); Log("*******************************\n"); Log("*                             *\n"); Log("*    Second Into Sequeue is start !   *\n"); Log("*                             *\n"); Log("*******************************\n"); for(i=0;i<7;i++) { FIFO_IN_Sequeue(s,i*2); } Log("***********************************\n"); Log("*                                 *\n"); Log("*   Output all Sequeue is start ! *\n"); Log("*                                 *\n"); Log("***********************************\n"); for(i=0;i<15;i++) {   FIFO_OUT_Sequeue(s,&X); Log("The OUTPUT data is %d\n",X); } }