数据结构 栈的顺序存储结构
栈是一种特殊的线性表，所以在前面讨论的线性表的各种存储结构都可以作为栈的存储结构，因此，栈也有两种存储表示方法：顺序存储和链式存储。
栈的顺序结构简称顺序栈，是利用一组地址连续的存储单元一次存放紫栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。用一维数组表示栈的顺序存储结构，一般以top=0表示空栈，由于C语言中数组的小标约定从0开始，因此用C做描述语言时，这样设定会带来很大不便，因此用top=-1表示栈空，顺序存储结构可表示为：
typedey struct
{
int stacksize;
datatype *bottom;
datatype *top;
}SqlStack; //顺序栈类型定义
Sqlstack *S//S是顺序栈类型指针
其中stacksize 是指栈的当前可使用的最大容量，top为栈顶指针，其初值指向栈顶，即top=-1可作为栈空的标记，每当插入新的站定元素时，指针top增加1，删除栈顶元素时，top减1.
约定top指向真正的栈顶位置上面的一个空单元，即新数据将要插入的位置。
置空栈的操作（栈的初始化）
Initstack(seqstack *s)
{
s->top=0;
s->base=0;
}
判栈空操作
int Empty(seqstack *s)
{
if(s->top==s->base)
return true;
else
return false;
}
进栈操作
datatype Push(seqstack *s,datatype x)//将元素x插入顺序栈s的顶部
{
if(s->top==maxsize)
{
printf(“overflow”);
return NULL;
}
else
{
s->data[s->top]=x;
s->top++;
}
return true;
}
出栈操作
datatype Pop(seqstack *s,datatype e)//若栈非空，删除栈顶元素，用e返回其值
{
if(Empty(s))
{
printf(“underflow”);return NULL;
}
else
{
s->top–;
e=s->data[s->top];
return (e);
}
}
取栈顶操作
datatype GetTop(seqstack *s)
{
if(Empty(s))
{
printf(“stack is empty”);//空栈
return NULL;
}
else
return (s->data[s->(top-1)]);
}
在实际工作中可能会用到多个栈，在使用一个数组存储栈时。数组中一般都会有剩余 的空间，如果给每个栈都定义一个数组，则有时会出现一个栈上溢，而另一个栈剩余很多空间的情况。为了合理地使用这些存储单元，可以采用将多个栈存储在同一数组中的方法，即多栈共享空间。
假设两个栈共享一个一维数组s【0，。。。。maxsize-1】，根据栈操作的特点，可使第一个栈使用数组空间的前面空间，并使栈底在前，而使用第二个栈使用数组空间的后面部分，并使栈底在后。
这样处理可以使两个栈最大限度地使用数组空间，下面给出这种空间存储结构的定义：
typedef datatype int //栈元素的数据类型
#define maxsize 64;
typedef struct
{
datatype data[maxsize];
int top1,top2;
}dstack;
设栈s1和s2共享空间s，s1从前向后存放，s2从后向前存放，top1和top2分别是s1和s2的栈顶指针，则在这种存储结构中初始化，进栈，出栈操作算法如下。
初始化操作
InitDstack(dstack *s)
{
s->top1=0;
s->top2=maxsize-1;
}
进栈操作
PushDstack(dstack *s ,char ch,datatype x)//把数据元素x压入栈s的左栈或右栈
{
if (s->top2-s->top1==1) return 0;//栈已满
if(ch==’s1′)
{
s->data[s->top1]=x;
s->top1=s->top1+1;
return 1;
}//进入栈s1；
if (ch==’s2′)
{
s->data[s->top2]=x;
s->top2=s->top2-1;
return 1;
}//进入栈s2
}
出栈操作
PopDstack(dstack *s,char ch)
{
//从栈s1或s2取出栈顶元素并返回其值
if(char==’s1′)
{
if(s->top1==0) return NULL;//栈s1已空
else
{
s->top1=s->top1-1;
return (s->data[s->top1]);
}
}
if(char==’s2′)
{
if(s->top2>maxsize-1) return NULL;
else
{
s->top2=s->top2+1;
return (s->data[s->top2]);
}
}//s2出栈
}
关于3个或3个以上的栈共享一个数组空间的情况，由于可能需要移动中间某个在数组中的相对位置，处理起来不很方便，因为一般不采用。
栈的链式存储结构，
栈的链式存储结构也称为链栈，它是运算受限制的单链表，其插入和删除操作仅限于在表头位置进行，由于只能在链表的头部进行操作，所以没有必要再附加头结点，链栈的栈顶指针就是链表的头指针。
链栈是单链表的特例。所以其类型和变量的说明和单链表一样。
top是栈顶指针，它唯一地确定一个链栈，当top=NULL时，该链表是空栈，
进栈操作
当需要一个新元素w插入链栈时，可动态地向系统申请一个结点p的存储空间，将新元素w写入新结点p的数据域，将栈顶指针top的值写入p结点的指针域。使原栈顶结点成为新结点p的直接后继结点，栈顶指针top改为指向p结点。
linkstack *PushLinkStack(linkstack *top,datatype w)//将元素w插入链表top的栈顶。
{
linkstack *p;
p=(linkstack *)malloc(sizeof(linkstack));
p->data=w;
p->next=top;
top=p;
return p;
}
出栈操作
当栈顶元素出栈时，先取出栈顶元素的值，将栈顶指针top指向top结点的直接后继结点，释放原栈顶结点。
linkstack *PopLinkStack(linkstack *top,datatype *x)//删除链栈top的栈顶结点让x指向栈顶结点的值，返回新栈指针
{
linkstack*p;
if(top==NULL)
{
printf(“空栈，下溢”);return NULL;
}
else
{
*x=top->data;//将栈顶数据存入*x
p=top;//保存栈顶结点地址
top=top->Next;//删除原栈顶结点。
free(p);//释放原栈顶结点。
return top;//返回新栈顶指针。
}
}
置空栈
void InitStack(linkstack *S)
{
s=NULL;
}
判空栈
int StackEmpty(linkstack *S)
{
if(S==NULL) return 1;
else
return 0;
}
去栈顶元素
datatype StackTop(linkstack *S)
{
if(StackEmpty(S))
{Error(“Stack is empty”); return NULL;}
return S->data;
}
顺序栈和链式栈的比较
实现顺序栈和链式栈的所有操作的时间相同，都是常数级的时间，但初始化一个顺序栈必须先声明一个固定长度。这样在栈不够满时。就浪费了一部分存储空间，而链式栈不存在这个问题。
但可以利用顺序栈的这一特性同时实现两个栈，使用一个数组存储两个栈，每个栈从各自的端点向中间延伸，这样就节约了空间。只有当整个向量空间被两个栈占满（即两个栈顶相遇时）才发生上溢，因此，两个栈共享一个长度为m的向量空间和两个栈分别占用两个长度为m/2和m/2的向量空间比较，前者发生上溢的概率比后者要小的多。