devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【头歌】数据结构-队列的应用_头歌数据结构队列的应用

作者：羊村懒王 | 2024-05-14 03:54:03

赞

踩

头歌数据结构队列的应用

 第1关：循环队列

任务描述

本关任务：编写一个循环队列，实现入队、出队操作，判断队空、队满等特殊情况。

相关知识

为了完成本关任务，你需要掌握：1.循环队列定义，2.入队、出队的定义，3.队空、队满的情况。

循环队列定义

循环队列将数组存储区看成是一个首尾相接的环形区域（下图）。当数据存放到尾地址后，下一个地址就跳转到首地址。循环队列定义如下：

 

  1. struct Queue{
  2. int maxSize; // 队列最大长度
  3. int *data; // 数据指针
  4. int front; // 头指针索引
  5. int rear; // 尾指针索引
  6. };
 

 

入队出队定义
 

入队操作：队列未满，在队尾插入一个元素item，使得data[rear+1]=item，若超过存储空间则尾指针索引取模(rear+1)%maxSize；
 

出队操作：队列不空，返回队首元素值data[front]，并移除队首元素front+1，若超过存储空间则头指针索引取模(front+1)%maxSize。
 

队空队满情况
 

初始化创建空队时，令front=rear=0， 其中front指向队首元素，rear指向队尾元素的下一个元素：
 

  • 当队空时：front==rear
  • 当队满时：front==rear 亦成立
 

因此只凭等式front==rear无法判断队空还是队满。 一个方法是少用一个元素空间，约定：队列头指针front在队尾指针rear的下一个位置上作为队列“满”状态的标志（如上图），即：
 

  • 队空时： front==rear
  • 队满时： (rear+1)%maxSize==front
 

编程要求
 

本关的编程任务是补全右侧代码片段isFull、isEmpty、enQueue和deQueue中Begin至End中间的代码，具体要求如下：
 

  • 在isFull中，判断队列是否为满，若满返回true并在一行打印The queue is Full，否则返回false；
  • 在isEmpty中，判断队列是否为空，若空返回true并在一行打印The queue is Empty，否则返回false；
  • 在enQueue中，实现入队操作：将元素item加入队列尾部；
  • 在deQueue中，实现出队操作：移除队列首部元素，并返回元素值。
 

测试说明
 

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
 

以下是平台的测试样例：
 

测试输入： 10 7 enqueue 30 enqueue 98 dequeue enqueue 96 dequeue dequeue enqueue 0 预期输出： 0 The queue is Empty
 

输入说明： 第一行n m分别表示循环队列大小、入队出队操作记录数量。 接下来m行，enqueue表示入队操作，后面接待入队元素；dequeue表示出队操作。
 

输出说明： 输出m个操作之后的所有队列元素。
 

 

