一、栈的介绍
栈(Stack)是限定只能在表的一端进行插入删除操作的线性表。
允许插入和删除运算的一端称作栈顶(top)。
不允许插入和删除的另一端称作栈底(bottom)。
在栈顶进行的插入操作称为入栈或进栈(push)
在栈顶进行的删除操作称为出栈或退栈(pop)
栈的特点:后进先出,即 LIFO(Last In First Out)
如下图:

顺序栈的数据类型
静态分配:

#define MaxSize 100#define int ElemType typedef struct{ ElemType data[MaxSize]; // 数组存储空间  int top;   //栈顶下标} SqStack;  // 顺序栈数据类型

MaxSize为顺序栈的最大容量;
top为栈顶元素的下标,0 <= top <= MaxSize-1
栈空:top = -1;
栈满:top = MaxSize-1


注意栈空和栈满的判断条件,如上图,栈顶top = 0 时,有数据元素a1,所以top = -1时,才能判断栈空。栈满时,由上图看知。

动态分配:

#define int ElemType typedef struct{   ElemType *base;  //栈底的指针  ElemType *top;   //栈顶的指针} SqStack;  // 顺序栈数据类型

链式栈的数据型

typedef struct LNode{  ElemType data;      //数据域  struct LNode *next; //后继结点指针} LinkStNode;         //链栈结点类型

S:单链表头指针,指向头结点。
栈顶:单链表第一个元素结点的位置,即头结点的后一个位置。

二、顺序栈的基本运算
1、初始化栈
建立一个新的空栈s,实际上是将栈顶指示变量置-1即可。

//初始化空顺序栈int InitStack(SqStack &S){S.top = -1;return 1;}

2、入栈
①判断栈是否已满,若满则产生上溢出错误,退出算法,否则执行第②步;
②栈顶下标增一(top++),指向新的栈顶位置;
③将新元素置于栈顶。

//item是需要入栈的数据元素bool Push(SqStack &S, ElemType item){  if (S.top == MaxSize - 1)  {    cout << "栈满" << endl;    return false;  }  S.top++;  S.data[S.top] = item;  return true;}

3、出栈:
①判断栈是否为空,若空则产生下溢出错误,退出算法,否则执行第②步;
②栈顶元素出栈;
③栈顶下标减一(top++),指向新的栈顶位置;

bool Pop(SqStack &S, ElemType &item){  if (S.top == -1)  {    cout << "栈空" << endl;    return false;  }  item = S.data[S.top];  S.top--;  return true;}

4、判断栈是否为空
栈S为空的条件是s.top==-1。

//判栈空int StackEmpty(SqStack &S){if(S.top==-1)return 1;elsereturn 0;}

5、取栈顶元素
在栈不为空的条件下,将栈顶元素赋给e。

//取栈顶int GetTop(SqStack &S, DataType &e){    if(S.top <= -1)    {         cout<<"栈空"<<endl;         return 0;    }   item=S.items[S.top];   return 1;}

注意:
取栈顶元素和出栈不同,取栈顶元素只是把栈顶元素复制一份,栈顶指针并没有改变。如下图:

入栈时要判断栈是否满,出栈时要判断是否为空。

三、链式栈的基本运算
1、初始化栈
建立一个空栈s。实际上是创建链栈的头结点,并将其next域置为NULL。

void (SNode *&s){      s=(SNode *)malloc(sizeof(SNode));//s=new SNode;    s->next=NULL;}

2、入栈:

bool Push(LinkStNode *S, ElemType item){ //带头结点单链表的表头插入法  LinkStNode *t = new LinkStNode; //①生成新结点  if (t == NULL)  {    cout << "内存不足";    return false;  }  t->data = item;  //②在栈顶插入新结点  t->next = S->next;  S->next = t; //③  return true;}


3、出栈:

bool Pop(LinkStNode *S, ElemType &item){ //删除单链表的第一个元素结点  //①判断栈是否为空  if (S->next == NULL)  {    cout << "栈空";    return false;  }  //②删除栈顶元素  LinkStNode *t = S->next;  S->next = t->next;  item = t->data;  delete t;  return true;}


4、销毁栈

//释放链栈void Destroy(SNode *&s){SNode *p;while(s!=NULL){p=s;s=s->next;delete p;}}

5、判断栈是否为空
栈S为空的条件是s->next==NULL,即单链表中没有数据结点。

//判栈空int StackEmpty(SNode *s){if(s->next==NULL)return 1;elsereturn 0;}

6、取栈顶元素

int GetTop(SNode *s,DataType &e){      if (s->next==NULL)//栈空的情况{return 0;}    e=s->next->data;    return 1;}