链栈和顺序栈的实现

 

顺序栈和链栈是我复习的第二部分，同样是把之前的代码整理出来，发布给大家，实现的方法并不

难，毕竟是最基本的方法嘛。关于代码的解释已经写成注释。所以不用多说了。大家好好看代码吧~

下面的代码是栈的实习，完整代码实现下载地址；

//顺序栈

//

#ifndef ASTACK_H

#defineASTACK_H

#include"Stack.h"

template <classElem> classAStack : publicStack<Elem>{

private:

         int size;//栈最大长度

         int top;//栈长度

         Elem *listArray;

public:

         AStack(intsz = DefaultListSize){

                   size = sz;

                   top = 0;

                   listArray = newElem[sz];

         }

         ~AStack(){

                   delete [] listArray;

         }

         voidclear(){

                   top=0;

         }

         boolpush(constElem& item){//存入操作

                   if(top==size) returnfalse;

                   else{

                            listArray[top++] = item;

                            returntrue;

                   }

         }

         boolpop(Elem& it){//取出操作

                   if(top==0) returnfalse;

                   else{

                            it = listArray[--top];

                            returntrue;

                   }

         }

         booltopValue(Elem& it){//获取栈顶值

                   if(top==0) returnfalse;

                   else{

                            it = listArray[top-1];

                            returntrue;

                   }

         }

         intlength() const{//栈长度

                   return top;

         }

         //利用栈将栈逆置

         //具体分为以下几步：声明一个变量，用来临时存放栈顶元素，记为A；

         //声明一个顺序栈，栈长比原栈小1，记为ls；

         //首先将栈顶元素放入A，将剩下的元素放入ls，再将A放入原栈，接着将ls中所有元素放入原栈；

         //重复n此，n为栈长；

         voidreverlist(){

                   Elem it;

                   Elem A;

                   AStack<Elem> ls(top-1);

                   for (int i = 0; i < top; i++){

                            this->pop(A);

                            while (this->length())

                            {

                                     this->pop(it);

                                     ls.push(it);

                            }

                            this->push(A);

                            while (ls.length())

                            {

                                     ls.pop(it);

                                     this->push(it);

                            }

                   }

         }

};

#endif

 

//Stack类，定义栈中的方法

//只有五个方法：1、清空；2、进栈；3、出栈；4、获得栈顶元素值；5、输出栈高

#ifndef STACK_H

#defineSTACK_H

 

#include<iostream>

usingnamespace std;

template <classElem> classStack{

public:

         virtualvoidclear() = 0;

         virtualboolpush(constElem&) = 0;

         virtualboolpop(Elem&) = 0;

         virtualbooltopValue(Elem&) = 0;

         virtualintlength() const =0;

         virtualvoidreverlist() = 0;

};

#endif;

 

//链式栈的节点

#ifndef  SLINK_H

#define  SLINK_H

//链栈节点

#include<iostream>

usingnamespace std;

template<classElem> classSLink{

public:

         Elem element;

         SLink *next;

         SLink(constElem& elemval,SLink* nextval = NULL){

                   element=elemval;

                   next = nextval;

         }

         SLink(SLink* nextval =NULL){

                   next = nextval;

         }

};

#endif// ! SLINK_H

 

//链式栈

#ifndef LSTACK_H

#defineLSTACK_H

#include"Stack.h"

#include"SLink.h"

template <classElem> classLStack : publicStack<Elem>{

         SLink<Elem>* top;

         int size;//表长度

public:

         LStack(){

                   size = 0;

         }

         ~LStack(){

                   clear();

         }

         //清空表

         //清空表的操作流程：将top元素一个一个delete掉

         voidclear(){

                   if (size == 0){

                            cout << "This stack is empty"<<endl;

                   }

                   else{

                            int num = 0;

                            while (top != NULL&&size>1)

                            {

                                     SLink<Elem>* temp = top;

                                     top = top->next;

                                     size--;

                                     delete temp;

                            }

                            delete top;

                            size--;

                            cout << size << endl;

                   }

         }

         //入栈

         boolpush(constElem& item){

                   top =newSLink<Elem>(item,top);

                   size++;

                   returntrue;

         }

         //出栈

         boolpop(Elem& it){

                   if(size==0) returnfalse;

                   else{

                   it = top->element;

                   SLink<Elem>* ltemp = top->next;

                   delete top;

                   top =ltemp;

                   size--;

                   returntrue;

                   }

 

         }

         //获取栈顶值

         booltopValue(Elem& it){

                   if(size == 0)returnfalse;

                   it = top->element;

                   returntrue;

         }

         //获取栈长

         intlength() const{

                   return size;

         }

         //逆置栈，相关操作可参考顺序表实现

         voidreverlist(){

                   Elem it;

                   Elem A;

                   AStack<Elem> ls(size - 1);

                   for (int i = 0; i < size; i++){

                            this->pop(A);

                            while (this->length())

                            {

                                     this->pop(it);

                                     ls.push(it);

                            }

                            this->push(A);

                            while (ls.length())

                            {

                                     ls.pop(it);

                                     this->push(it);

                            }

                   }

         }

 

};

 

#endif