大胖的部落格

Just a note
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  112 随笔 :: 0 文章 :: 3 评论 :: 0 Trackbacks
数据结构 ---- 队列
分别用线性表和链表实现的队列：
#include <iostream>

using namespace std;

/////////////// Linear list //////////////////
template <class T>
class Queue {
public:
    Queue(int i=10);
    ~Queue();
    bool IsEmpty() const{return front==rear;}
    bool IsFull() const {return ((front-rear-1)%MaxSize)==0;}
    T First() const;
    T Last() const;
    Queue<T>& Add(const T& t);
    Queue<T>& Delete(T& t);
private:
    int front;
    int rear;
    int MaxSize;
    T*    queue;
};

template <class T>
Queue<T>::Queue(int i)
:front(0),
 rear(0),
 MaxSize(i+1)
{
    queue = new T[MaxSize];
}

template <class T>
Queue<T>::~Queue()
{
    front = 0;
    rear = 0;
    MaxSize = 0;
    delete []queue;
}

template <class T>
T Queue<T>::First() const
{
    if(front != rear) {
        return queue[(front+1)%MaxSize];
    }
}

template <class T>
T Queue<T>::Last() const
{
    if(front != rear) {
        return queue[rear%MaxSize];
    }
}

template <class T>
Queue<T>& Queue<T>::Add(const T &t)
{
    if(!IsFull()) {
        rear = (rear+1)%MaxSize;
        queue[rear] = t;
    }
    return *this;
}

template <class T>
Queue<T>& Queue<T>::Delete(T &t)
{
    if(!IsEmpty()) {
        front = (front+1)%MaxSize;
        t = queue[front];
    }
    return *this;
}


//////////////////// Chain ///////////////////
template <class T>  class LinkedQueue;

template <class T>
class Node {
    friend    LinkedQueue<T>;
    T        data;
    Node<T>*    link;
};

template <class T>
class LinkedQueue {
public:
    LinkedQueue();
    ~LinkedQueue();
    bool IsEmpty() const {return NULL == front;}
    T First() const;
    T Last() const;
    LinkedQueue& Add(const T& t);
    LinkedQueue& Delete(T& t);

private:
    Node<T>*    front;
    Node<T>*    rear;
};

template <class T>
LinkedQueue<T>::LinkedQueue()
{
    front = NULL;
    rear = NULL;
}

template <class T>
LinkedQueue<T>::~LinkedQueue()
{
    Node<T>* next = NULL;
    while(NULL != front) {
        next = front;
        front = front->link;
        delete next;
    }
}

template<class T>
T LinkedQueue<T>::First() const
{
    if(NULL != front) {
        return front->data;
    }
}

template <class T>
LinkedQueue<T>& LinkedQueue<T>::Add(const T &t)
{
    Node<T>* p = new Node<T>;
    p->data = t;
    p->link = NULL;

    if(NULL == front) {
        front = p;
        rear = p;
    }
    else {
        rear->link=p;
        rear = p;
    }
    return *this;
}

template<class T>
LinkedQueue<T>& LinkedQueue<T>::Delete(T& t)
{
    if(NULL != front) {
        Node<T>* p = front;
        t = front->data;
        front = front->link;
        delete p;
    }
    return *this;
}

template <class T>
T LinkedQueue<T>::Last() const
{
    if(NULL != front) {
        return rear->data;
    }
}


int main()
{
    int i;
    LinkedQueue<int> q;
    cout<<boolalpha<<q.IsEmpty()<<endl;
    q.Add(4);
    cout<<q.First()<<','<<q.Last()<<endl;
    cout<<boolalpha<<q.IsEmpty()<<endl;
    q.Add(5);
    cout<<q.First()<<','<<q.Last()<<endl;
    cout<<boolalpha<<q.IsEmpty()<<endl;
    q.Delete(i);
    cout<<q.First()<<','<<q.Last()<<i<<endl;
    cout<<boolalpha<<q.IsEmpty()<<endl;
    q.Delete(i);
    cout<<q.First()<<','<<q.Last()<<i<<endl;
    cout<<boolalpha<<q.IsEmpty()<<endl;
    return 0;
}

posted on 2009-06-29 10:51 大胖 阅读(178) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

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