顺序栈和链式栈(C++实现)

顺序栈，是一种基于数组的存储表示。

链式栈与顺序栈相比有很多优点。当栈需要动态变化时，如果使用顺序栈，如果设置过大会造成很多的资源浪费；如果过小，当栈溢出时，需要开辟一块更大的空间同时将原来栈中的元素全部拷贝过去，造成较大的时间开销。相反，用链接表示可以动态扩充栈的大小；而且可以节约内存空间。

实现类代码如下：

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 }

原文链接: https://www.cnblogs.com/ytz1996/p/6290449.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