顺序栈，是一种基于数组的存储表示。
链式栈与顺序栈相比有很多优点。当栈需要动态变化时，如果使用顺序栈，如果设置过大会造成很多的资源浪费；如果过小，当栈溢出时，需要开辟一块更大的空间同时将原来栈中的元素全部拷贝过去，造成较大的时间开销。相反，用链接表示可以动态扩充栈的大小；而且可以节约内存空间。
实现类代码如下：
template<class T>
class SeqStack{
T *element;
int top;
int maxSize;
void overflow(){//栈溢出时扩大栈容量
T *newArray=new T[maxSize+];
for(int i=;i<=top;i++){
newArray[i]=element[i];
}
maxSize+=;
delete []element;
element=newArray;
}
public:
SeqStack(int sz=){
top=-;
maxSize=sz;
element=new T[maxSize];
}
~SeqStack(){
delete[] element;
}
void push(const T& x){//进栈
if(isFull())
overflow();
element[++top]=x;
}
bool pop(T& x){//出栈
if(isEmpty())
return false;
x=element[top--];
return true;
}
bool getTop(T& x){//获取栈顶元素
if(isEmpty())
return false;
x=element[top];
return true;
}
bool isEmpty()const{
return (top==-)?true:false;
}
bool isFull()const{
return (top==maxSize-)?true:false;
}
int getSize(){
return top+;
}
void makeEmpty(){//置栈空
top=-;
}
};
测试代码如下：
void menu(){
cout<<"1.进栈"<<endl;
cout<<"2.出栈"<<endl;
cout<<"3.获取栈顶元素"<<endl;
cout<<"4.栈置空"<<endl;
cout<<"5.退出"<<endl;
}
template<class T>
void function(int num,SeqStack<T> *ss){
switch(num){
int x;
case :
cin>>x;
ss->push(x);
break;
case :
ss->pop(x);
break;
case :
ss->getTop(x);
cout<<x<<endl;
break;
case :
ss->makeEmpty();
break;
default:
exit();
}
}
int main(int argc, char** argv) {
SeqStack<int> *ss=new SeqStack<int>;
int num;
while(true){
menu();
cin>>num;
function(num,ss);
}
delete ss;
return ;
}链式栈，是一种基于链表的存储表示。
实现类代码如下：
template<class T>
struct LinkNode{//链表节点
T data;
LinkNode *link;
LinkNode(const T& args,LinkNode<T> *ptr=NULL){
data=args;
link=ptr;
}
};
template<class T>
class LinkedStack{
LinkNode<T> *top;
public:
LinkedStack(){
top=NULL; }
~LinkedStack(){
makeEmpty();
}
void push(const T& x){//进栈
top=new LinkNode<T>(x,top);
}
bool pop(T& x){//出栈
if(isEmpty())
return false;
LinkNode<T> *p=top;
top=top->link;
x=p->data;
delete p;
}
bool getTop(T& x)const{//返回栈顶元素
if(isEmpty())
return false;
x=top->data;
return true;
}
bool isEmpty()const{
return (top==NULL)?true:false;
}
int getSize()const{
LinkNode<T> *p=top;
int k=;
while(p!=NULL){
p=p->link;
k++;
}
return k;
}
void makeEmpty(){//栈置空
LinkNode<T> *p;
while(top!=NULL){
p=top;
top=top->link;
delete p;
}
}
};
测试代码如下：
void menu(){
cout<<"1.进栈"<<endl;
cout<<"2.出栈"<<endl;
cout<<"3.获取栈顶元素"<<endl;
cout<<"4.栈置空"<<endl;
cout<<"5.退出"<<endl;
}
template<class T>
void function(int num,LinkedStack<T> *ls){
switch(num){
int x;
case :
cin>>x;
ls->push(x);
break;
case :
ls->pop(x);
break;
case :
ls->getTop(x);
cout<<x<<endl;
break;
case :
ls->makeEmpty();
break;
case :
exit();
break;
}
}
int main(int argc, char** argv) {
LinkedStack<int> *ls=new LinkedStack<int>;
int num;
while(true){
menu();
cin>>num;
function(num,ls);
}
delete ls;
return ;
}