c++队列与堆栈图解.docx

应用抽象类，建立两种类型的表：队列与堆栈。先建立一个抽象类，为后面队列与堆栈的建立做准备class list /声明一个抽象类public:list *head; /表头指针list *tail; /表尾指针list *next;int num;list()head=tail=next=NULL;virtual void store(int i)=0; /纯虚函数storevirtual int retrieve()=0; /纯虚函数retrieve;一 .队列的建立与分析：class queue: public list /声明公有派生类queuepublic:void store(int i); /函数声明int retrieve(); /函数声明;void queue:store(int i); /定义虚函数storelist *item;item=new queue;if(!item)coutnum=i;if(tail)tail-next=item;tail=item;item-next=NULL;if(!head)head=tail;int queue:retrieve() /定义虚函数retrieveint i;list *p;if(!head)coutnum;p=head;head=head-next;delete p;return i;int main()list *p;queue q_ob;p=&q_ob;p-store(1);p-store(2);p-store(3);coutqueue: ;coutretrieve();coutretrieve();coutretrieve();coutstore(1);p-store(2);p-store(3);图解如下：p-store(1):item-num=1;tail=item;item-next=NULL; itemnullnullnullnullheadtailnextnumnull1headtailnextnump-store(2):item-num=2;if(tail)tail-next=item;tail=item;item-next=NULL; itemnullnullnullnullheadtailnextnumnull1headtailnextnumnull2headtailnextnump-store(3)：item-num=3;if(tail)tail-next=item;tail=item;item-next=NULL; item nullnullnullnullheadtailnextnumnull1headtailnextnumnull2headtailnextnumnull3headtailnextnum第二步：数据输出:int i;list *p;i=head-num;p=head;head=head-next;delete p;return i;1. coutretrieve();运行之后： item nullnullnullnullheadtailnextnumnull2headtailnextnumnull3headtailnextnum返回1。2. coutretrieve();运行之后： item nullnullnullnullheadtailnextnumnull3headtailnextnum返回2。3. coutretrieve();运行之后： nullnullnullnullheadtailnextnum回3。2 堆栈的建立与分析：class stack:public list /声明公有派生类stackpublic: void store(int i);int retrieve();void stack:store(int i) list *item;item=new stack;if(!item)coutnum=i;if(head)item-next=head;head=item;if(!tail)tail=head;int stack:retrieve() /定义虚函数retrieveint i;list *p;if(!head)coutnum;p=head;head=head-next;delete p;return i;int main()list *p;stack s_ob;p=&s_ob;p-store(1);p-store(2);p-store(3);coutStack: ;coutretrieve();coutretrieve();coutretrieve();coutstore(1);p-store(2);p-store(3);图解如下：p-store(1):item-num=1;head=item;If(!tail)tail=head; itemnullnullnullnullheadtailnextnum1headtailnextnump-store(2):item-num=2;if(headl)headl-next=head;head=item; itemnullnullnullnullheadtailnextnum1headtailnextnum2headtailnextnump-store(3)：item-num=2;if(headl)headl-next=head;head=item; itemnullnullnullnullheadtailnextnum1headtailnextnum2headtailnextnum3headtailnextnum第二步：数据输出：int i;list *p;i=head-num;p=head;head=head-next;delete p;return i;1.coutretrieve(); nullnullnullnullheadtailnextnum1headtailnextnum2headtailnextnum运行后返