C++中实现队列类链式存储与栈类链式存储的代码示例
队列类链式存储
代码：
linkqueue.hpp
//队列类
#pragmaonce
#include"linklist.hpp"
template<typenameT>
classLinkQueue
{
public:
LinkQueue();
~LinkQueue();
public:
intclear();
intappend(T&t);
intretieve(T&t);
intheader(T&t);
intlength();
protected:
LinkList<T>*m_list;
};
template<typenameT>
LinkQueue<T>::LinkQueue()
{
m_list=newLinkList<T>;
}
template<typenameT>
LinkQueue<T>::~LinkQueue()
{
clear();
deletem_list;
m_list=NULL;
}
template<typenameT>
intLinkQueue<T>::clear()
{
Tt;
while(m_list->getLen()>0){
m_list->del(0,t);
}
return0;
}
template<typenameT>
intLinkQueue<T>::append(T&t)
{
returnm_list->insert(t,m_list->getLen());
}
template<typenameT>
intLinkQueue<T>::retieve(T&t)
{
returnm_list->del(m_list->getLen()-1,t);
}
template<typenameT>
intLinkQueue<T>::header(T&t)
{
returnm_list->get(0,t);
}
template<typenameT>
intLinkQueue<T>::length()
{
returnm_list->getLen();
}
main.cpp
//队列类测试程序
#include<iostream>
#include<cstdio>
#include"linkqueue.hpp"
usingnamespacestd;
structStudent
{
charname[32];
intage;
};
voidplay()
{
Students1,s2,s3;
s1.age=21;
s2.age=22;
s3.age=23;
LinkQueue<Student>lq;//创建队列
lq.append(s1);//入队列
lq.append(s2);
lq.append(s3);
Studenttmp;
lq.header(tmp);
cout<<"headerofqueue:"<<tmp.age<<endl;
cout<<"lengthofqueue:"<<lq.length()<<endl;
while(lq.length()>0){
lq.retieve(tmp);
cout<<tmp.age<<"";
}
cout<<endl;
lq.clear();
}
intmain()
{
play();
return0;
}
栈类链式存储
linkstack.hpp
//栈类
#pragmaonce
#include"linklist.hpp"
template<typenameT>
classLinkStack
{
public:
LinkStack();
~LinkStack();
public:
intclear();
intpush(T&t);
intpop(T&t);
inttop(T&t);
intsize();
protected:
LinkList<T>*m_list;
};
template<typenameT>
LinkStack<T>::LinkStack()
{
m_list=newLinkList<T>;
}
template<typenameT>
LinkStack<T>::~LinkStack()
{
clear();
deletem_list;
m_list=NULL;
}
template<typenameT>
intLinkStack<T>::clear()
{
Tt;
while(m_list->getLen()>0){
m_list->del(0,t);
}
return0;
}
template<typenameT>
intLinkStack<T>::push(T&t)
{
returnm_list->insert(t,0);
}
template<typenameT>
intLinkStack<T>::pop(T&t)
{
returnm_list->del(0,t);
}
template<typenameT>
intLinkStack<T>::top(T&t)
{
returnm_list->get(0,t);
}
template<typenameT>
intLinkStack<T>::size()
{
returnm_list->getLen();
}
main.cpp
//链式存储栈类的测试程序
#include<iostream>
#include<cstdio>
#include"linkstack.hpp"
usingnamespacestd;
structStudent
{
charname[32];
intage;
};
voidplay()
{
Students1,s2,s3;
s1.age=21;
s2.age=22;
s3.age=23;
LinkStack<Student>ls;//创建栈
//入栈
ls.push(s1);
ls.push(s2);
ls.push(s3);
//获取栈顶元素
Studenttmp;
ls.top(tmp);
cout<<"topofstack:"<<tmp.age<<endl;
cout<<"sizeofstack:"<<ls.size()<<endl;
//出栈
while(ls.size()>0){
ls.pop(tmp);
}
ls.clear();
}
intmain()
{
play();
return0;
}
linklist.h
//链表类
#pragmaonce
#include<iostream>
#include<cstdio>
usingnamespacestd;
template<typenameT>
structNode
{
Tt;
Node<T>*next;
};
template<typenameT>
classLinkList
{
public:
LinkList();
~LinkList();
public:
intclear();
intinsert(T&t,intpos);
intget(intpos,T&t);
intdel(intpos,T&t);
intgetLen();
protected:
Node<T>*header;
intlength;
};
template<typenameT>
LinkList<T>::LinkList()
{
header=newNode<T>;
header->next=NULL;
length=0;
}
template<typenameT>
LinkList<T>::~LinkList()
{
Node<T>*tmp=NULL;
while(header){
tmp=header->next;
deleteheader;
header=tmp;
}
}
template<typenameT>
intLinkList<T>::clear()
{
~LinkList();
LinkList();
return0;
}
template<typenameT>
intLinkList<T>::insert(T&t,intpos)
{
Node<T>*cur=NULL;
//对pos的容错处理
if(pos>=length){
pos=length;
}
cur=header;
for(inti=0;i<pos;++i){
cur=cur->next;
}
//把上层应用的t结点缓存到容器中
Node<T>*node=newNode<T>;
node->next=NULL;
node->t=t;//把t缓存到容器中
node->next=cur->next;
cur->next=node;
++length;
return0;
}
template<typenameT>
intLinkList<T>::get(intpos,T&t)
{
Node<T>*cur=NULL;
if(pos>=length){
return-1;
}
cur=header;
for(inti=0;i<pos;++i){
cur=cur->next;
}
t=cur->next->t;//把pos位置的结点赋值给t
return0;
}
template<typenameT>
intLinkList<T>::del(intpos,T&t)
{
Node<T>*cur=NULL;
if(pos>=length){
return-1;
}
cur=header;
for(inti=0;i<pos;++i){
cur=cur->next;
}
Node<T>*ret=NULL;
ret=cur->next;
t=ret->t;//把缓存的结点给上层应用t
//删除操作
cur->next=ret->next;
--length;
deleteret;//注意释放内存，因为insert的时候newNode<T>
return0;
}
template<typenameT>
intLinkList<T>::getLen()
{
returnlength;
}