队列及其实现-白红宇

队列及其实现

阅读量：5111 次

发布时间：2019-06-13

本文共 5756 字，大约阅读时间需要 19 分钟。

　　和栈相反，队列是一种先进先出的特殊线性表，它只允许在表的一段进行插入，而在另一端删除元素，这里需要注意，队列不允许在中间部位进行操作，队列通常有两种实现方式：顺序结构实现、链式结构实现。

队列有下面几个操作：

InitQueue（）　　 ——初始化队列

EnQueue（） ——进队列

DeQueue（） ——出队列

IsQueueEmpty（）——判断队列是否为空

IsQueueFull（） ——判断队列是否已满

　　顺序结构实现如下：

　　对于顺序队列，入队的新元素是在线性表的最后，时间复杂度O(1)，出队时需要将后续的所有元素向前移动，时间复杂度时O(n)，那么如何使它的时间复杂度降低到O(1)呢？

　　定义front使其始终代表头的下标

出队时将对头元素返回，且front++

　　定义rear使其始终代表队尾下一个元素的下标

入队时将新元素插入，且rear++

　　顺序队列的关键状态

初始状态：length == 0 ， front == 0 ， rear == 0；

空队列状态：length == 0 ， front == rear；

满队列状态：length == capacity ， front == rear；

　　循环使用队列中的空间