开始你的任务吧，祝你成功！
 

 
 

  1. //
  2. //  queue_.cpp
  3. //  Queue
  4. //
  5. //  Created by ljpc on 2018/5/29.
  6. //  Copyright © 2018年 ljpc. All rights reserved.
  7. //
  8.  
  9. #include "queue_.h"
  10.  
  11.  
  12. void creatQueue(Queue* que, int maxSize)
  13. //  创建一个循环队列指针que，队列最大长度为maxSize
  14. {
  15.     que->maxSize = maxSize;
  16.     que->data = (int*)malloc(maxSize * sizeof(int));
  17.     que->front = que->rear = 0;
  18. }
  19.  
  20. void destroyQueue(Queue* que)
  21. //  释放队列内存空间
  22. {
  23.     free(que->data);
  24. }
  25.  
  26. bool isFull(Queue* que)
  27. //  判断队列que是否为满
  28. //  若满返回 true 并在一行打印  The queue is Full 末尾换行！！！
  29. //  否则返回 false
  30.  
  31. {
  32.     // 请在这里补充代码，完成本关任务
  33.     /********** Begin *********/
  34.     if((que->rear+1)%que->maxSize==que->front)
  35.     {
  36.         printf("The queue is Full\n");
  37.         return true;
  38.     }
  39.     else return false;
  40.     /********** End **********/
  41. }
  42.  
  43. bool isEmpty(Queue* que)
  44. //  判断队列que是否为空
  45. //  若空返回 true 并在一行打印 The queue is Empty 末尾换行！！！
  46. //  否则返回 false
  47. {
  48.     // 请在这里补充代码，完成本关任务
  49.     /********** Begin *********/
  50.     if(que->rear==que->front)
  51.     {
  52.         printf("The queue is Empty\n");
  53.         return true;
  54.     }   
  55.     else 
  56.     return false;
  57.  
  58.     /********** End **********/
  59. }
  60.  
  61. int enQueue(Queue* que, int item)
  62. //  实现入队操作：将元素item加入队列que尾部
  63. //  若队列没满，编写加入操作，返回 1
  64. //  若队列满了，不做任何操作，返回 -1
  65. {
  66.     // 请在这里补充代码，完成本关任务
  67.     /********** Begin *********/
  68.     
  69.     if(isFull(que))
  70.     {
  71.         return -1;
  72.     }
  73.     else 
  74.     {
  75.         que->data[que->rear]=item;
  76.         que->rear=(que->rear+1)%que->maxSize;
  77.         return 1;
  78.     }
  79.     /********** End **********/
  80. }
  81.  
  82. int deQueue(Queue* que)
  83. //  实现出队操作：移除队列que首部元素，并返回元素值
  84. {
  85.     // 请在这里补充代码，完成本关任务
  86.     /********** Begin *********/
  87.     int x;
  88.     if(que->front==que->rear)
  89.     {
  90.         return false;
  91.     }
  92.     else 
  93.     {
  94.         x=que->data[que->front];
  95.         que->front=(que->front+1)%que->maxSize;        
  96.     }
  97.     return x;
  98.  
  99.     /********** End **********/
  100. }
  101.  
  102. void printQueue(Queue* que)
  103. //  打印队列
  104. {
  105.     while (isEmpty(que)==false) {
  106.         int item = deQueue(que);
  107.         printf("%d ", item);
  108.     }
  109. }
 

 第二关-链队列
 

任务描述
 

本关任务：编写一个链队列，实现入队、出队操作，判断队空等特殊情况。
 

相关知识
 

为了完成本关任务，你需要掌握：1.链队列定义，2.入队、出队的定义，3.队空的情况。
 

链队列定义
 

链队列的定义是在单链表的基础上，增加一个尾指针。队列的特点是“先进先出”，因此只需要一头一尾两个指针，就可以快速地在队头取出数据，在队尾插入数据。
 

链队列动态创建节点，不需要预设大小，内存空间不需要连续，入队、出队更容易实现。但是存取速度慢，操作也比数组的方式更加复杂。
 

 

  1. struct Node // 数据节点
  2. {
  3. int data; // 数据类型
  4. Node *next; // 指向下一个节点的指针
  5. };
  6. struct LinkQueue // 链表队列
  7. {
  8. Node *front; // 头指针
  9. Node *rear; // 尾指针
  10. };
 

 

入队出队定义
 

入队操作：
 

  • 第一步：为待入队元素创建数据节点Node* node；
  • 第二步：将队尾节点next指向新节点rear->next = node;
  • 第三步：修改队尾指针rear指向新节点rear = node。
 

出队操作：队列不空，返回队首元素值。
 

  • 第一步：获取队首节点Node *node = front->next，注意front->next才是指向队列头节点，front本身不具备任何意义。
  • 第二步：移除队首节点，修改front->next = node->next；
  • 特殊情况：当队列最后一个元素被删除后，队列尾指针也丢失了，因此需对队尾指针重新赋值，即指向头结点 rear = front。
 

队空情况
 

初始化创建空队时，令rear = front，即队空的情况是rear == front。
 

编程要求
 

本关的编程任务是补全右侧代码片段isEmpty、enQueue和deQueue中Begin至End中间的代码，具体要求如下：
 

  • 在isEmpty中，判断队列是否为空，若空返回true并在一行打印The queue is Empty，否则返回false；
  • 在enQueue中，实现入队操作：将元素item加入队列尾部；
  • 在deQueue中，实现出队操作：移除队列首部元素，并返回元素值。
 

测试说明
 

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
 

以下是平台的测试样例：
 

测试输入： 7 enqueue 30 enqueue 98 dequeue enqueue 96 dequeue dequeue enqueue 0 预期输出： 0 The queue is Empty
 

输入说明： 第一行m分别表示链队列入队出队操作记录数量。 接下来m行，enqueue表示入队操作，后面接待入队元素；dequeue表示出队操作。
 

