目录

1 栈

1.1 栈的定义

1.2 栈的表示和实现

顺序栈

两栈共享技术（双端栈）

 链栈

多栈运算

1.3 栈的应用举例

1. 括号匹配问题

2. 表达式求值

1.4 栈与递归的实现

                                       为了自己的目标和追求，也希望带给更多的人帮助。

1 栈

1.1 栈的定义

栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶 (Top)，表的另一端被称为栈底 (Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。

 进栈、出栈图例

       根据栈定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。因此，栈又称为后进先出的线性表。简称为LIFO表。如下图所示：

栈的抽象数据类型定义

数据元素：可以是任意类型的数据，但必须属于同一个数据对象。

关系：栈中数据元素之间是线性关系

基本操作：

1.InitStack（S）    2. ClearStack（S） 3. IsEmpty（S）      4. IsFull（S）  

 5. Push（S，x）   6. Pop（S，x）        7. GetTop（S，x）

1.2 栈的表示和实现

栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。

顺序存储的栈为顺序栈； 链式存储的栈为链栈。

顺序栈

 顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top = -1表示空栈。

 栈的顺序存储结构定义如下 ：

#define Stack_Size 50typedef struct{StackElementType  elem[Stack_Size];   /*用来存放栈中元素的一维数组*/int  top;   /*用来存放栈顶元素的下标，top为-1表示空栈*/}SeqStack; 

 顺序栈中的进栈和出栈图例：

顺序栈基本操作的实现

 1）初始化

void  InitStack(SeqStack *S){/*构造一个空栈S*/  S->top= -1;}

 2）进栈

int Push(SeqStack * S, StackElementType x){if(S->top== Stack_Size)  return(FALSE);  /*栈已满*/S->top++;S->elem[S->top]=x;return(TRUE);}

3）出栈

int Pop(SeqStack * S, StackElementType *x){    if(S->top==-1)     /*栈为空*/     return(FALSE);      else  {*x= S->elem[S->top];      S->top--;    /* 修改栈顶指针 */      return(TRUE);   }}

4） 取栈顶元素

int GetTop（SeqStack S, StackElementType *x）{  /* 将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变 */if(S->top==-1)  /*栈为空*/     return(FALSE);else    {*x = S->elem[S->top]; return(TRUE);     }}

[注意]：

在实现GetTop操作时，也可将参数说明SeqStack *S 改为SeqStack S，也就是将传地址改为传值方式。传值比传地址容易理解，但传地址比传值更节省时间、空间。

两栈共享技术（双端栈）

主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间S[M]，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。

共享栈的空间示意为：top[0]和top[1]分别为两个栈顶指示器 。

 两栈共享的数据结构定义

#define M 100typedef struct{ StackElementType Stack[M]; StackElementType top[2];  /*top[0]和top[1]分别为两个栈顶指示器*/}DqStack;

两栈共享的初始化操作算法

void InitStack(DqStack *S){S->top[0]=-1;S->top[1]=M;}

 两栈共享的进栈操作算法

int Push(DqStack *S, StackElementType x, int i){  /*把数据元素x压入i号堆栈*/if(S->top[0]+1==S->top[1])      /*栈已满*/ return(FALSE);switch(i){case 0:S->top[0]++; S->Stack[S->top[0]]=x; break;  case 1: S->top[1]--; S->Stack[S->top[1]]=x; break;  default: return(FALSE)  /*参数错误*/ }return(TRUE);}

 两栈共享的出栈操作算法

int Pop(DqStack *S, StackElementType *x, int i){ /* 从i 号堆栈中弹出栈顶元素并送到x中 */   switch(i)    {case 0: if(S->top[0]==-1)  return(FALSE);   *x=S->Stack[S->top[0]]; S->top[0]--; break;      case 1:if(S->top[1]==M)  return(FALSE); *x=S->Stack[S->top[1]];S->top[1]++;break;default: return(FALSE);}return(TRUE);}

 链栈

链栈是采用链表作为存储结构实现的栈。为便于操作，采用带头结点的单链表实现栈。由于栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针。

链栈的示意图为：

注意：链栈在使用完毕时，应该释放其空间。

链栈结构的用C语言定义

typedef struct node{  StackElementType  data;  struct node *next;}LinkStackNode;typedef  LinkStackNode  *LinkStack;

 链栈的进栈操作

int Push(LinkStack top, StackElementType x)/* 将数据元素x压入栈top中 */  {  LinkStackNode * temp;   temp=(LinkStackNode * )malloc(sizeof(LinkStackNode));   if(temp==NULL)  return(FALSE);   /* 申请空间失败 */temp->data=x; temp->next=top->next;top->next=temp;   /* 修改当前栈顶指针 */ return(TRUE);}

链栈的出栈操作

int Pop(LinkStack top, StackElementType *x){  /* 将栈top的栈顶元素弹出，放到x所指的存储空间中 */    LinkStackNode * temp; temp=top->next;    if(temp==NULL)  /*栈为空*/return(FALSE);    top->next=temp->next; *x=temp->data;     free(temp);   /* 释放存储空间 */     return(TRUE);}

多栈运算

 将多个链栈的栈顶指针放在一个一维指针数组中来统一管理，从而实现同时管理和使用多个栈。

 用c语言定义

#define  M  10   /*M个链栈*/typedef struct node{    StackElementType  data;    struct node*next;}LinkStackNode,  *LinkStack;  LinkStack  top[M]; 

(1)第i号栈的进栈操作

int  pushi(LinkStack  top[M],  int  i,  StackElementType  x){/*将元素x进入第i号链栈*/LinkStackNode  *temp;temp=(LinkStackNode * )malloc(sizeof(LinkStackNode));if(temp==NULL)  return(FALSE);   /* 申请空间失败 */temp->data=x;temp->next=top[i]->next;    top[i]->next=temp;   /* 修改当前栈顶指针 */   return(TRUE);} 

(2) 第i号栈元素的出栈操作

int Pop(LinkStack  top[M],  int  i,  StackElementType  *x){  /* 将栈top的栈顶元素弹出，放到x所指的存储空间中 */     LinkStackNode  *temp;     temp=top[i]->next;     if(temp==NULL)  /*第i号栈为空栈*/return(FALSE);    top[i]->next=temp->next;    *x=temp->data;    free(temp);   /* 释放存储空间 */  return(TRUE);   } 

1.3 栈的应用举例

1. 括号匹配问题

思想：在检验算法中设置一个栈，若读入的是左括号，则直接入栈，等待相匹配的同类右括号；若读入的是右括号，且与当前栈顶的左括号同类型，则二者匹配，将栈顶的左括号出栈，否则属于不合法的情况。另外，如果输入序列已读尽，而栈中仍有等待匹配的左括号，或者读入了一个右括号，而栈中已无等待匹配的左括号，均属不合法的情况。当输入序列和栈同时变为空时，说明所有括号完全匹配。

void BracketMatch(char *str){Stack S; int i; char ch;InitStack(&S);For(i=0; str[i]!='\0'; i++) {switch(str[i])      {case '(':case '[':case '{': Push(&S,str[i]); break;case ')':case ']':case '}':if(IsEmpty(S)) { printf("\n右括号多余!");  return;}else{GetTop (&S,&ch);if(Match(ch,str[i])) Pop(&S,&ch); else{ printf("\n对应的左右括号不同类!");  return;}}}/*switch*/}/*for*/if(IsEmpty(S))printf("\n括号匹配!");elseprintf("\n左括号多余!");}

2. 表达式求值

1) 无括号算术表达式求值

