棧是一種限定只在表尾進行插入或刪除操作的線性表，棧也是線性表。表頭稱為棧的底部,表尾稱為棧的頂部,表為空稱為空棧。

棧又稱為后進先出的線性表,棧也有兩種表示:順序棧與鏈式棧。順序棧是利用一組地址連續的存儲單元。依次存放從棧底到棧頂的數據元素。

#include<iostream>
using namespace std;
# define STACK_INIT_SIZE 100
# define STACKINCREMENT 10typedef  struct 
{int  * base;int  * top;int   stacksize;//當前棧可使用的最大容量} SqStack;void InitStack(SqStack &S)//構造一個空棧
{S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));if(!S.base) {cout<<"存儲分配失敗!!!"<<endl<<endl;}else{S.top=S.base;S.stacksize=STACK_INIT_SIZE;cout<<"構造成功!!!"<<endl;}
}void Push(SqStack &S,int e)//插入元素e為棧頂元素
{if(S.top-S.base>=S.stacksize){S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));if(!S.base) cout<<"存儲分配失敗!!!"<<endl<<endl;else{S.stacksize+=STACKINCREMENT;S.top=S.base+S.stacksize;}}*S.top++=e;
}void DisplayStack(SqStack &S) //從棧底到棧頂逐次顯示棧中的元素
{int *p;p=S.base;if(S.base==S.top)	cout<<"當前棧為空棧!!!"<<endl<<endl;else{cout<<"當前棧內元素為: ";while(p!=S.top){cout<<*(p)<<" ";p++;}cout<<endl;}
}int StackLength(SqStack S) //求長度
{int *p;p=S.base;int i=0;while(p!=S.top) {p++;i++;}return i;
}void pop(SqStack &S,int &e) //出棧
{ if (S.top==S.base) cout<<"操作失敗!!!"<<endl<<endl;else {e=*--S.top;DisplayStack(S);}
}void ClearStack(SqStack &S)//清空
{int b;while(S.top!=S.base) b=*--S.top;if(S.top==S.base) cout<<"順序棧已清空!!!"<<endl<<endl;
}void StackEmpty(SqStack S)//判空
{if(S.top==S.base) cout<<"順序棧為空!!!"<<endl<<endl;else cout<<"順序棧不為空!!!"<<endl<<endl;
}void DestroyStack(SqStack &S)
{S.base=NULL;cout<<"順序棧已銷毀!!!"<<endl<<endl;
}void GetTop(SqStack S,int &e)//返回棧頂元素
{if(S.top==S.base) cout<<"操作失敗!!!"<<endl<<endl;else{cout<<"棧頂元素為: ";e=*(S.top-1);cout<<e<<endl<<endl;}
}int main()
{cout<<"*  1、構造一個空棧       *"<<endl;cout<<"*  2、輸入棧的元素       *"<<endl;cout<<"*  3、輸出棧的元素       *"<<endl;cout<<"*  4、求棧的長度         *"<<endl;cout<<"*  5、求棧頂元素         *"<<endl;cout<<"*  6、刪除棧頂元素       *"<<endl;cout<<"*  7、清空已存在的棧     *"<<endl;cout<<"*  8、判斷棧是否為空     *"<<endl;cout<<"*  0、銷毀棧             *"<<endl;int n,k;SqStack S;for(n=0;n<15;n++)
{cout<<"請選擇0-8:  ";cin>>k;if(k==0) {DestroyStack(S);n=15;}if(k==1) InitStack(S);if(k==2) {int a;cout<<"輸入棧S的元素為: ";cin>>a;Push(S,a);DisplayStack(S);}if(k==3) DisplayStack(S);if(k==4) cout<<"棧的長度為: "<<StackLength(S)<<endl<<endl;if(k==5) {int c;GetTop(S,c);}if(k==6) {int b;pop(S,b);}if(k==7) ClearStack(S);if(k==8) StackEmpty(S);}
return 0;
}