C++下环形队列的简单实现

c++下环形队列的简单实现

#include <iostream>
#include <string>
using namespace std;
 
class student
{
public:
    student(string name="o",int age=0)
    {
        sname=name;
        iage=age;
    }
    void print()
    {
        cout<<"name:"<<sname<<endl;
        cout<<"age:"<<iage<<endl;
        cout<<endl;
    }
private:
    string sname;
    int iage;
};
class myqueue
{
public:
    myqueue(int c);
    ~myqueue();
    void clearqueue();
    int queuelen();
    bool full();
    bool empty();
    void enterqueue(student element);
    void deletequeue(student &element);
    void traverse();
private:
    int icapacity;
    student *iqueue;//this pointer stands for the whole queue.
    int ilen;
    int head;
    int tail;
};
myqueue::myqueue(int c)
{
    icapacity=c;
    iqueue=new student[icapacity];
    ilen=0;
    head=0;
    tail=0;
    cout<<"this queue's capacity is "<<c<<endl;
}
myqueue::~myqueue()
{
    delete iqueue;
    iqueue=null;
}
void myqueue::clearqueue()
{
    ilen=0;
    head=0;
    tail=0;
}
int myqueue::queuelen()
{
    return ilen;
}
bool myqueue::full()
{
    return ilen == icapacity ? true: false;
}
bool myqueue::empty()
{
    return ilen == 0 ? true: false;
}
void myqueue::enterqueue(student element)//入队，从tail进
{
    if (full()==false)
    {
        iqueue[tail%icapacity]=element;
        //iqueue[tail]=element;
        tail++;
        //tail=tail%icapacity;
        ilen++;
    }
 
}
void myqueue::deletequeue(student &element)//出队，从head出，删除元素就是删除地址，该函数就是指删除首元素。
{
    if(empty()==false)
    {
        element=iqueue[head%icapacity];
        //element=iqueue[head];
        head++;
        //head=head%icapacity;
        ilen--;
    }
}
void myqueue::traverse()//遍历
{
    //cout<<iqueue[0]<<" "<<iqueue[1]<<" "<<iqueue[2]<<" "<<iqueue[3]<<endl;检验的确是循环使用的。
    for(int i=head;i<head+ilen;i++)
    {
 
        iqueue[i%icapacity].print();//ilen or icapacity???
        cout<<endl;
    }
}
 
int main()
{
    /* myqueue *p=new myqueue(4);
    p->enterqueue(10);
    p->enterqueue(12);
    p->enterqueue(14);
    p->enterqueue(16);
    int e=0;//任意赋初值
    p->deletequeue(e);
    cout<<e<<endl;//返回删除的元素的值
    cout<<endl;
    p->traverse();
    p->enterqueue(20);
    p->traverse();*/
    myqueue *p=new myqueue(4);
    student s1("a",1);
    student s2("b",2);
    student s3("c",3);
    student s4("d",4);
    p->enterqueue(s1);
    p->enterqueue(s2);
    p->enterqueue(s3);
    p->enterqueue(s4);
    p->traverse();
    delete []p;
    p=null;
    return 0;
}

队列，fifo；分为普通队列和环形队列。

它只允许在队头进行删除操作，而在队尾进行插入操作。

普通队列效率低，速度慢，且容易造成内存空间浪费。

相较于普通队列，环形队列（循环队列）则很好的解决了这些问题。