52清华殷人昆数据结构笔记ds04

栈(Stack)队列(Queue)优先队列(PriorityQueue)小结栈(Stack)只允许在一端插入和删除的顺序表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)templateclassTypeclassStack{public:Stack(int=10);//构造函数voidPush(constType&item);//进栈TypePop();//出栈TypeGetTop();//取栈顶元素voidMakeEmpty();//置空栈intIsEmpty()const;//判栈空否intIsFull()const;//判栈满否}栈的抽象数据类型#includeassert.htemplateclassTypeclassStack{public:Stack(int=10);//构造函数~Stack(){delete[]elements;}//析构函数voidPush(constType&item);//进栈TypePop();//出栈TypeGetTop();//取栈顶voidMakeEmpty(){top=-1;}//置空栈intIsEmpty()const{returntop==-1;}栈的数组表示—顺序栈intIsFull()const{returntop==maxSize-1;}private:inttop;//栈顶数组指针Type*elements;//栈数组intmaxSize;//栈最大容量}templateclassTypeStackType::Stack(ints):top(-1),maxSize(s){elements=newType[maxSize];assert(elements!=0);//断言}进栈示例退栈示例templateclassTypevoidStackType::Push(constType&item){assert(!IsFull());//先决条件断言elements[++top]=item;//加入新元素}templateclassTypeTypeStackType::Pop(){assert(!IsEmpty());//先决条件断言returnelements[top--];//退出栈顶元素}templateclassTypeTypestackType::GetTop(){assert(!IsEmpty());//先决条件断言returnelements[top];//取出栈顶元素}双栈共享一个栈空间多栈处理栈浮动技术n个栈共享一个数组空间V[m]设立栈顶指针数组t[n+1]和栈底指针数组b[n+1]t[i]和b[i]分别指示第i个栈的栈顶与栈底b[n]作为控制量，指到数组最高下标各栈初始分配空间s=m/n指针初始值t[0]=b[0]=-1b[n]=m-1t[i]=b[i]=b[i-1]+s,i=1,2,…,n-1插入新元素时的栈满处理StackFull()templateclassTypevoidPush(constinti,constType&item){if(t[i]==b[i+1])StackFull(i);elseV[++t[i]]=item;//第i个栈进栈}templateclassTypeType*Pop(consti){if(t[i]==b[i]){StackEmpty(i);return0;}elsereturn&V[t[i]--];//第i个栈出栈}栈的链接表示—链式栈链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作templateclassTypeclassStack;templateclassTypeclassStackNode{friendclassStackType;private:Typedata;//结点数据StackNodeType*link;//结点链指针StackNode(Typed=0,StackNodeType*l=NULL):data(d),link(l){}};链式栈(LinkedStack)类的定义templateclassTypeclassStack{public:Stack():top(NULL){}~Stack();voidPush(constType&item);TypePop();TypeGetTop();voidMakeEmpty();//实现与~Stack()同intIsEmpty()const{returntop==NULL;}private:StackNodeType*top;//栈顶指针}templateclassTypeStackType::~Stack(){StackNodeType*p;while(top!=NULL)//逐结点回收{p=top;top=top→link;deletep;}}templateclassTypevoidStackType::Push(constType&item){top=newStackNodeType(item,top);//新结点链入top之前,并成为新栈顶}templateclassTypeTypeStackType::Pop(){assert(!IsEmpty());StackNodeType*p=top;Typeretvalue=p→data;//暂存栈顶数据top=top→link;//修改栈顶指针deletep;returnretvalue;//释放,返回数据}templateclassTypeTypeStackType::GetTop(){assert(!IsEmpty());returntop→data;}队列(Queue)定义队列是只允许在一端删除，在另一端插入的顺序表允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。特性先进先出(FIFO,FirstInFirstOut)templateclassTypeclassQueue{public:Queue(int=10);//构造函数voidEnQueue(constType&item);//进队TypeDeQueue();//出队列TypeGetFront();//取队头元素值voidMakeEmpty();//置空队列intIsEmpty()const;//判队列空否intIsFull()const;//判队列满否}队列的抽象数据类型#includeassert.htemplateclassTypeclassQueue{public:Queue(int=10);~Queue(){delete[]elements;}voidEnQueue(constType&item);TypeDeQueue();TypeGetFront();voidMakeEmpty(){front=rear=0;}队列的数组表示循环队列的类定义intIsEmpty()const{returnfront==rear;}intIsFull()const{return(rear+1)%maxSize==front;}intLength()const{return(rear-front+maxSize)%maxSize;}private:intrear,front;Type*elements;intmaxSize;}队列的进队和出队进队时队尾指针先进一rear=rear+1，再将新元素按rear指示位置加入。出队时队头指针先进一front=front+1，再将下标为front的元素取出。队满时再进队将溢出出错；队空时再出队将队空处理。存储队列的数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;队列初始化：front=rear=0;队空条件：front==rear;队满条件：(rear+1)%maxSize==front循环队列(CircularQueue)循环队列的进队和出队循环队列部分成员函数的实现templateclassTypeQueueType::Queue(intsz):front(0),rear(0),maxSize(sz){elements=newType[maxSize];assert(elements!=0);}templateclassTypevoidQueueType::EnQueue(constType&item){assert(!IsFull());rear=(rear+1)%MaxSize;elements[rear]=item;}templateclassTypeTypeQueueType::DeQueue(){assert(!IsEmpty());front=(front+1)%MaxSize;returnelements[front];}templateclassTypeTypeQueueType::GetFront(){assert(!IsEmpty());returnelements[front];}队列的链接表示—链式队列队头在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为front==NULL链式队列类的定义templateclassTypeclassQueue;templateclassTypeclassQueueNode{friendclassQueueType;private:Typedata;//队列结点数据QueueNodeType*link;//结点链指针QueueNode(Typed=0,QueueNode*l=NULL):data(d),link(l){}};templateclassTypeclassQueue{public:Queue():rear(NULL),front(NULL){}~Queue();voidEnQueue(constType&item);TypeDeQueue();TypeGetFront();voidMakeEmpty();//实现与~Queue()同intIsEmpty()const{returnfront==NULL;}private:QueueNodeType*front,*rear;//队列指针};链式队列成员函数的实现templateclassTypeQueueType::~Queue(){//队列的析构函数QueueNodeType*p;while(front!=NULL){//逐个结点释放p=front;front=front→link;deletep;}}templateclassTypevoidQueueType::EnQueue(constType&item){//将新元素item插入到队列的队尾if(front==NULL)//空,创建第一个结点front=rear=newQueueNodeType(item,NULL);else//队列不空,插入rear=rear→link=newQueueNodeType(item,NULL);}templateclassTypeTypeQueueType::DeQueue(){//删去队头结点，并返回队头元素的值assert(!IsEmpty());//判队空的断言QueueNodeType*p=front;Typeretvalue=p→data;//保存队头的值front=front→link;//新队头deletep;returnretvalue;}templat