template class Stack public:Stack(int=10);/构造函数构造函数 void Push(const Type&item);/进栈进栈 Type Pop();/出栈出栈 Type GetTop();/取栈顶元素取栈顶元素 void MakeEmpty();/置空栈置空栈 int IsEmpty()const;/判栈空否判栈空否 int IsFull()const;/判栈满否判栈满否#include template class Stack public:Stack(int=10);/构造函数构造函数 Stack()delete elements;/析构函数析构函数 void Push(const Type&item);/进栈进栈 Type Pop();/出栈出栈 Type GetTop();/取栈顶元素取栈顶元素 void MakeEmpty()top=-1;/置空栈置空栈 int IsEmpty()const return top=-1;int IsFull()const return top=maxSize-1;private:int top;/栈顶数组指针栈顶数组指针 Type*elements;/栈数组栈数组 int maxSize;/栈最大容量栈最大容量template Stack:Stack(int s):top(-1),maxSize(s)elements=new TypemaxSize;assert(elements!=0);/断言断言进栈示例进栈示例 退栈示例退栈示例template void Stack:Push(const Type&item)assert(!IsFull();/先决条件断言先决条件断言 elements+top=item;/加入新元素加入新元素template Type Stack:Pop()assert(!IsEmpty();/先决条件断言先决条件断言 return elementstop-;/退出栈顶元素退出栈顶元素template Type stack:GetTop()assert(!IsEmpty();/先决条件断言先决条件断言 return elementstop;/取出栈顶元素取出栈顶元素插入新元素时的栈满处理插入新元素时的栈满处理 StackFull()template void Push(const int i,const Type&item)if(t i=bi+1)StackFull(i);else V+ti=item;/第i 个栈进栈template Type*Pop(const i)if(ti=bi)StackEmpty(i);return 0;else return&Vti-;/第i 个栈出栈template class Stack;template class StackNode friend class Stack;private:Type data;/结点数据结点数据 StackNode*link;/结点链指针结点链指针 StackNode(Type d=0,StackNode *l=NULL):data(d),link(l);template class Stack public:Stack():top(NULL)Stack();void Push(const Type&item);Type Pop();Type GetTop();void MakeEmpty()top=NULL;int IsEmpty()const return top=NULL;private:StackNode*top;/栈顶指针栈顶指针template void Stack:Stack()StackNode*p;while(top!=NULL)/逐结点回收逐结点回收 p=top;top=toplink;delete p;template void Stack:Push(const Type&item)top=new StackNode(item,top);/新结点链入新结点链入top之前之前,并成为新栈顶并成为新栈顶template Type Stack:Pop()assert(!IsEmpty();StackNode*p=top;Type retvalue=pdata;/暂存栈顶数据暂存栈顶数据 top=toplink;/修改栈顶指针修改栈顶指针 delete p;return retvalue;/释放释放,返回数据返回数据template Type Stack:GetTop()assert(!IsEmpty();return topdata;template class Queue public:Queue(int=10);/构造函数构造函数 void EnQueue(const Type&item);/进队进队 Type DeQueue();/出队列出队列 Type GetFront();/取队头元素值取队头元素值 void MakeEmpty();/置空队列置空队列 int IsEmpty()const;/判队列空否判队列空否 int IsFull()const;/判队列满否判队列满否#include template class Queue public:Queue(int=10);Queue()delete elements;void EnQueue(const Type&item);Type DeQueue();Type GetFront();void MakeEmpty()front=rear=0;int IsEmpty()const return front=rear;int IsFull()const return(rear+1)%maxSize=front;int Length()const return(front-rear+maxSize)%maxSize;private:int rear,front;Type*elements;int maxSize;n n template Queue:Queue(int sz):front(0),rear(0),maxSize(sz)elements=new TypemaxSize;assert(elements!=0);template void Queue:EnQueue(const Type&item)assert(!IsFull();rear=(rear+1)%MaxSize;elementsrear=item;template Type Queue:DeQueue()assert(!IsEmpty();front=(front+1)%MaxSize;return elementsfront;template Type Queue:GetFront()assert(!IsEmpty();return elementsfront;template class Queue;template class QueueNode friend class Queue;private:Type data;/队列结点数据队列结点数据 QueueNode*link;/结点链指针结点链指针 QueueNode(Type d=0,QueueNode *l=NULL):data(d),link(l);template class Queue public:Queue():rear(NULL),front(NULL)Queue();void EnQueue(const Type&item);Type DeQueue();Type GetFront();void MakeEmpty()front=rear=NULL;int IsEmpty()const return front=NULL;private:QueueNode*front,*rear;/队列指针队列指针;template void Queue:Queue()/队列的析构函数队列的析构函数 QueueNode*p;while(front!=NULL)/逐个结点释放逐个结点释放 p=front;front=frontlink;delete p;template void Queue:EnQueue(const Type&item)/将新元素将新元素item插入到队列的队尾插入到队列的队尾 if(front=NULL)front=rear=new QueueNode(item,NULL);else rear=rearlink=new QueueNode(item,NULL);template TypeQueue:DeQueue()/删去队头结点，并返回队头元素的值删去队头结点，并返回队头元素的值 assert(!IsEmpty();/判队空的断言判队空的断言 QueueNode*p=front;Type retvalue=pdata;/保存队头的值保存队头的值 front=frontlink;delete p;/新队头新队头 return retvalue;template Type Queue:GetFront()/若队不空，则函数返回队头元素的值若队不空，则函数返回队头元素的值;若若/队空，则函数返回队空，则函数返回0。
assert(!IsEmpty();return frontdata;1 1 i=1 1 2 12 1 5 5 13 1 4 6 4 14 1 51010 5 15 1 6152015 6 16 利用队列打印二项展开式系数的程序利用队列打印二项展开式系数的程序#include#include#include queue.hvoid YANGVI(int n)Queue q;/队列初始化队列初始化 q.MakeEmpty();q.EnQueue(1);q.EnQueue(1);int s=0;for(int i=1;i=n;i+)/逐行计算逐行计算 cout endl;q.EnQueue(0);for(int j=1;j=i+2;j+)/下一行下一行 int t=q.DeQueue();q.EnQueue(s+t);s=t;if(j!=i+2)cout s ;任务编号任务编号 1 2 3 4 5 优先权优先权 20 0 40 30 10 执行顺序执行顺序 3 1 5 4 2#include#include$include const int maxPQSize=50;/缺省元素个数缺省元素个数template class PQueue public:PQueue();PQueue()delete pqelements;void PQInsert(const Type&item);Type PQRemove();void makeEmpty()count=-1;int IsEmpty()const return count=-1;int IsFull()const return count=maxPQSize;int Length()const return count;private:Type*pqelements;/存放数组存放数组 int count;/队列元素计数队列元素计数 优先队列部分成员函数的实现优先队列部分成员函数的实现template PQueue:PQueue():count(-1)pqelements=new TypemaxPQSize;assert(pqelements!=0);/分配断言分配断言template void PQueue:PQInsert(const Type&item)assert(!IsFull();/判队满断言判队满断言 count+；pqelementscount=item;template Type PQueue:PQRemove()assert(!IsEmpty();/判队空断言判队空断言 Type min=pqelements0;int minindex=0;for(int i=1;icount;i+)/寻找最小元素寻找最小元素 if(pqelementsi min)/存于存于min min=pqelementsi;minindex=i;pqelementsminindex=pqelementscount-1;count-;/删除删除 return min;。