输出说明： 输出m个操作之后的所有队列元素。
 

 

开始你的任务吧，祝你成功！
 

  1. //
  2. //  queue_.cpp
  3. //  LinkQueue
  4. //
  5. //  Created by ljpc on 2018/5/30.
  6. //  Copyright © 2018年 ljpc. All rights reserved.
  7. //
  8.  
  9. #include "queue_.h"
  10.  
  11. void creatLinkQueue(LinkQueue* que)
  12. //  创建一个循环队列指针que
  13. {
  14.     que->front = (Node*)malloc(sizeof(Node));
  15.     que->rear = que->front;
  16.     que->rear->next = NULL;
  17. }
  18.  
  19. bool isEmpty(LinkQueue* que)
  20. //  判断队列que是否为空
  21. //  若空返回 true 并在一行打印 The queue is Empty 末尾换行！！！
  22. //  否则返回 false
  23. {
  24.     // 请在这里补充代码，完成本关任务
  25.     /********** Begin *********/
  26.     if(que->front==que->rear)
  27.     {
  28.         printf("The queue is Empty\n");
  29.         return true;
  30.     }
  31.     else 
  32.     return false;
  33.  
  34.     /********** End **********/
  35. }
  36.  
  37. void enQueue(LinkQueue* que, int item)
  38. //  实现入队操作：将元素item加入队列que尾部
  39. {
  40.     // 请在这里补充代码，完成本关任务
  41.     /********** Begin *********/
  42.     Node *newque=(Node*)malloc(sizeof(Node));
  43.     if(newque!=NULL)
  44.     {
  45.         newque->data=item;
  46.         newque->next=NULL;
  47.         que->rear->next=newque;
  48.         que->rear=newque;
  49.     }
  50.     /********** End **********/
  51. }
  52.  
  53. int deQueue(LinkQueue* que)
  54. //  实现出队操作：移除队列que首部元素，并返回元素值
  55. {
  56.     // 请在这里补充代码，完成本关任务
  57.     /********** Begin *********/
  58.     Node *p;
  59.     int item;
  60.     if(que->front==que->rear)
  61.        return false;
  62.  
  63.     p=que->front->next;
  64.     que->front->next=p->next;
  65.     item=p->data;
  66.  
  67.     if(que->rear==p)
  68.     {
  69.         que->rear=que->front;
  70.     }
  71.     free(p);
  72.     return item;
  73.     /********** End **********/
  74. }
  75.  
  76. void printQueue(LinkQueue* que)
  77. //  打印队列
  78. {
  79.     while (isEmpty(que)==false) {
  80.         int item = deQueue(que);
  81.         printf("%d ", item);
  82.     }
  83. }
 

第3关：单链表循环队列
 

任务描述
 

本关任务：编写一个单链表循环队列，实现入队、出队操作，判断队空等特殊情况。
 

相关知识
 

为了完成本关任务，你需要掌握：1.单链表循环队列定义，2.入队、出队的定义，3.队空的情况。
 

单链表循环队列
 

单链表循环队列设一个尾指针rear，不设头指针。队尾添加数据的时候，只需要在rear和rear->next之间插入该数据节点，然后将rear指向这个节点。因为没有头指针，所以添加一个整形变量size_来判定队列空的情况。
 

 

 

  1. struct Node // 数据节点
  2. {
  3. int data; // 数据类型
  4. Node *next; // 指向下一个节点的指针
  5. };
  6. struct CycleQueue // 循环链表队列
  7. {
  8. int size_; // 目前队列元素个数
  9. Node *rear; // 尾指针
  10. };
 

入队出队定义
 

注意初始队列时，尾指针rear = NULL以及rear->next = NULL。
 

入队操作：
 

 

  • 为待入队元素创建数据节点Node* node；
  • 如果队列为空，则尾节点指向新节点rear = node，rear->next指向队首节点rear->next = node。
  • 如果队列非空，则在rear和rear->next之间插入新节点： 
     
  
    1. Node *temp = rear->next;
    2. rear->next = node;
    3. node->next = temp;
    4. rear = node;
    5. rear->next = temp;
 

出队操作：队列不空，返回队首元素值。
 

 

  • 第一步：获取队首节点Node *node = rear->next;
  • 第二步：移除队首节点，修改rear->next = node->next。
 

