🌞欢迎来到数据结构的世界 
🌈博客主页：卿云阁

💌欢迎关注🎉点赞👍收藏⭐️留言📝

🌟本文由卿云阁原创！

🌠本阶段属于锻体阶段，希望各位仙友顺利完成突破

📆首发时间：🌹2021年1月27日🌹

✉️希望可以和大家一起完成进阶之路！

🙏作者水平很有限，如果发现错误，请留言轰炸哦！万分感谢！

---

目录

0️⃣栈的定义

1️⃣栈的顺序存储结构

2️⃣栈的链式存储结构

3️⃣栈的应用举例

🅰数制转换问题

🅱括号匹配的检验

🅾简单表达式求值

0️⃣✨✨✨栈的定义✨✨✨ 

栈的抽象数据类型定义如下： 

ADT Stack {
数据对象D：D＝{ ai|ai∈ElemSet, i=1,2,...,n, n≥0 }
数据关系R：R＝{ <ai-1, ai>|ai-1, ai∈D, i=2,...,n }
约定an 端为栈顶，a1 端为栈底。
基本操作 P：
InitStack(&S)
操作结果：构造一个空栈S。
StackEmpty(S)
初始条件：栈S已存在
操作结果：若栈S为空栈，则返回TRUE，否则FALSE。
StackFull(S)
初始条件：栈S已存在
操作结果：若栈S满，则返回TRUE，否则FALSE。
GetTop(S, &e)
初始条件：栈S已存
操作结果：若栈S非空，用e返回S的栈顶元素。
Push(&S, e)
初始条件：栈S已存在。
操作结果：若栈S不满，插入元素e为新的栈顶元素。
Pop(&S, &e)
初始条件：栈S已存在且非空。
操作结果：若栈S非空，删除S的栈顶元素，并用e返回其值。
} ADT Stack

1️⃣✨✨✨栈的顺序存储结构✨✨✨

1.顺序栈的类型定义

#define MAXSIZE 100
typedef struct
{ DataType data[MAXSIZE];int top;
}SqStack;

 在顺序栈中，用于指示栈顶的当前位置的top是整型，它的实质是栈顶元素在数组中的下标。

 2.顺序栈的算法实现

(1)初始化栈(置栈空)

int  InitStack(SqStack *S)
{   //构造一个空栈S->top= -1;return OK;
}

(2)判栈空 判栈满

int Push(SqStack &S, DataType e)
{ //将元素e插入到栈中，作为的新栈顶if(StackFull(S))  return ERROR; //栈满S.top++;    // top加1，栈顶位置上移S.data[S.top]=e;   //数据e存入当前栈顶return  OK;
}

(4)进栈

进栈时应首先判栈满，若栈不满则将栈顶指针top上移，存入元素。

int Push(SqStack &S, DataType e)
{ //将元素e插入到栈中，作为的新栈顶if(StackFull(S))  return ERROR; //栈满S.top++;    // top加1，栈顶位置上移S.data[S.top]=e;   //数据e存入当前栈顶return  OK;
}

(5)出栈 

int Pop(SqStack &S,DataType &e)
{//若栈不为空，则删除栈顶元素if(StackEmpty(S)) return ERROR; //栈空e=S.data[S.top];   //取出数据放入e所指单元中S.top--;     // top减1，栈顶位置下移return OK;
}

(6)取栈顶元素1,

int GetTop(SqStack S,DataType &e)
{//若栈不为空，则取栈顶元素if(StackEmpty(S)) return ERROR;  //栈空e=S.data[S.top];    //取出数据，top不变return OK;
}

取栈顶元素2

DataType GetTop(SqStack S)
{//若栈不为空，则取栈顶元素DataType e;if(StackEmpty(S)) return ERROR;  //栈空e=S.data[S.top];    //取出数据，top不变return e;
}

---

2️⃣✨✨✨栈的链式存储结构✨✨✨ 

1.链栈的类型定义

typedef struct node
{ DataType data;struct node* next;
} StackNode,*LinkStack;
LinkStack top;   //top为栈顶指针

 

2.链栈的算法实现 

(1)初始化栈(置空栈)
LinkStack  InitStack()
//空栈的top指针为NULL
｛  return NULL;   ｝
(2)判栈空
int  StackEmpty(LinkStack top)      
//判栈为空栈时返回值为真，反之为假
{   return(top==NULL? TRUE:FALSE);  }

 (3)进栈

void Push(LinkStack top, DataType e)
{   //将元素e进链栈,即在表头插入新的结点StackNode  *s;s=(StackNode*)malloc(sizeof(StackNode));s->data=e;s->next=top;top=s;
}

