详解数据结构：栈

一、顺序栈

顺序栈的存储方式如下：

从图中可以看出，顺序栈需要两个指针，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，将栈顶元素赋给ereturn true;}

4、取栈顶元素

取栈顶元素和出栈不同。取栈顶元素只是把栈顶元素复制一份，栈顶指针未移动，栈内元素个数未变。而出栈时栈顶指针向下移动一个位置，栈内不在包含这个元素。

完美图解：

取栈顶元素*(S.top-1)即元素4，取值后S.top指针没有改变，栈内元素的个数也没有改变。

代码实现：

int GetTop(SqStack S) //返回S的栈顶元素，栈顶指针不变{if(S.top!=S.base)  //栈非空return *(S.top-1); //返回栈顶元素的值，栈顶指针不变elsereturn -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;    //修改栈顶指针为preturn 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;  //将栈顶元素赋给ep=S;  //用p保存栈顶元素地址，以备释放S=S->next;  //修改栈顶指针，指向下一个结点delete p;  //释放原栈顶元素的空间return true;}

4.取栈顶元素

取栈顶元素和出栈不同，取栈顶元素只是把栈顶元素赋值一份，栈顶指针并没有改变。而出栈是指删除栈顶元素，栈顶指针指向了下一个元素。

代码实现：

int GetTop(LinkStack S) //返回S的栈顶元素，不修改栈顶指针{if(S!=NULL) //栈非空return S->data; //返回栈顶元素的值，栈顶指针不变elsereturn -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，将栈顶元素赋给ereturn true;
}int GetTop(SqStack S) //返回S的栈顶元素，栈顶指针不变
{if(S.top!=S.base)  //栈非空return *(S.top-1); //返回栈顶元素的值，栈顶指针不变elsereturn -1;
}int main()
{int n,x;SqStack S;InitStack(S);//初始化一个顺序栈Scout<<"请输入元素个数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;    //修改栈顶指针为preturn true;
}bool Pop(LinkStack &S,int &e) //删除S的栈顶元素，用e保存其值
{LinkStack p;if(S==NULL) //栈空return false;e=S->data;  //将栈顶元素赋给ep=S;  //用p保存栈顶元素地址，以备释放S=S->next;  //修改栈顶指针，指向下一个结点delete p;  //释放原栈顶元素的空间return true;
}int GetTop(LinkStack S) //返回S的栈顶元素，不修改栈顶指针
{if(S!=NULL) //栈非空return S->data; //返回栈顶元素的值，栈顶指针不变elsereturn -1;
}int main()
{int n,x;LinkStack S;InitStack(S);//初始化一个顺序栈Scout<<"请输入元素个数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;
}