一、顺序栈
顺序栈的存储方式如下：
从图中可以看出，顺序栈需要两个指针，base指向栈底，top指向栈顶。
typedef struct SqStack {
ElemType *base; //栈底指针
ElemType *top; //栈顶指针
}SqStack;说明：
ElemType是元素类型，需要什么类型就写什么类型。
typedef将结构体等价于类型名Sqstack。
栈定义好了之后，还要先定义一个最大的分配空间，这和数组一样，需要预先分配空间，因此可以采用宏定义：
#define Maxsize 100; //预先分配空间，这个数值根据实际需要预估确定
上面的结构体定义采用了动态分配的形式，也可以采用静态分配的形式，使用一个长数组存储数据元素，一个整型下标记录栈顶元素的位置。静态分配的顺序栈结构定义如下：
typedef struct SqStack {
ElemType data[Maxsize]; //定长数组
int top; //栈顶下标
}SqStack;注意：栈只能在一端操作，后进先出，是人为规定的，也就是说不允许在中间查找，取值，插入，删除等操作。顺序栈本身是顺序存储的，有人就想：我偏要从中间取一个元素，这也是可以的，但这样做，这就不是栈了。
1、顺序栈的初始化
初始化一个空栈，动态分配Maxsize大小的空间，用S.top和S.base指向该空间的基地址。
代码实现：
bool InitStack(SqStack &S) //构造一个空栈S
{
S.base=new int[Maxsize];//为顺序栈分配一个最大容量为Maxsize的空间
if(!S.base) //空间分配失败
return false;
S.top=S.base; //top初始为base，空栈
return true;
}2、入栈
入栈前要判断是否栈满，如果栈已满，则入栈失败；否则将元素放入栈顶，栈顶指针向上移动一个位置（top++）。
图解：
输入1，入栈（左图）
接着输入2，入栈（右图）
代码实现：
bool Push(SqStack &S,int e) // 插入元素e为新的栈顶元素
{
if(S.top-S.base==Maxsize) //栈满
return false;
*(S.top++)=e; //元素e压入栈顶，然后栈顶指针加1，等价于*S.top=e; S.top++;
return true;
}3、出栈
出栈前要先判断是否为空栈，如果栈是空的，则出栈失败；否则将栈顶元素暂存给一个变量，栈顶指针向下移动一个位置（top--）。
完美图解：
栈顶元素所在的位置是S.top-1，因此把该元素取出来，暂存在变量e中，然后S.top指针向下移动一个位置。因此可以先移动一个位置，即--S.top，然后再取出元素。
例：栈顶元素4出栈前后的状态
注意：因为顺序栈删除一个元素时，并没有销毁该空间，所以4其实还在那个位置，只不过下一次再有元素进栈时，就把他覆盖了。相当于该元素已出栈，因为栈的内容时S.base到S.top-1。
代码实现：
bool Pop(SqStack &S,int &e) //删除S的栈顶元素，暂存在变量e中
{
if(S.base==S.top) //栈空
return false;
e=*(--S.top); //栈顶指针减1，将栈顶元素赋给e
return true;
}4、取栈顶元素
取栈顶元素和出栈不同。取栈顶元素只是把栈顶元素复制一份，栈顶指针未移动，栈内元素个数未变。而出栈时栈顶指针向下移动一个位置，栈内不在包含这个元素。
完美图解：
取栈顶元素*(S.top-1)即元素4，取值后S.top指针没有改变，栈内元素的个数也没有改变。
代码实现：
int GetTop(SqStack S) //返回S的栈顶元素，栈顶指针不变
{
if(S.top!=S.base) //栈非空
return *(S.top-1); //返回栈顶元素的值，栈顶指针不变
else
return -1;
}二、链栈
栈可以顺序存储，也可以用链式存储。
顺序栈是分配一段连续的空间，需要两个指针：base指向栈底，top指向栈顶，而链栈每个节点的地址都不连续，只需要一个栈顶指针即可。
链栈的每个节点都包含两个域：数据域和指针域。可以把链栈看作一个不带头结点的单链表，但只能在头部进行插入、删除、取值等操作，不可以在中间和尾部操作。
链栈的结构体定义如下：
typedef struct Snode{
ElemType data; //数据域
struct Snode *next; //指针域，指向下一个节点的指针
}Snode,*LinkStack;链栈的节点定义和单链表一样，只不过它只能在栈顶那一端操作而已。
1、链栈的初始化
初始化一个空的链栈是不需要头结点的，因此只需要让栈顶指针为空即可。
代码实现：
typedef struct Snode{
ElemType data; //数据域
struct Snode *next; //指针域，指向下一个节点的指针
}Snode,*LinkStack;2.入栈
入栈是将新元素节点压入栈顶。因为链栈中第一个节点为栈顶，因此将新元素节点插入到第一个节点的前面，然后修改栈顶指针指向新结点即可。有点像堆柴，将新的节点堆在栈顶之上，新的节点成为新的栈顶。
完美图解：
（1）生成新结点。入栈前要创建一个新结点，将元素e存入该结点的数据域。
代码实现：
p=new Snode; //生成新结点，用p指针指向该结点
p->data=e; //将e放在新结点数据域（2）将新元素节点插入到第一个节点的前面，然后修改栈顶指针指向新结点。
赋值解释：
- p->next=S; //将新结点的指针域指向S，即将S的地址赋值给新结点的指针域。
- S=p; //修改栈顶指针为p
整体代码实现：
bool Push(LinkStack &S,int e) //在栈顶插入元素e
{
LinkStack p;
p=new Snode; //生成新结点
p->data=e; //将e放在新结点数据域
p->next=S; //将新结点的指针域指向S，即将S的地址赋值给新结点的指针域
S=p; //修改栈顶指针为p
return true;
}3.出栈
出栈就是把栈顶元素删除，绕过指针指向下一个节点，然后释放该结点空间。
赋值解释：
- p=S; //用p保存栈顶元素地址，以备释放
- S=S->next; //修改栈顶指针，指向下一个结点
- delete p; //释放原栈顶元素的空间
代码实现：
bool Pop(LinkStack &S,int &e) //删除S的栈顶元素，用e保存其值
{
LinkStack p;
if(S==NULL) //栈空
return false;
e=S->data; //将栈顶元素赋给e
p=S; //用p保存栈顶元素地址，以备释放
S=S->next; //修改栈顶指针，指向下一个结点
delete p; //释放原栈顶元素的空间
return true;
}4.取栈顶元素
取栈顶元素和出栈不同，取栈顶元素只是把栈顶元素赋值一份，栈顶指针并没有改变。而出栈是指删除栈顶元素，栈顶指针指向了下一个元素。
代码实现：
int GetTop(LinkStack S) //返回S的栈顶元素，不修改栈顶指针
{
if(S!=NULL) //栈非空
return S->data; //返回栈顶元素的值，栈顶指针不变
else
return -1;
}顺序栈和链栈的所以基本操作都只需要常数事件，所以在事件效率上难分伯仲。在空间效率方面，顺序栈需要预先分配固定长度的空间，有可能造成空间浪费或溢出；链栈每次只分配一个节点，除非没有内存，否则不会出现溢出，但是每个节点需要一个指针域，结构性开销增加。因此，如果元素个数变化较大，可以采用栈链；反之，可以采用顺序栈。在实际中，顺序栈比链栈应用更广泛。
配套完整代码（顺序栈）：
#include<iostream>
using namespace std;
#define Maxsize 100 //预先分配空间，这个数值根据实际需要预估确定；
typedef struct SqStack {
int *base; //栈底指针
int *top; //栈顶指针
}SqStack;
bool InitStack(SqStack &S) //构造一个空栈S
{
S.base=new int[Maxsize];//为顺序栈分配一个最大容量为Maxsize的空间
if(!S.base) //空间分配失败
return false;
S.top=S.base; //top初始为base，空栈
return true;
}
bool Push(SqStack &S,int e) // 插入元素e为新的栈顶元素
{
if(S.top-S.base==Maxsize) //栈满
return false;
*(S.top++)=e; //元素e压入栈顶，然后栈顶指针加1，等价于*S.top=e; S.top++;
return true;
}
bool Pop(SqStack &S,int &e) //删除S的栈顶元素，暂存在变量e中
{
if(S.base==S.top) //栈空
return false;
e=*(--S.top); //栈顶指针减1，将栈顶元素赋给e
return true;
}
int GetTop(SqStack S) //返回S的栈顶元素，栈顶指针不变
{
if(S.top!=S.base) //栈非空
return *(S.top-1); //返回栈顶元素的值，栈顶指针不变
else
return -1;
}
int main()
{
int n,x;
SqStack S;
InitStack(S);//初始化一个顺序栈S
cout<<"请输入元素个数n："<<endl;
cin>>n;
cout<<"请依次输入n个元素，依次入栈："<<endl;
while(n--)
{
cin>>x; //输入元素
Push(S,x);
}
cout<<"元素依次出栈："<<endl;
while(S.top!=S.base)//如果栈不空，则依次出栈
{
cout<<GetTop(S)<<"\t";//输出栈顶元素
Pop(S,x); //栈顶元素出栈
}
return 0;
}配套完整源代码（链栈）：
#include<iostream>
using namespace std;
typedef struct Snode{
int data; //数据域
struct Snode *next; //指针域
}Snode,*LinkStack;
bool InitStack(LinkStack &S)//构造一个空栈S
{
S=NULL;
return true;
}
bool Push(LinkStack &S,int e) //在栈顶插入元素e
{
LinkStack p;
p=new Snode; //生成新结点
p->data=e; //将e放在新结点数据域
p->next=S; //将新结点的指针域指向S，即将S的地址赋值给新结点的指针域
S=p; //修改栈顶指针为p
return true;
}
bool Pop(LinkStack &S,int &e) //删除S的栈顶元素，用e保存其值
{
LinkStack p;
if(S==NULL) //栈空
return false;
e=S->data; //将栈顶元素赋给e
p=S; //用p保存栈顶元素地址，以备释放
S=S->next; //修改栈顶指针，指向下一个结点
delete p; //释放原栈顶元素的空间
return true;
}
int GetTop(LinkStack S) //返回S的栈顶元素，不修改栈顶指针
{
if(S!=NULL) //栈非空
return S->data; //返回栈顶元素的值，栈顶指针不变
else
return -1;
}
int main()
{
int n,x;
LinkStack S;
InitStack(S);//初始化一个顺序栈S
cout<<"请输入元素个数n："<<endl;
cin>>n;
cout<<"请依次输入n个元素，依次入栈："<<endl;
while(n--)
{
cin>>x; //输入元素
Push(S,x);
}
cout<<"元素依次出栈："<<endl;
while(S!=NULL)//如果栈不空，则依次出栈
{
cout<<GetTop(S)<<"\t";//输出栈顶元素
Pop(S,x); //栈顶元素出栈
}
return 0;
}
