数据结构-栈

栈 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 -           (后缀表达式)