顺序栈,是一种基于数组的存储表示。
链式栈与顺序栈相比有很多优点。当栈需要动态变化时,如果使用顺序栈,如果设置过大会造成很多的资源浪费;如果过小,当栈溢出时,需要开辟一块更大的空间同时将原来栈中的元素全部拷贝过去,造成较大的时间开销。相反,用链接表示可以动态扩充栈的大小;而且可以节约内存空间。
实现类代码如下:
1 template<class T> 2 class SeqStack{ 3 T *element; 4 int top; 5 int maxSize; 6 void overflow(){//栈溢出时扩大栈容量 7 T *newArray=new T[maxSize+20]; 8 for(int i=0;i<=top;i++){ 9 newArray[i]=element[i]; 10 } 11 maxSize+=20; 12 delete []element; 13 element=newArray; 14 } 15 public: 16 SeqStack(int sz=50){ 17 top=-1; 18 maxSize=sz; 19 element=new T[maxSize]; 20 } 21 ~SeqStack(){ 22 delete[] element; 23 } 24 void push(const T& x){//进栈 25 if(isFull()) 26 overflow(); 27 element[++top]=x; 28 } 29 bool pop(T& x){//出栈 30 if(isEmpty()) 31 return false; 32 x=element[top--]; 33 return true; 34 } 35 bool getTop(T& x){//获取栈顶元素 36 if(isEmpty()) 37 return false; 38 x=element[top]; 39 return true; 40 } 41 bool isEmpty()const{ 42 return (top==-1)?true:false; 43 } 44 bool isFull()const{ 45 return (top==maxSize-1)?true:false; 46 } 47 int getSize(){ 48 return top+1; 49 } 50 void makeEmpty(){//置栈空 51 top=-1; 52 } 53 };
测试代码如下:
1 void menu(){ 2 cout<<"1.进栈"<<endl; 3 cout<<"2.出栈"<<endl; 4 cout<<"3.获取栈顶元素"<<endl; 5 cout<<"4.栈置空"<<endl; 6 cout<<"5.退出"<<endl; 7 } 8 template<class T> 9 void function(int num,SeqStack<T> *ss){ 10 switch(num){ 11 int x; 12 case 1: 13 cin>>x; 14 ss->push(x); 15 break; 16 case 2: 17 ss->pop(x); 18 break; 19 case 3: 20 ss->getTop(x); 21 cout<<x<<endl; 22 break; 23 case 4: 24 ss->makeEmpty(); 25 break; 26 default: 27 exit(1); 28 } 29 } 30 31 int main(int argc, char** argv) { 32 SeqStack<int> *ss=new SeqStack<int>; 33 int num; 34 while(true){ 35 menu(); 36 cin>>num; 37 function(num,ss); 38 } 39 delete ss; 40 return 0; 41 }
链式栈,是一种基于链表的存储表示。
实现类代码如下:
1 template<class T> 2 struct LinkNode{//链表节点 3 T data; 4 LinkNode *link; 5 LinkNode(const T& args,LinkNode<T> *ptr=NULL){ 6 data=args; 7 link=ptr; 8 } 9 }; 10 template<class T> 11 class LinkedStack{ 12 LinkNode<T> *top; 13 public: 14 LinkedStack(){ 15 top=NULL; 16 17 } 18 ~LinkedStack(){ 19 makeEmpty(); 20 } 21 void push(const T& x){//进栈 22 top=new LinkNode<T>(x,top); 23 } 24 bool pop(T& x){//出栈 25 if(isEmpty()) 26 return false; 27 LinkNode<T> *p=top; 28 top=top->link; 29 x=p->data; 30 delete p; 31 } 32 bool getTop(T& x)const{//返回栈顶元素 33 if(isEmpty()) 34 return false; 35 x=top->data; 36 return true; 37 } 38 bool isEmpty()const{ 39 return (top==NULL)?true:false; 40 } 41 int getSize()const{ 42 LinkNode<T> *p=top; 43 int k=0; 44 while(p!=NULL){ 45 p=p->link; 46 k++; 47 } 48 return k; 49 } 50 void makeEmpty(){//栈置空 51 LinkNode<T> *p; 52 while(top!=NULL){ 53 p=top; 54 top=top->link; 55 delete p; 56 } 57 } 58 };
测试代码如下:
1 void menu(){ 2 cout<<"1.进栈"<<endl; 3 cout<<"2.出栈"<<endl; 4 cout<<"3.获取栈顶元素"<<endl; 5 cout<<"4.栈置空"<<endl; 6 cout<<"5.退出"<<endl; 7 } 8 template<class T> 9 void function(int num,LinkedStack<T> *ls){ 10 switch(num){ 11 int x; 12 case 1: 13 cin>>x; 14 ls->push(x); 15 break; 16 case 2: 17 ls->pop(x); 18 break; 19 case 3: 20 ls->getTop(x); 21 cout<<x<<endl; 22 break; 23 case 4: 24 ls->makeEmpty(); 25 break; 26 case 5: 27 exit(1); 28 break; 29 } 30 } 31 int main(int argc, char** argv) { 32 LinkedStack<int> *ls=new LinkedStack<int>; 33 int num; 34 while(true){ 35 menu(); 36 cin>>num; 37 function(num,ls); 38 } 39 delete ls; 40 return 0; 41 }