The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

动态循环队列模板类——链表实现

 

//template_by_abilitytao_ACM
//Begin_template_myqueue
//这是一个非常高效的循环链表队列
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

struct node {
    int data;
    node* next;
};

class myqueue
{
private:
    node *prear;
    int lenth;
public:
    myqueue();
    int push(int num);
    int pop();
    int front();
    int rear();
    int len();
    bool empty();
    bool full();
    
};


myqueue::myqueue()
{

    prear=new node;
    prear->data=0x7fffffff;
    prear->next=prear;
    lenth=0;
}


int myqueue::push(int num)//入队成功返回1，否则返回0 。问：（返回0有可能吗？如果内存不够系统内部有 返回值吗，猜：返回null?）
{
    {
        node *p=new node;
        p->data=num;
        p->next=prear->next;
        prear->next=p;
        prear=p;
        lenth++;
        return 1;
    }
    return 0;
}

int myqueue::pop()//如果出队成功返回1，勾着否则返回0；
{
    if(prear->next==prear)
        return 0;
    node *p=prear->next;
    node *q=prear->next->next;
    p->next=q->next;
    delete q;
    if(p=p->next)
        prear=p;
    --lenth;
}

int myqueue::front()//队列为空返回0，否则返回队首元素的值
{

    if(prear->next==prear)
        return 0;
    node*p=prear->next->next;
    return p->data;

}

int myqueue::rear()//队列为空返回值为0，否则返回队尾元素的值
{
    if(prear->next==prear)
        return 0;
    return prear->data;
}

int myqueue::len()
{
    return lenth;
}

bool myqueue::empty()
{

    if(prear->next==prear)
        return true;
    else
        return false;
}

bool myqueue::full()//为了提高本模板的兼容性，故提供此函数，其实函数的返回值永远不可能为1；
{
    return false;
}
//endtemplate_by_abilitytao_ACM

////////////////////////////////////////////////////////////////////下面是测试数据////////////////////////////////////////////////////////////////////////////
int main ()
{

    myqueue test;
    int a=test.len();
    bool b=test.empty();
    test.push(1);
    test.push(2);
    a=test.front();
    a=test.rear();
    a=test.len();
    b=test.empty();
    b=test.full();
    a=test.pop();
    a=test.front();
    a=test.rear();
    a=test.pop();
    a=test.front();
    a=test.rear();

}

posted on 2009-03-02 21:00 abilitytao 阅读(1620) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理