【数据结构笔记】队的实现（C++）
队的概念 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行删除操作的端称为队头，进行插入操作的端称为队尾。队分为顺序队和链表队。
顺序队 1）.定义 建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素。一个是队尾指针rear，它指向下一个入队元素的存储位置。每次在队尾插入一个元素是，rear增1；在队头删除一个元素时，front增1。顺序队即队列的数组实现。 空队列：当front=rear时，队列中没有任何元素，称为空队列。 2）.假上溢 当rear增加到指向分配的连续空间之外时，队列无法再插入新元素，但这时往往还有大量可用空间未被占用。 3）.循环队列 针对假上溢问题。有个较好的解决方法，就是对已经申请的(数组)内存重复利用。这就是我们所说的循环队列。 循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。循环队列可以更简单防止假上溢的发生，但队列大小是固定的。 在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。 因此，队列判空的条件是front=rear；队列判满的条件是front=（rear+1)%MaxSize。 4） .顺序队代码实现
#pragma once enum Error_code { success, fail, range_error, underflow, overflow, fatal, not_present, duplicate_error, entry_inserted, entry_found, internal_error }; const int maxqueue = 10; //设置队列长度 typedef char Queue_entry; // The program will use stacks with float entries. class Queue { public: Queue(); bool empty() const; Error_code serve(); Error_code append(const Queue_entry& item); Error_code retrieve(Queue_entry& item) const; protected: int count; int front, rear; Queue_entry entry[maxqueue]; }; Queue::Queue() { count = 0; rear = 0; front = 0; } bool Queue::empty() const { return front==rear; } Error_code Queue::append(const Queue_entry& item)//插入一个元素 { if (count >= maxqueue) return overflow;//如果大于数组长度，返回溢出 count++; rear = ((rear + 1) == maxqueue) ? 0 : (rear + 1);//如果队尾元素加1为队列的长度，则从0开始，如果不为队尾长度则为rear + 1。这里就体现了循环队列。 entry[rear] = item;//将要插的元素以引用形式赋给队尾 return success; } Error_code Queue::serve()//删掉一个元素 { if (count <= 0) return underflow;//如果小于0，则说明队列中无元素 count--; front = ((front + 1) == maxqueue) ? 0 : (front + 1);//循环队列 return success; } Error_code Queue::retrieve(Queue_entry& item) const//返回队头元素 { if (count <= 0) return underflow; item = entry[front]; return success; } class Extended_queue : public Queue { public: bool full() const; int size() const; void clear(); Error_code serve_and_retrieve(Queue_entry& item); }; bool Extended_queue::full() const { return front==(rear+1)%maxqueue; } int Extended_queue::size() const { return count; } void Extended_queue::clear() { count = 0; rear = 0; front = 0; } Error_code Extended_queue::serve_and_retrieve(Queue_entry& item)//删除并返回队首元素 { if (count <= 0) return underflow; count--; front = ((front + 1) == maxqueue) ? 0 : (front + 1); item = entry[front]; return success; } 链表队 1).定义 链表队列采用的FIFO(first in first out)，新元素总是被插入到链表的尾部，而读取的时候总是从链表的头部开始读取。每次读取一个元素，释放一个元素。所谓的动态创建，动态释放。 2).入队， 出队操作 3).顺序队与链表队的对比 顺序队： 1.顺序储存，内存空间地址连续。 2.可以通过下标方便查找具体元素，但插入和删除元素比较困难。 3.长度固定，类型固定。 链表队： 1.内存地址不连续。 2.不方便找到具体元素，但是在指定元素后插入删除很方便。 3.长度不固定，任意增添删除节点。 4).链表队代码实现 #pragma once typedef int Node_entry; struct Node { Node_entry entry; Node* next; Node(); Node(Node_entry item, Node* add_on = nullptr); }; Node::Node() { next = nullptr; } Node::Node(Node_entry item, Node* add_on) { entry = item; next = add_on; } enum Error_code { success, fail, range_error, underflow, overflow, fatal, not_present, duplicate_error, entry_inserted, entry_found, internal_error }; typedef int Queue_entry; class Queue { public: Queue(); bool empty() const; Error_code append(const Queue_entry &item); Error_code serve(); Error_code retrieve(Queue_entry &item) const; ~Queue();//析构函数 Queue(const Queue &original);//拷贝构造函数 void operator =(const Queue &original);//运算符函数重载 protected: Node *front, *rear; };//类里的内容与顺序队类内容相同，保证接口相同 Queue::Queue() { front=rear=NULL; } Error_code Queue::append(const Queue_entry &item) { Node *new_rear=new Node(item);//构建新结点，结点内数据为引用带入的item if(new_rear==NULL) return overflow;//如果新结点没有构造成功，返回溢出 if(rear==NULL) front=rear=new_rear;//如果尾指针为空，说明队列为空，新建的结点即为首也为尾 else { rear->next=new_rear;//尾的下一个为新 rear=new_rear;//新结点为尾 } return success; } Error_code Queue::serve() { if (front==NULL) return underflow;//如果队列为空 Node *old_front=front;//设置临时结点为首 front=old_front->next;//将临时结点的下一个置为首 if(front==NULL) rear=NULL;//如果删完后首为空说明队列已经全部删完 delete old_front;//删除临时结点 return success; } Error_code Queue::retrieve(Queue_entry &item) const { if (front==NULL) return underflow; item=front->entry; return success; } Queue::~Queue() { while(!empty())//如果队列不为空就一直删除直到为空为止 serve(); } Queue::Queue(const Queue ©) { Node *copy_node=copy.front;//copy首结点 front=rear=NULL;//置空 while(copy_node!=NULL) { append(copy_node->entry);//添加元素置为原队列元素内容 copy_node=copy_node->next;//copy结点指向下一个 } } void Queue::operator =(const Queue ©) { while (!empty())serve();//与拷贝构造函数相同，前面加了一步清空队列 Node *copy_node = copy.front; while (copy_node !=NULL) { append(copy_node->entry); copy_node =copy_node->next; } } class Extended_queue: public Queue { public: bool full() const; int size() const; void clear(); Error_code serve_and_retrieve(Queue_entry &item); }; bool Extended_queue::full() const { return false;//无论是否为满都返回失败，在真正插结点插失败时才表示队列满 } int Extended_queue::size() const { Node *window = front; int count = 0; while (window != NULL) { window = window->next; count++; } return count; } void Extended_queue::clear() { while(!empty()) serve(); } Error_code Extended_queue:serve_and_retrieve(Queue_entry &item) { if (front==NULL) return underflow;//如果队列为空 item=front->entry; Node *old_front=front;//设置临时结点为首 front=old_front->next;//将临时结点的下一个置为首 if(front==NULL) rear=NULL;//如果删完后首为空说明队列已经全部删完 delete old_front;//删除临时结点 return success; }