【头歌】数据结构 |
您所在的位置：网站首页 › dequeue是前出还是后出 › 【头歌】数据结构 |
【头歌】数据结构
|
第1关：循环队列 任务描述 本关任务：编写一个循环队列，实现入队、出队操作，判断队空、队满等特殊情况。 相关知识 为了完成本关任务，你需要掌握：1.循环队列定义，2.入队、出队的定义，3.队空、队满的情况。 循环队列定义 循环队列将数组存储区看成是一个首尾相接的环形区域（下图）。当数据存放到尾地址后，下一个地址就跳转到首地址。循环队列定义如下： struct Queue{int maxSize; // 队列最大长度int *data; // 数据指针int front; // 头指针索引int rear; // 尾指针索引};
入队出队定义 入队操作：队列未满，在队尾插入一个元素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个操作之后的所有队列元素。 开始你的任务吧，祝你成功！ // // queue_.cpp // Queue // // Created by ljpc on 2018/5/29. // Copyright © 2018年 ljpc. All rights reserved. // #include "queue_.h" void creatQueue(Queue* que, int maxSize) // 创建一个循环队列指针que，队列最大长度为maxSize { que->maxSize = maxSize; que->data = (int*)malloc(maxSize * sizeof(int)); que->front = que->rear = 0; } void destroyQueue(Queue* que) // 释放队列内存空间 { free(que->data); } bool isFull(Queue* que) // 判断队列que是否为满 // 若满返回 true 并在一行打印 The queue is Full 末尾换行！！！ // 否则返回 false { // 请在这里补充代码，完成本关任务 /********** Begin *********/ if((que->rear+1)%que->maxSize==que->front) { printf("The queue is Full\n"); return true; } else return false; /********** End **********/ } bool isEmpty(Queue* que) // 判断队列que是否为空 // 若空返回 true 并在一行打印 The queue is Empty 末尾换行！！！ // 否则返回 false { // 请在这里补充代码，完成本关任务 /********** Begin *********/ if(que->rear==que->front) { printf("The queue is Empty\n"); return true; } else return false; /********** End **********/ } int enQueue(Queue* que, int item) // 实现入队操作：将元素item加入队列que尾部 // 若队列没满，编写加入操作，返回 1 // 若队列满了，不做任何操作，返回 -1 { // 请在这里补充代码，完成本关任务 /********** Begin *********/ if(isFull(que)) { return -1; } else { que->data[que->rear]=item; que->rear=(que->rear+1)%que->maxSize; return 1; } /********** End **********/ } int deQueue(Queue* que) // 实现出队操作：移除队列que首部元素，并返回元素值 { // 请在这里补充代码，完成本关任务 /********** Begin *********/ int x; if(que->front==que->rear) { return false; } else { x=que->data[que->front]; que->front=(que->front+1)%que->maxSize; } return x; /********** End **********/ } void printQueue(Queue* que) // 打印队列 { while (isEmpty(que)==false) { int item = deQueue(que); printf("%d ", item); } } 第二关-链队列 任务描述 本关任务：编写一个链队列，实现入队、出队操作，判断队空等特殊情况。 相关知识 为了完成本关任务，你需要掌握：1.链队列定义，2.入队、出队的定义，3.队空的情况。 链队列定义 链队列的定义是在单链表的基础上，增加一个尾指针。队列的特点是“先进先出”，因此只需要一头一尾两个指针，就可以快速地在队头取出数据，在队尾插入数据。 链队列动态创建节点，不需要预设大小，内存空间不需要连续，入队、出队更容易实现。但是存取速度慢，操作也比数组的方式更加复杂。 struct Node // 数据节点{int data; // 数据类型Node *next; // 指向下一个节点的指针};struct LinkQueue // 链表队列{Node *front; // 头指针Node *rear; // 尾指针};
入队出队定义 入队操作： 第一步：为待入队元素创建数据节点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个操作之后的所有队列元素。 开始你的任务吧，祝你成功！ // // queue_.cpp // LinkQueue // // Created by ljpc on 2018/5/30. // Copyright © 2018年 ljpc. All rights reserved. // #include "queue_.h" void creatLinkQueue(LinkQueue* que) // 创建一个循环队列指针que { que->front = (Node*)malloc(sizeof(Node)); que->rear = que->front; que->rear->next = NULL; } bool isEmpty(LinkQueue* que) // 判断队列que是否为空 // 若空返回 true 并在一行打印 The queue is Empty 末尾换行！！！ // 否则返回 false { // 请在这里补充代码，完成本关任务 /********** Begin *********/ if(que->front==que->rear) { printf("The queue is Empty\n"); return true; } else return false; /********** End **********/ } void enQueue(LinkQueue* que, int item) // 实现入队操作：将元素item加入队列que尾部 { // 请在这里补充代码，完成本关任务 /********** Begin *********/ Node *newque=(Node*)malloc(sizeof(Node)); if(newque!=NULL) { newque->data=item; newque->next=NULL; que->rear->next=newque; que->rear=newque; } /********** End **********/ } int deQueue(LinkQueue* que) // 实现出队操作：移除队列que首部元素，并返回元素值 { // 请在这里补充代码，完成本关任务 /********** Begin *********/ Node *p; int item; if(que->front==que->rear) return false; p=que->front->next; que->front->next=p->next; item=p->data; if(que->rear==p) { que->rear=que->front; } free(p); return item; /********** End **********/ } void printQueue(LinkQueue* que) // 打印队列 { while (isEmpty(que)==false) { int item = deQueue(que); printf("%d ", item); } } 第3关：单链表循环队列任务描述 本关任务：编写一个单链表循环队列，实现入队、出队操作，判断队空等特殊情况。 相关知识 为了完成本关任务，你需要掌握：1.单链表循环队列定义，2.入队、出队的定义，3.队空的情况。 单链表循环队列 单链表循环队列设一个尾指针rear，不设头指针。队尾添加数据的时候，只需要在rear和rear->next之间插入该数据节点，然后将rear指向这个节点。因为没有头指针，所以添加一个整形变量size_来判定队列空的情况。
入队出队定义 注意初始队列时，尾指针rear = NULL以及rear->next = NULL。 入队操作：
出队操作：队列不空，返回队首元素值。
队空情况 队列中不含数据节点，通过变量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个操作之后的所有队列元素。 开始你的任务吧，祝你成功！ // // queue_.cpp // Cycle // // Created by ljpc on 2018/5/30. // Copyright © 2018年 ljpc. All rights reserved. // #include "queue_.h" void creatCycleQueue(CycleQueue* que) // 创建一个循环队列指针que { que->size_ = 0; que->rear = NULL; } bool isEmpty(CycleQueue* que) // 判断队列que是否为空 // 若空返回 true 并在一行打印 The queue is Empty 末尾换行！！！ // 否则返回 false { // 请在这里补充代码，完成本关任务 /********** Begin *********/ if(que->size_==0){ printf("The queue is Empty\n"); return true; }else{ return false; } /********** End **********/ } void enQueue(CycleQueue* que, int item) // 实现入队操作：将元素item加入队列que尾部 { // 请在这里补充代码，完成本关任务 /********** Begin *********/ Node *newque=(Node*)malloc(sizeof(Node)); newque->data=item; if(que->size_>0) { newque->next=que->rear->next; que->rear->next=newque; que->rear=newque; que->size_++; } else { que->rear=newque; que->rear->next=newque; que->size_++; } /********** End **********/ } int deQueue(CycleQueue* que) // 实现出队操作：移除队列que首部元素，并返回元素值 { // 请在这里补充代码，完成本关任务 /********** Begin *********/ Node *p; int item; if(isEmpty(que)) return false; if(que->size_==1) { item=que->rear->data; p=que->rear; que->rear=NULL; free(p); } else if(que->size_>1) { p=que->rear->next; que->rear->next=p->next; item=p->data; free(p); } que->size_--; return item; /********** End **********/ } void printQueue(CycleQueue* que) // 打印队列 { while (isEmpty(que)==false) { int item = deQueue(que); printf("%d ", item); } } |
【本文地址】