队列的2种实现

 队列一般有以下接口：

queue();构造函数

int empty();

void put(Item);

Item get();

链表实现如下：

#include<iostream>
using namespace std;

template<class Item>
class Queue
{
private:
    struct node
    {
        Item item;
        node *next;
        node(Item x):item(x),next(0){}
    };
    typedef node *Link;
    Link head,tail;
public:
    Queue() { head=0;}
    bool empty()const { return head==0; }
    void put(Item x)
    {
        Link t=tail;
        tail=new node(x);//tail始终指向最后一项
        if(head==0)
            head=tail;
        else
            t->next=tail;
    }
    Item get()
    {
          
        Link t=head;
        Item t2=head->item;
        head=head->next;
        delete t;
        return t2;
    }
};

int main()
{
    Queue<int> q;
    cout<<q.empty()<<endl;
    for(int i=0;i<10;i++)
        q.put(i);
    for(int i=0;i<10;i++)
        cout<<q.get()<<ends;
     
}

我们设立了两个指针，head和tail，put时，使tail始终指向最后一个元素，get时，修改head。

使用数组实现，如果head%N==tail，我们认为head跟tail 重合，此时对列为空，但是如果一个put操作造成了他们相等，我们认为此时的队列为满，通常我们不检查这样的错误条件，但是我们设定数组长度的时候，会将它设为为客户将在队列中放置的元素的最大数目大1，因此我们可以为这个程序加上这样的检查。

#include<iostream>
using namespace std;
template<class Item>
class Queue
{
private:
     Item *q;
     int N,head,tail;
public:
    Queue(int maxN)
    {
        q=new Item[maxN+1];
        N=maxN+1;
        head=N;tail=0;
    }
    int empty() const { return head%N==tail; }
    void put(Item item)
    {
         q[tail++]=item;
         tail=tail%N;
    }
    Item get()
    {
        head=head%N;
        return q[head++];
    }
};

int main()
{
    Queue<int> q(20);
    for(int i=0;i<10;i++)
        q.put(i);
    cout<<q.empty()<<endl;
    for(int i=0;i<10;i++)
        cout<<q.get()<<ends;
    cout<<endl<<q.empty()<<endl;
}

 （严蔚敏教材上面是启始：Q.front=Q.rear=0。）