数据结构（严蔚敏版）第三章——栈和队列（二）【栈的表示和操作的实现】

ADTStack {
数据对象；D= {ai|ai属于ElementSet, i=1, 2, ... , n, n>=0}
数据关系：R1= {<ai-1, ai>|ai-1, ai属于D, i=2, ... , n }
约定an端为栈顶，a1端为栈底基本操作：InitStack(&S)
操作结果：构造一个空栈DestroyStack(&S)
初始条件：栈S已存在操作结果：栈S被销毁ClearStack(&S)
初始条件：栈S已存在操作结果：将栈S清空为空栈StackEmpty(S)
初始条件：栈S已存在操作结果：若栈S为空栈，则返回true，否则则返回falseStackLength(S)
初始条件：栈S已存在操作结果：返回S的元素个数，即栈的长度GetTop(S, e)
初始条件：栈S已存在操作结果：返回S的栈顶元素，不修改栈顶的指针Push(&S, e)
初始条件：栈S已存在操作结果：插入元素e为新的栈顶元素Pop(S)
初始条件：栈S已存在操作结果：删除S的栈顶元素，并用e返回其值StackTraverse(S)
初始条件：栈S已存在且非空操作结果：从栈底到栈顶依次对S的每个数据元素进行访问}ADTStack

#define MAXSIZE 100       // 顺序栈存储空间的初始分配量typedefstruct{
SElemType*base;        // 栈底指针SElemType*top;         // 栈顶指针intstacksize;          // 栈可用的最大容量}SqStack;

StatusInitStack(SqStack&S)
{ // 构造一个空栈S.base=newSElemType[MASIZE]; // 或S.base = (SElemType*)malloc(MAXSIZE*sizeof(SElemType));if (!S.base) exit (OVERFLOW);   // 存储分配失败S.top=S.base;                 // 栈顶指针等于栈底指针S.stacksize=MAXSIZE;          // stacksize置为栈的最大容量MAXSIZEreturnOK;
}

StatusStackEmpty(SqStackS)
{ // 若栈为空，返回TRUE；否则返回FALSEif (S.top==S.base) 
returnTRUE;
elsereturnFALSE;
}

intStackLength(SqStackS)
{
returnS.top-S.base;
}

StatusClearStack(SqStackS)
{
if (S.base) S.top=S.base;
returnOK;
}

StatusDestroyStack(SqStack&S)
{
if (S.base) 
  {
deleteS.base;
S.stacksize=0;
S.base=S.top=NULL;
  }
returnOK;
}

StatusPush(SqStack&S, SElemTypee)
{ // 插入元素e为新的栈顶元素if (S.top-S.base==S.stacksize) returnERROR;    // 栈满*S.top++=e;
// 或 *S.top = e; S.top++;returnOK;
}

StatusPop(SqStack&S, SElemType&e)
{ // 删除S的栈顶元素，用e返回其值if (S.top==S.base) returnERROR;  // 栈空e=*--S.top;                       // 栈顶指针减1，将栈顶元素赋给e// 或 e = S.top; S.top--;returnOK;
}

SElemTypeGetTop(SqStackS) 
{ // 返回S的栈顶元素，不修改栈顶指针if(S.top!=S.base)         // 栈非空return*(S.top-1);      // 返回栈顶元素的值，栈顶指针不变}

typedefstructStackNode{
SElemTypedata;
structStackNode*next;
}StackNode, *LinkStack;
LinkStackS;

voidInitStack(LinkStack&S) 
{  // 构造一个空栈，栈顶指针置为空S=NULL;
returnOK;
}

StatusStackEmpty(LinkStackS)
{
if (S==NULL)  returnNULL;
elesereturnFALSE;
}

StatusPush(LinkList&S, SElemTypee)
{  // 在栈顶插入元素ep=newStackNode;                  // 生成新的结点p->data=e;                      // 将新结点的数据域置为ep->next=S;                      // 将新结点插入栈顶S=p;                              // 修改栈顶指针为preturnOK;
}

StatusPop(LinkStack&S, SElemType&e)
{  // 删除S的栈顶元素，用e返回其值if (S==NULL)
returnERROR;                   // 栈空e=S->data;                    // 将栈顶元素赋给ep=S;                            // 用p临时保存栈顶元素空间，以备释放S=S->next;                    // 修改栈顶指针deletep;                         // 释放原栈顶元素的空间returnOK;
}

SElemTypeGetTop(LinkListS)
{  // 返回S的栈顶元素，不修改栈顶元素if (S!=NULL)                // 栈非空  {
returnS->data;           // 返回栈顶元素的值，栈顶指针不变  }
}