首页 > 代码库 > 【队列】基于循环数组的实现
【队列】基于循环数组的实现
请完成以下队列类的实现：（请注意数组实现应该为循环数组）
enum ErrorCode
{
success,
underflow,
overflow
};
const int maxQueue = 100;
template <class QueueEntry>
class MyQueue
{
public:
MyQueue();
bool empty() const; // 判断队列是否为空
ErrorCode append(const QueueEntry &item); // 入队操作
ErrorCode serve();// 出队操作
ErrorCode retrieve(QueueEntry &item) const; // 获取队头元素
bool full() const; // 判断队列是否已满
int size() const; // 获取队列已有元素个数
void clear(); // 清除队列所有元素
ErrorCode retrieve_and_serve(QueueEntry &item); // 获取队头元素并出队
private:
int front; // 队头下标
int rear; // 队尾下标
QueueEntry entry[100]; // 队列容器
};
Problem Source: 第二周 5班
解题思路：
实现循环数组
Circular arrays（循环数组）
将数组设想为一个循环的，而非线性的； 用两个下标front和rear记录队头和队尾位置； 添加元素时，rear右移，将元素置于rear位置。当rear等于max时(last index), rear 置 0. 元素出队时，删除位于front位置的元素，然后front右移. 当front 等于 max时, 置 front 为 0。
Boundary conditions
问题：无法区分满队列与空队列。
解决方法:
1. 在数组中空一个位置；
2. 使用一个布尔量表示队列是否满。当rear刚好到达front之前时，置 此标志为true.
3. 使用一个计数器（ counter）以记录队列中的元素个数。
此处代码采用第一种解决办法：
1.front始终指向队列第一个元素，即总是放着东西的；
rear始终指向队列的下一个位置，即总是空着的；
2.假设数组开到100，那么队列满时，实际长度为99，判断为满：(rear + 1) % 100 == front
判断为空：front==rear
3.当排到数组尾部，要跳到头部来继续进行循环。
实现代码：
enum ErrorCode { success, underflow, overflow};const int maxQueue = 100;template <class QueueEntry>class MyQueue{public: MyQueue(); bool empty() const; ErrorCode append(const QueueEntry &item); ErrorCode serve(); ErrorCode retrieve(QueueEntry &item) const; bool full() const; int size() const; void clear(); ErrorCode retrieve_and_serve(QueueEntry &item);private: int front; int rear; QueueEntry entry[100]; };template <class QueueEntry>MyQueue<QueueEntry>::MyQueue() { //初始化 front = rear = 0;}template <class QueueEntry>bool MyQueue<QueueEntry>:: empty() const { //判断队列是否为空 if (front == rear) return true; else return false; }template <class QueueEntry>ErrorCode MyQueue<QueueEntry>::append(const QueueEntry &item) {//入队 if (full()) { return overflow; } else { entry[rear] = item; rear++; if (rear == 100) rear = 0;//从数组头部继续进行循环 return success; }}template <class QueueEntry>ErrorCode MyQueue<QueueEntry>::serve() { //出队 if (empty()) { return underflow; } else { front++; if (front == 100) front = 0; return success; }}template <class QueueEntry>ErrorCode MyQueue<QueueEntry>::retrieve(QueueEntry &item) const { //取队头 if (empty()) { return underflow; } else { item = entry[front]; return success; }}template <class QueueEntry>bool MyQueue<QueueEntry>::full() const { //判断队列是否已满 if ((rear + 1) % 100 == front) return true; else return false;}template <class QueueEntry>int MyQueue<QueueEntry>::size() const { //判断队的长度 if (front <= rear) { return (rear - front); } else { return (100 - front + rear); }}template <class QueueEntry>void MyQueue<QueueEntry>::clear() { //清除队列 rear = front = 0;}template <class QueueEntry>ErrorCode MyQueue<QueueEntry>::retrieve_and_serve(QueueEntry &item) {//取队头并出队 ErrorCode flag; flag = retrieve(item); serve(); return flag;}
（本博文或多或少参考过其他网上资料，但时间已久忘记当初的参考了，在此对他们表示感谢！）
【队列】基于循环数组的实现