栈：
#include<iostream>
using namespace std;
template<class T>
struct Node{
T date;
Node<T> * next;
Node():date(T()),next(NULL){}
};
template<class T>
class Stack
{
public:
Stack()
{
top=bottom=new Node<T>;
top->next=NULL;
}
bool push(const T & e);
const T& pop();
const T& gtop();
bool empty();
int size();
bool clear();
private:
Node<T> * top;
Node<T> * bottom;
};
template<class T>
bool Stack<T>::push(const T & e)
{
Node<T> * p=new Node<T>;
p->date=e;
p->next=NULL;
top->next=p;
top=p;
return true;
}
template<class T>
const T & Stack<T>::pop()
{
if(empty())
{
cout<<"栈为空，pop失败！"<<endl;
return (T)NULL;
}
Node<T> * p=bottom;
Node<T> * q=NULL;
while(p->next)
{
q=p;
p=p->next;
}
q->next=NULL;
top=q;
T e=p->date;
delete p;
return e;
}
template<class T>
const T& Stack<T>::gtop()
{
if(empty())
{
cout<<"栈为空，gtop失败！"<<endl;
return (T)NULL:
}
return top->date;
}
template<class T>
bool Stack<T>::empty()
{
if(top==bottom)
{
return true;
}
else
return false;
}
template<class T>
int Stack<T>::size()
{
Node<T> * p=bottom;
int i=0;
while(p)
{
p=p->next;
i++;
}
}
template<class T>
bool Stack<T>::clear()
{
Node<T> * p=bottom;
while(p)
{
p=p->next;
delete bottom;
bottom=p;
}
return true;
}
int main()
{
Stack<int> s;
s.push(3);
s.push(4);
s.push(5);
cout<<"栈顶元素："<<s.gtop()<<endl;
s.pop();
cout<<"栈顶元素："<<s.gtop()<<endl;
s.clear();
return 0;
}
队列：
#include<iostream>
using namespace std;
template<class T>
struct Node{
T date;
Node<T> * next;
Node():date(T()),next(NULL){}
};
template<class T>
class Queue
{
public:
Queue()
{
front=rear=new Node<T>;
rear->next=NULL;
}
bool add(const T & e);
const T & del();
bool empty();
int size();
bool clear();
private:
Node<T> * front;
Node<T> * rear;
};
template<class T>
bool Queue<T>::add(const T & e)
{
Node<T> * p=new Node<T>;
p->date=e;
rear->next=p;
p->next=NULL;
rear=p;
return true;
}
template<class T>
const T & Queue<T>::del()
{
if(this->empty())
{
cout<<"队列为空，del失败！"<<endl;
return (T)NULL;
}
Node<T> * p=front->next;
T e=p->date;
front->next=p->next;
delete p;
return e;
}
template<class T>
bool Queue<T>::empty()
{
if(front==rear)
{
return true;
}
else
{
return false;
}
}
template<class T>
int Queue<T>::size()
{
int i=0;
Node<T> * p=front->next;
while(p)
{
p=p->next;
i++;
}
return i;
}
template<class T>
bool Queue<T>::clear()
{
Node<T> * p=front;
Node<T> * q=NULL;
while(p)
{
q=p;
p=p->next;
delete q;
}
return true;
}
int main()
{
Queue<int> q;
q.add(10);
q.add(9);
q.add(8);
cout<<"出队："<<q.del()<<endl;
cout<<"队列的长度："<<q.size()<<endl;
if(q.empty())
{
cout<<"队列为空！"<<endl;
}
else
{
cout<<"队列不为空！"<<endl;
}
q.clear();
return 0;
}
循环队列：
循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。
解决这个问题的方法至少有两种：
① 另设一布尔变量以区别队列的空和满；
②另一种方式就是数据结构常用的： 队满时：(rear+1)%n==front，n为队列长度（所用数组大小），由于rear，front均为所用空间的指针，循环只是逻辑上的循环，所以需要求余运算。如图情况，队已满，但是rear（5）+1=6！=front（0），对空间长度求余，作用就在此6%6=0=front（0）。
#include<iostream>
using namespace std;
#define QueueSize 10
template<class T>
class CirQueue
{
public:
CirQueue():front(0),rear(0),count(0)
{
}
boolempty();
boolfull();
booladd(const T& e);
booldel(T &e);
int size();
private:
int front;
int rear;
intcount;
T date[QueueSize];
};
template<class T>
bool CirQueue<T>::empty()
{
if(rear%QueueSize==front)
{
returntrue;
}
else
returnfalse;
}
template<class T>
bool CirQueue<T>::full()
{
if((rear+1)%QueueSize==front)
{
returntrue;
}
else
returnfalse;
}
template<class T>
bool CirQueue<T>::add(const T& e)
{
if(full())
{
cout<<"队列已满，add失败！"<<endl;
returnfalse;
}
date[rear]=e;
rear++;
count++;
returntrue;
}
template<class T>
bool CirQueue<T>::del(T & e)
{
if(empty())
{
cout<<"队列为空！,del失败！"<<endl;
returnfalse;
}
e=date[front];
front++;
count--;
returntrue;
}
template<class T>
int CirQueue<T>::size()
{
returncount;
}
int main()
{
CirQueue<int>q;
if(q.empty())
{
cout<<"队列为空！"<<endl;
}
q.add(10);
q.add(9);
q.add(8);
cout<<"队列长度："<<q.size()<<endl;
if(q.full())
{
cout<<"队列已满！"<<endl;
}
else
{
cout<<"队列未满！"<<endl;
}
for(inti=0;i<6;i++)
{
q.add(i);
}
if(q.full())
{
cout<<"队列已满！"<<endl;
}
else
{
cout<<"队列未满！"<<endl;
}
inte=0;
q.del(e);
cout<<"出队:"<<e<<endl;
return0;
}