无括号算术表达式的处理过程

2) 算术表达式处理规则

（1）规定优先级表；

(2) 设置两个栈：OVS(运算数栈)和OPTR(运算符栈)；

(3) 自左向右扫描，遇操作符则与OPTR栈顶优先级比较：当前操作符>OPTR栈顶则进OPTR栈；当前操作符≤ OPTR栈顶，OVS栈顶、次顶和OPTR栈顶，退栈形成运算T（i）， T（i）进OVS栈。

例：实现A/B↑C+D*E#的运算过程时栈区变化情况

 3) 带括号算术表达式

实现算符优先算法时需要使用两个工作栈：一个称作运算符栈operator；另一个称作操作数栈operand。 算法的基本过程如下：

A.初始化操作数栈operand和运算符栈operator，并将表达式起始符“#”压入运算符栈；

B.读入表达式中的每个字符，若是操作数则直接进入操作数栈operand，若是运算符，则与运算符栈operator的栈顶运算符进行优先权比较，并做如下处理：

(1) 若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进operator栈；    

(2) 若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入θ，同时将操作数栈operand退栈两次，得到两个操作数a、b，对a、b进行θ运算后，将运算结果作为中间结果推入operand栈；      

(3) 若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，只需将栈顶运算符（左括号）退栈即可。

当operator栈的栈顶元素和当前读入的字符均为“#”时，说明表达式起始符“#”与表达式结束符“#”相遇，整个表达式求值完毕。

1.4 栈与递归的实现