【队列】基于循环数组的实现

Description

请完成以下队列类的实现：（请注意数组实现应该为循环数组）

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;
}

（本博文或多或少参考过其他网上资料，但时间已久忘记当初的参考了，在此对他们表示感谢！）