队空情况
 

队列中不含数据节点，通过变量size_来判定队列空的情况。
 

编程要求
 

本关的编程任务是补全右侧代码片段isEmpty、enQueue和deQueue中Begin至End中间的代码，具体要求如下：
 

  • 在isEmpty中，判断队列是否为空，若空返回true并在一行打印The queue is Empty，否则返回false；
  • 在enQueue中，实现入队操作：将元素item加入队列尾部；
  • 在deQueue中，实现出队操作：移除队列首部元素，并返回元素值。
 

测试说明
 

平台将自动编译补全后的代码，并生成若干组测试数据，接着根据程序的输出判断程序是否正确。
 

以下是平台的测试样例：
 

测试输入： 7 enqueue 30 enqueue 98 dequeue enqueue 96 dequeue dequeue enqueue 0 预期输出： 0 The queue is Empty
 

输入说明： 第一行m分别表示链队列入队出队操作记录数量。 接下来m行，enqueue表示入队操作，后面接待入队元素；dequeue表示出队操作。
 

输出说明： 输出m个操作之后的所有队列元素。
 

 

开始你的任务吧，祝你成功！
 

  1. //
  2. //  queue_.cpp
  3. //  Cycle
  4. //
  5. //  Created by ljpc on 2018/5/30.
  6. //  Copyright © 2018年 ljpc. All rights reserved.
  7. //
  8.  
  9. #include "queue_.h"
  10.  
  11.  
  12. void creatCycleQueue(CycleQueue* que)
  13. //  创建一个循环队列指针que
  14. {
  15.     que->size_ = 0;
  16.     que->rear = NULL;
  17. }
  18.  
  19. bool isEmpty(CycleQueue* que)
  20. //  判断队列que是否为空
  21. //  若空返回 true 并在一行打印 The queue is Empty 末尾换行！！！
  22. //  否则返回 false
  23. {
  24.     // 请在这里补充代码，完成本关任务
  25.     /********** Begin *********/
  26.     if(que->size_==0){
  27.     	printf("The queue is Empty\n");
  28.     	return true;
  29. 	}else{
  30. 		return false;
  31. 	}
  32.  
  33.     /********** End **********/
  34.  
  35. }
  36.  
  37. void enQueue(CycleQueue* que, int item)
  38. //  实现入队操作：将元素item加入队列que尾部
  39. {
  40.     // 请在这里补充代码，完成本关任务
  41.     /********** Begin *********/
  42.     Node *newque=(Node*)malloc(sizeof(Node));
  43.     newque->data=item;
  44.     if(que->size_>0)
  45.     {
  46.         newque->next=que->rear->next;
  47.         que->rear->next=newque;
  48.         que->rear=newque;
  49.         que->size_++;
  50.     }
  51.     else
  52.     {
  53.         que->rear=newque;
  54.         que->rear->next=newque;
  55.         que->size_++;
  56.     }
  57.  
  58.     /********** End **********/
  59.  
  60. }
  61.  
  62. int deQueue(CycleQueue* que)
  63. //  实现出队操作：移除队列que首部元素，并返回元素值
  64. {
  65.     // 请在这里补充代码，完成本关任务
  66.     /********** Begin *********/
  67.     Node *p;
  68.     int item;
  69.     if(isEmpty(que))
  70.         return false;
  71.     if(que->size_==1)
  72.     {
  73.     	item=que->rear->data;
  74.         p=que->rear;
  75. 	    que->rear=NULL;
  76. 	    free(p);
  77.     } 
  78.     else if(que->size_>1)   
  79.     {
  80.         p=que->rear->next;
  81.         que->rear->next=p->next;
  82.         item=p->data;
  83.         free(p);
  84.     }
  85.     que->size_--;
  86.     return item;
  87.     /********** End **********/
  88.  
  89. }
  90.  
  91. void printQueue(CycleQueue* que)
  92. //  打印队列
  93. {
  94.     while (isEmpty(que)==false) {
  95.         int item = deQueue(que);
  96.         printf("%d ", item);
  97.     }
  98. }
 


                

        
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/567158
推荐阅读
相关标签
Copyright ©  2003-2013 www.wpsshop.cn  版权所有，并保留所有权利。

  
闽ICP备14008679号