入列：rear = (rear + 1）%capacity；

出列：front = (front + 1)%capacity；

小结：优化的顺序队列利用顺序空间提高出列操作的效率。

　　链式结构如下：

对于链式队列，入队的新元素是在线性表的最后，时间复杂度O(n)，出队时需要将后续的所有元素向前移动，时间复杂度时O(1)，那么如何使它的时间复杂度降低到O(1)呢？

　　定义rear指针始终向链表中的最后一个元素

入队时将新元素通过rear插入队尾，且将rear指向新元素

　　链式队列的关键状态

空队列状态：front == NULL ， rear == NULL；

　　关键操作

入队：

　rear -> next = node；

　rear = node；

　node -> next = NULL；

出列：

　front = front -> next；

小结：优化的链式队列定义rear指针向队尾元素提高出列操作的效率。

　　但是这样的话，空间利用率不高，所以最后再介绍一种队列：循环队列。为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，如下图：

　　这里需要注意的是，循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。在C语言中不能够用动态分配的一位数组来实现循环队列，如果用户的应用程序中设有循环队列的话，则必须为它设定一个最长队列长度；若用户无法预估所用队里的最大长度，则应该采用链式队列。具体实现代码如下：

1 #include
      
         2   3 #include
       
          4   5 #define MAXSIZE 50                                    //队列是最大长度  6   7 typedef struct                                        //点实体结构  8 {  9  10     char name[10]; 11  12     char id[8]; 13  14     float x,y,z; 15  16 }Point; 17  18 typedef struct                                        //循环列表结构 19 { 20  21     Point *base; 22  23     int front; 24  25     int rear; 26  27 }SqQueue; 28  29 int initQueue(SqQueue *Q); 30  31 int isEmpty(SqQueue *Q); 32  33 int isFull(SqQueue *Q); 34  35 int enQueue(SqQueue *Q,Point e); 36  37 int deQueue(SqQueue *Q,Point *e); 38  39 int main(void) 40 { 41  42     char choice; 43  44     Point temp; 45  46     SqQueue *Q = (SqQueue *)malloc(sizeof(SqQueue));    //声明队列 47  48     initQueue(Q);                                        //构造队列 49  50     printf("请选择操作：\n" 51  52         "a:入队    b:出队    q:退出\n"); 53  54     while(scanf("%c", &choice) == 1) 55     { 56         //元素入队 57  58         if(choice == 'a') 59         { 60  61             printf("请输入点名:\n"); 62  63             scanf("%s", &temp.name); 64  65             printf("请输入点号:\n"); 66  67             scanf("%s", &temp.id); 68  69             printf("请输入x坐标:\n"); 70  71             scanf("%f", &temp.x); 72  73             printf("请输入y坐标:\n"); 74  75             scanf("%f", &temp.y); 76  77             printf("请输入z坐标:\n"); 78  79             scanf("%f", &temp.z); 80  81             enQueue(Q, temp);                                //插入元素到队尾 82  83             fflush(stdin);                                    //清空输入缓存 84  85             printf("请选择操作：\n"         86  87                 "a:入队    b:出队    q:退出\n"); 88         } 89  90         //元素出队 91         else if(choice == 'b') 92         { 93             //删除失败的情况 94  95             if(deQueue(Q, &temp) == -1) 96  97             { 98  99                 fflush(stdin);                                    //清空输入缓存100 101                 printf("请选择操作：\n"102 103                     "a:入队    b:出队    q:退出\n");104 105                 continue;106 107             }108 109             printf("删除的节点的信息为：\n"110 111                 "点名：%s\n"112 113                 "点号：%s\n"114 115                 "x坐标：%.2f\n"116 117                 "y坐标：%.2f\n"118 119                 "z坐标：%.2f\n",120 121                 temp.name, temp.id, temp.x, temp.y, temp.z);122 123             fflush(stdin);                                    //清空输入缓存124 125             printf("请选择操作：\n"126 127                 "a:入队    b:出队    q:退出\n");128 129         }130 131         //退出132 133         else if(choice == 'q')134 135             break;136 137         //输入错误138 139         else140 141         {142 143             fflush(stdin);                                    //清空输入缓存144 145             printf("输入错误，输入应该为‘a’或‘b’或‘q’!\n"146 147                 "请选择操作：\n"148 149                 "a:入队    b:出队    q:退出\n");150 151         }152 153     }154 155     free(Q->base);156 157     free(Q);158 159     printf("Done!\n");160 161     return 0;162 163 }164 165 //构造一个空队列166 167 int initQueue(SqQueue *Q)168 169 {170 171     Q->base=(Point *)malloc(MAXSIZE * sizeof(Point));172 173     if(!Q->base)174 175     {176 177         printf("分配空间错误，初始化失败!\n");178 179         return -1;180 181     }182 183     Q->front = Q->rear = 0;184 185     printf("队列初始化成功!\n");186 187     return 0;188 189 }190 191 //判断队列是否为空192 193 int isEmpty(SqQueue *Q)194 195 {196 197     if(Q->front == Q->rear)198 199         return 1;200 201     else 202 203         return 0;204 205 }206 207 //判断队列是否为满208 209 int isFull(SqQueue *Q)210 211 {212 213     if(Q->front == (Q->rear + 1) % MAXSIZE)214 215         return 1;216 217     else 218 219         return 0;220 221 }222 223 //插入元素e为Q的新队尾元素224 225 int enQueue(SqQueue *Q,Point e)226 {227 228     if(isFull(Q))229 230     {231 232         printf("队列已满，插入失败!\n");233 234         return -1;235 236     }237 238 239 240     Q->base[Q->rear] = e;241 242     Q->rear = (Q->rear + 1) % MAXSIZE;243 244     printf("插入成功!\n");245 246     return 0 ;247 248 }249 250 //删除Q的队头元素，用e返回其值251 252 int deQueue(SqQueue *Q,Point *e)253 254 {255 256     if(isEmpty(Q)) 257 258     {259 260         printf("队列为空，删除失败!\n");261 262         return -1;263 264     }265     *e = Q->base[Q->front];266 267     Q->front = (Q->front + 1) % MAXSIZE;268 269     printf("删除成功!\n");270 271     return 0;272 273 }

XHqueue

我用Dev-C++的环境编译之后的结果如下，这里我任意输入了几个例子，以供大家体会：

转载于:https://www.cnblogs.com/lihuidashen/p/4229404.html

你可能感兴趣的文章