(4)出栈

int Pop(LinkStack top,DataType &e)
{   //若栈不为空将栈顶元素出栈，即为删除表头结点StackNode *p;if(StackEmpty(top)) return  ERROR;  //栈空e=top->data;p=top;top=top->next;free(p);retrun OK;
}

---

3️⃣✨✨✨栈的应用举例✨✨✨

🅰数制转换问题

是指对于输入的任意一个非负十进制整数N，打印输出与其等值的r进制数。

将十进制数N转换为r进制数，算法思路如下： (1)当N≠0，则重复执行①，②     ①将N % r进栈s；     ②N = N / r   (2)将栈s的内容依次出栈，算法结束。

typedef int DataType;
void conversion(int N, int r)
{  SqStack S;    	  //定义一个顺序栈SDataType x;InitStack(S);while(N){  Push(S, N%r);   		//余数入栈N=N/r;}while(!StackEmpty(S)){   Pop(S,x);printf("%d",x);}
}

🅱括号匹配的检验

假设在一个算术表达式中，可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”和花括号“{”和“}”，并且这三种括号可以按任意的次序嵌套使用，比如某一个算术表达式中的括号使用括号情况为“...[...{...}...[...]...]...[...]...(...)..”。括号匹配的检验主要就是判别给定表达式中所含括号是否正确配对。

依次输入表达式每一个字符，若是左括号，将其入栈保存；若是右括号，则出栈左括号，并检验与其是否匹配。循环执行，直到表达式输入结束。

注意：在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。

当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号； 从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况； 算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。

typedef char DataType;
int bracketmatching()
{
SqStack S;
DataType ch;
InitStack(S);
while ((ch=getchar())!='\n') 
{
switch (ch)     //遇左括号入栈;遇到右括号时,分别检测匹配情况
{case '(':case '[':case '{': Push(S,ch);break; 
case  ')':if (StackEmpty(S)) return FALSE; else { Pop(S,ch);  if (ch!= '(') return FALSE; }break;case ']':if (StackEmpty(S)) return FALSE;else { Pop(S,ch);   if (ch!= '[') return FALSE; }break;case '}':if (StackEmpty(S)) return FALSE;else{ Pop(S,ch);  if (ch!='{') return FALSE; }break;default:break;}}if (StackEmpty(S)) return TRUE;else return FALSE;
}

🅾简单表达式求值

(1)表达式的构成

在计算机中，任何一个表达式都是由操作数（operand）、运算符（operator）和界限符（delimiter）组成的。本节讨论的简单表达式中，其操作数由数字0～9构成，运算符包括加、减、乘、除和括号，表达式界限符设定为“=”。由此，将表达式的构成分成两类符号：操作数和算符，其中算符包含运算符和界限符。

(2)表达式的运算规则 先乘除后加减； 同级运算时先左后右； 先括号内，后括号外

(1)算符优先关系的实现
char Precede (char a,char b)  /*比较两个运算符的优先级*/
{char z;if((b=='+')||(b=='-')||(b=='*')||(b=='/')|| (b=='(')||(b==')') ||(b=='='))switch (a){case '+':case '-':if((b=='*')||(b=='/')||(b=='(')) z='<';else z='>'; break;case '*':case '/':if(b=='(')  z='<';else z='>';break;case '(':if(b=='=') z='E';else if(b==')')z='=';else z='<';break;case ')':if(b=='(') z='E';else z='>'; break;case '=':if(b=='=')z='=';else if(b==')') z='E';else z='<';break;}else z='E';return(z);
}
float CalculateExpression()
{  //算术表达式求值的算符优先算法。设optr和opnd分别为算符栈和操作数栈，
//OP为算符集合
InitStack(optr); Push(optr, '=');
InitStack(opnd); 
c=getchar();
while(c!='=' ||GetTop(optr)!='=')
{ if(!In(c)){Push(opnd,c); c=getchar();} //不是算符则进栈else
switch(Precede(GetTop(optr),c)){ case '<' :   //栈顶算符优先级低Push(optr,c); c=getchar();break;case '=' : //优先级相同，脱去括号并读入下一字符Pop(optr,x); c=getchar();break;case '>' : //栈顶算符优先级高，退栈并将运算结果入栈Pop(optr,theta);Pop(opnd,b);Pop(opnd,a);Push(opnd,Operate(a,theta,b));break;}}return GetTop(opnd);
}int In(char ch)  /*判断字符ch是否为算符*/
{int i,flag=0;char op[7]={'+','-','*','/','(',')','='};   /*算符数组*/for (i=0;i<7;i++)if(ch==op[i]){flag=1;break;}return flag;
}