C++用數組和鏈表分別實現Queue

C++用數組和鏈表分別實現Queue

昨天寫了《C++用數組和鏈表分別實現Stack》，今天就是《C++用數組和鏈表分別實現Queue》，

隊列就是先來的先被處理掉，后來的就等，直到成為先來的，實現起來感覺和棧差不多。

模板好用的，功能強大，有些東東還是寫成模板的好，廢話昨天都說了，今天是不想說的，

博客園的哥們說我的博客不符合推薦到首頁的要求，只好加幾句廢話。

鏈表版

template<typename T,typename container>
class queue
{
public:
bool empty() const
{
return len==0;
}

void checkEmpty()
{
if(empty())
{
throw new exception("隊列中沒有數據");
}
}

T& back()
{
checkEmpty();
return cur->val;
}

const T& back() const
{
return back();
}

void pop()
{
checkEmpty();
if(head->next==cur)
{
delete head->next;
head->next=NULL;
}else
{
node* tmp=head->next;
head->next=tmp->next;
delete tmp;
}
--len;
}

T& front()
{
checkEmpty();
return head->next->val;
}

const T& front() const
{
return front();
}

void push(const T& val)
{
node *tmp=new node(val);
cur->next=tmp;
cur=tmp;
++len;
}

queue()
{
initialize();
}

explicit queue(const container& cont)
{
initialize();
vector <int>::const_iterator iter=cont.begin();
while(iter!=cont.end())
{
push(*iter++);
}
}

~queue()
{
node *tmp;
while(tmp!=NULL)
{
tmp=head;
head=head->next;
delete tmp;
tmp=NULL;
}
delete cur;
}


int size()
{
return len;
}

protected:
typedef struct node1
{
node1 *next;
T val;
node1(T v):val(v),next(NULL){}
}node;

private :
int len;
node *head;
node *cur;
void initialize()
{
head=new node(-1);
cur=head;
len=0;
}
};

數組版

template<typename T,typename container>
class queue
{
public:
bool empty() const
{
return head==rail;
}

void checkEmpty()
{
if(empty())
{
throw new exception("隊列中沒有數據");
}
}

//隊尾元素
T& back()
{
checkEmpty();
return arr[rail-1];
}

const T& back() const
{
return back();
}

//出隊
void pop()
{
checkEmpty();
arr[head++]=0;
}

//隊頭元素
T& front()
{
checkEmpty();
return arr[head];
}

const T& front() const
{
return front();
}

//入隊
void push(const T& val)
{
if(rail>=capacity){
capacity=(rail-head)*2;
T *tmp=new T[capacity];
int j=0;
for(int i=head;i<rail;i++)
{
tmp[j++]=arr[i];
}
delete arr;
arr=tmp;
rail=rail-head;
head=0;
}
arr[rail++]=val;
}

queue()
{
initialize(4);
}

queue(int capacity)
{
initialize(capacity);
}

explicit queue(const container& cont)
{
initialize(cont.size());
vector <int>::const_iterator iter=cont.begin();
while(iter!=cont.end())
{
push(*iter++);
}
}

~queue()
{
delete arr;
}

//隊列中元素個數
int size()
{
return rail-head;
}

protected:
typedef struct node1
{
node1 *next;
T val;
node1(T v):val(v),next(NULL){}
}node;

private :
int capacity;
int head;//對頭元素的位置
int rail;//對尾元素的位置
int *arr;

void initialize(int cap)
{
capacity=cap;
arr=new int[capacity];
head=rail=0;
}
};

作者：陳太漢