首页 > 程序开发 > 软件开发 > C++ >

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

2018-07-30

C++下环形队列的简单实现。队列,FIFO;分为普通队列和环形队列。它只允许在队头进行删除操作,而在队尾进行插入操作。

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&#39;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;分为普通队列和环形队列。

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

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

相较于普通队列,环形队列(循环队列)则很好的解决了这些问题。

相关文章
最新文章
热点推荐