顺序循环队列的实现

用数组模拟队列时,我们为了避免数据移动及假溢出而使用循环队列,即当插入数据已经位于数组尾部的下一个位置时,若数组头部有空闲空间,则插入到数组头部;删除时,若删除的元素位于数组尾部,则删除后将队首头移动到数组的头部。为了区分队空还是队满,我们还需要使用一个空闲元素。

#include <bits/stdc++.h>
using namespace std;

class CircularQueue //顺序队列必须为循环队列
{
public:
    CircularQueue(int length) //length代表存放最大元素的个数
    {
        p = new int[length+1]();
        this->len = length+1;
        this->front = this->rear = 0;
        this->cnt = 0;
    }
    bool in(int num);
    bool out();
    bool isFull();
    bool isEmpty();
    int getLength()
    { return this->cnt; } //获取队列长度
    void show();
    ~CircularQueue()
    {
        delete [] p;
    }
private:
    int rear; //指向队尾元素的后一个
    int front; //队首
    int len; //数组长度
    int cnt; //队列中有效元素个数
    int * p; //用于模拟队列数组的首地址
};

bool CircularQueue::isEmpty()
{
    if (rear == front)
        return true;
    else
        return false;
}

bool CircularQueue::isFull()
{
    if ((rear+1) % len == front)
        return true;
    else
        return false;
}

bool CircularQueue::in(int num)
{
    if (this->isFull())
    {
        cout<<"循环队列已满,无法入队!"<<endl;
        return false;
    }
    *(p+rear) = num;
    rear = (rear+1) % len; //注意该行不能单纯rear++,否则数组会越界
    cnt++;
    return true;
}

bool CircularQueue::out()
{
    if (this->isEmpty())
    {
        cout<<"循环队列已空,无法出队!"<<endl;
        return false;
    }
    front = (front+1) % len; //注意该行不能单纯front++,否则数组会越界
    cnt--;
    return true;
}

void CircularQueue::show()
{
    if (this->isEmpty())
    {
        cout<<"循环队列已空,无法显示!"<<endl;
        return;
    }
    for (int i = front; i != rear; i = (i+1) % len)
    {
        cout<<*(p+i)<<" ";
    }
    cout<<endl;
}

int main()
{
    CircularQueue q(5);
    for (int i = 1; i <= 6; i++)
    {
        q.in(i);
        q.show();
    }
    for (int i = 1; i <= 6; i++)
    {
        q.out();
        q.show();
    }
    return 0;
}

main函数中的测试代码运行结果如下:

发表评论

电子邮件地址不会被公开。 必填项已用*标注