栈 stack
1)栈 是限定 在表尾(栈顶)进行插入和删除操作的线性表
栈是一种思想 "先进后出 LIFO" "后进先出"
栈顶 top 进行插入和删除操作的地方(表尾)
栈底 bottom (表头)
2)要对栈进行的基本操作:
InitStack() 初始化一个栈
Push() 入栈
Pop() 出栈
StackLength() 栈的长度(元素个数)
GetTop() 获取栈顶元素的值,但是不出栈
IsEmpty() 判断是否为空栈
ClearStack() 清空栈
DestroyStack() 销毁栈
3)栈的实现
3.1)顺序栈
顺序结构的存储方式
用一组地址连续的空间 依次存放栈的每一个元素 "数组"
#define MAX_LEN 20 //栈的最大的容量
typedef int ElemType; //数据的类型typedef struct SqStack //顺序栈
{
ElemType *data; //data指向一块地址连续的空间,来存储栈的每一个元素
//指针实现 : data = (ElemType *)malloc( sizeof(ElemType) * MAX_LEN );
//数组实现 : ElemType data[MAX_LEN];int top; //栈顶, 指定栈顶元素的下标
//top == -1 表示栈中没有元素, 空栈
} SqStack ;
练习:
1)初始化一个顺序栈, 将栈的地址返回
SqStack.c / SqStack.h
//初始化一个顺序栈
SqStack * InitStack()
{//创建一个顺序栈,并初始化SqStack * s = (SqStack *)malloc( sizeof(SqStack) );s->data = (ElemType *)malloc( sizeof(ElemType)*MAX_LEN );s->top = -1;return s;
}
2)销毁一个顺序栈
//销毁一个顺序栈
void DestroyStack( SqStack * s )
{if( s == NULL ){return ;}if( s->data ){free( s->data );}s->top = -1;free(s);
}
3)清空一个栈
//清空一个栈
void ClearStack( SqStack * s )
{ if( s ){//清空之后,只能入栈,会把原来的数据覆盖掉s->top = -1;}
}
4)判断是否为空栈
返回值:
1 为空
0 不为空
/*
int IsEmpty( SqStack * s )
{//栈为空: 栈不存在 || 栈里面没有元素if( s == NULL || s->top == -1 ){return 1;}return 0;
}
*/
bool IsEmpty( SqStack * s )
{//栈为空: 栈不存在 || 栈里面没有元素if( s == NULL || s->top == -1 ){return true;}return false;
}
5)获取栈的长度 (栈中元素的个数)
//获取栈的长度 (栈中元素的个数)
int StackLength( SqStack * s )
{if( s == NULL ){return 0;}return s->top + 1;
}
6)入栈
返回值:
1 入栈成功
0 入栈失败
int Push( SqStack * s, ElemType d )
{//不能入栈的情况: 栈不存在 || 栈满了if( s == NULL || s->data == NULL || s->top == MAX_LEN - 1 ){//printf("Push error! \n");return 0;}//入栈 s->data[ ++(s->top) ] = d;return 1;
}
7)出栈
返回值:
1 出栈成功
0 出栈失败
int Pop( SqStack * s, ElemType *d )
{//不能出栈的情况: 栈不存在 || 栈为空if( s == NULL || s->data == NULL || s->top == -1 ){//printf("Pop error! \n");return 0;}//出栈 *d = s->data[ (s->top)-- ];return 1;
}
8)获取栈顶元素的值,但是不出栈
返回值:
1 出栈成功
0 出栈失败
int GetTop( SqStack * s, ElemType *d )
{//不能出栈的情况: 栈不存在 || 栈为空if( s == NULL || s->data == NULL || s->top == -1 ){//printf("GetTop error! \n");return 0;}//获取栈顶元素的值,但是不出栈 (top下标不变) *d = s->data[ s->top ];return 1;
}
3.2) 链式栈
用链表来实现 "带头结点的双向链表"
//数据元素的类型
typedef int ElemType; //数据元素中数据的类型
typedef struct node
{
ElemType data; //数据域 --> 存储数据
struct node * next; //指针域 --> 保存逻辑上的下一个
struct node * prev; //保存逻辑上的上一个
} DNode;//栈 头结点的类型
typedef struct LinkStack
{
struct node * top; //指向栈顶元素 last
struct node * bottom; //指向栈底元素 first
int num; //记录栈中元素的个数
//...
} LinkStack;
基本操作: 同上
练习:
1)初始化一个栈, 将栈的地址返回
LinkStack.c / LinkStack.h
//初始化一个栈
LinkStack * InitStack()
{//创建一个栈(头结点), 并初始化 LinkStack * s = (LinkStack *)malloc( sizeof(LinkStack) );s->top = NULL;s->bottom = NULL;s->num = 0;return s;
}
2)清空一个栈
//清空一个栈
void ClearStack( LinkStack * s )
{//栈不存在 || 空栈 if( s == NULL || s->top == NULL ){return ;}//遍历 --> 释放所有的数据节点的空间 DNode * p = s->top; //遍历指针while( p ){s->top = s->top->prev;if( s->top ){s->top->next = NULL;}p->prev = NULL;free( p );p = s->top;}s->num = 0;s->bottom = NULL;
}
3)销毁一个栈
//销毁一个栈
void DestroyStack( LinkStack * s )
{//栈不存在if( s == NULL ){return ;}//释放所有的数据节点的空间ClearStack( s );//再 释放栈头结点free( s );
}
4)判断是否为空栈
返回值:
1 为空
0 不为空
int IsEmpty( LinkStack * s )
{//栈不存在 || 栈里面没有元素 if( s == NULL || s->top == NULL ){return 1;}return 0;
}
5)获取栈的长度 (栈中元素的个数)
//获取栈的长度 (栈中元素的个数)
int StackLength( LinkStack * s )
{if( s == NULL ){return 0;}return s->num;
}
6)入栈
返回值:
1 入栈成功
0 入栈失败
int Push( LinkStack * s , ElemType d )
{//栈不存在if( s == NULL ){return 0;}//为入栈的元素 创建一个新的节点空间, 并初始化DNode * pnew = (DNode *)malloc( sizeof(DNode) );pnew->data = d;pnew->next = NULL;pnew->prev = NULL;//入栈, 只能在栈顶top进行插入和删除操作 --> 尾插法 if( s->top == NULL ) //从无到有{s->top = pnew;s->bottom = pnew;}else //从少到多{//尾插法s->top->next = pnew;pnew->prev = s->top;s->top = pnew;}s->num ++;return 1;
}
7)出栈
返回值:
1 出栈成功
0 出栈失败
int Pop( LinkStack * s , ElemType *d )
{//栈不存在 || 栈为空if( s == NULL || s->top == NULL ){return 0;}//出栈 //先获取栈顶元素top的值 *d = s->top->data;//然后在释放该栈顶元素top (删除尾节点)DNode *p = s->top;s->top = s->top->prev;if( s->top ){s->top->next = NULL;}p->prev = NULL;free( p );s->num --;if( s->num == 0 ){s->bottom = NULL;}return 1;
}
8)获取栈顶元素的值,但是不出栈
返回值:
1 出栈成功
0 出栈失败
int GetTop( LinkStack * s , ElemType *d )
{//栈不存在 || 栈为空if( s == NULL || s->top == NULL ){return 0;}//获取栈顶元素的值 *d = s->top->data;return 1;
}
练习:
1)简答题 :
有5个元素,其入栈顺序为: A,B,C,D,E
在各种可能出栈的次序中,
第一个出栈为C,且第二个出栈为D的情况有哪些?
CDEBA
CDBEA
CDBAE
2)编程题
从键盘上获取一串数学表达式(数字+运算符+括号)
请判断其括号是否匹配正确
返回值:
1 匹配正确
0 匹配错误
例子:
9+3-2*(3-1)+5 OK
{(1+2*3)-[3]()} OK
(4-2*[6){} error
(1*3+[2-3)+4] error
栈的思想
遍历字符串
如果是左边的括号, 就入栈 (入栈其对应的右边括号)
如果是右边的括号, 就出栈 进行对比
int judge_match_brake( char *str )
{int flag = 1; //标志位,1匹配正确,0匹配失败//初始化一个顺序栈SqStack * s = InitStack();//遍历字符串 int i;for( i=0; i<=strlen(str); i++ ){//如果是左边的括号, 就入栈 (入栈其对应的右边括号)if( str[i] == '(' ){Push( s, ')' );}else if( str[i] == '{' ){Push( s, '}' );}else if( str[i] == '[' ){Push( s, ']' );}//如果是右边的括号, 就拿它与出栈元素 进行对比if( str[i] == ')' || str[i] == '}' || str[i] == ']' ){if( ! IsEmpty( s ) ) //栈不为空{ElemType temp = 0;Pop( s, &temp ); //出栈if( temp != str[i] ){flag = 0;break;}}else //栈为空:左边的括号少了,右边的括号多了{flag = 0;break;}}}//比较完之后, 栈不为空: 左边的括号多了if( ! IsEmpty( s ) ){flag = 0;}//销毁栈DestroyStack( s );return flag;
}int main()
{char buf[128] = {0};scanf("%s", buf );int flag = judge_match_brake( buf );if( flag ){printf("Right!\n");}else {printf("Error!\n");}
}
3) 实现 简易计算器的功能 + - * /
输入一串数学表达式, 计数这个表达式的结果
输入: 1+22*4/2+10-5+20
输出: 70
提示:
运算符栈
操作数栈
//判断字符 是否为运算符 +-*/
int is_operator_char( char ch )
{if( ch == '+' || ch == '-' || ch == '*' || ch == '/' ){return 1;}return 0;
}//运算符的优先级的比较 (ch1是待入栈, ch2是栈顶)
int compare_operator( char ch1, char ch2 )
{if( ( ch1 == '*' || ch1 == '/' ) && ( ch2 == '+' || ch2 == '-' ) ){return 1;}return 0;
}//计算
int calculate( SqStack *sd, SqStack *so )
{//1个运算符 + 2个操作数int a = 0, b = 0;Pop( sd, &b );Pop( sd, &a );int op = 0;Pop( so, &op );switch( op ){case '+' : return a+b;case '-' : return a-b;case '*' : return a*b;case '/' : return a/b;default : return 0;}
}int expression( char * str )
{if( str == NULL ){return 0;}//初始化两个栈(运算符栈+操作数栈) intSqStack *sd = InitStack(); //操作数栈SqStack *so = InitStack(); //运算符栈//解析字符串while( *str ){//如果是数字字符,则合成操作数,然后入栈 int d = 0;while( *str >= '0' && *str <= '9' ){d = d*10 + (*str - '0');str++;}Push( sd, d ); //操作数就直接入栈if( *str == '\0' ){break;}//如果是运算符 if( is_operator_char( *str ) ){while(1) {//栈为空 || 带入栈的运算符的优先级高于栈顶元素的优先级 --> 入栈int top = 0;GetTop( so, &top ); //获取栈顶运算符if( IsEmpty( so ) || compare_operator( *str, top ) ){Push( so, *str );break;}else {//否则 就出栈(1个运算符+2个操作数) 计算, 再将结果继续入栈int sum = calculate( sd, so );Push( sd, sum );}}}str++;}//将剩余的全部出栈 进行计算while( !IsEmpty( so ) ) {int sum = calculate( sd, so );Push( sd, sum );}//最后将结果出栈int ret = 0;Pop( sd, &ret );//销毁栈DestroyStack( sd );DestroyStack( so );return ret;
}int main()
{char buf[128] = {0};scanf("%s", buf );int sum = expression( buf );printf("%s = %d\n", buf, sum );
}
=====================
中缀表达式
就是我们平时所用的标准四则运算表达式, 比如 9+3-2*(1+4)-4/2
所有的运算符都是在两个操作数的中间
后缀表达式 (逆波兰式)
所有的运算符都是在要运算的操作数的后面出现
例子:
1)
9+(3-1)*3+10/2
==>
9 3 1 - 3 * + 10 2 / + (后缀表达式)
2)
2*(3+5)+7/1-4
==>
2 3 5 + * 7 1 / + 4 - (后缀表达式)