04_栈

数据结构和算法

4.1 栈的定义

• defs：栈（Stack）是一个后进先出（Last in first out，LIFO）的线性表，它要求只在表尾进行删除和插入操作。
• tips：栈其实就是一个特殊的线性表（顺序表、链表），但是它在操作上有一些特殊要求和限制：
  
  • 栈的元素必须“后进先出”
  • 栈的操作只能在这个线性表的表尾进行
  • 对于栈来说，这个表尾称为栈的栈顶（top），相应的表头称为栈底（bottom）

4.2 栈的插入和删除操作

• 栈的插入操作（Push），叫做进栈，也称为压栈，入栈。
• 栈的删除操作（Pop），叫做出栈，也称为弹栈。

4.3 栈的顺序存储结构

• 因为栈的本质是一个线性表，线性表有两种存储形式，那么栈也有分为栈的顺序存储结构和栈的链式存储结构
• 最开始的栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。
• 然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。
• 数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。

typedef struct 
{
    ElemType *base; //指向栈底的指针变量
    ElemType *top; //指向栈顶的指针变量
    int stackSize; //栈的当前可用最大容量
}sqStack;

4.3.1 创建一个栈

#define STACK_INIT_SIZE 100
initStack(sqStack *s)
{
    s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if ( !s->base )
        exit(0);
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}

4.3.2 入栈操作

• 入栈操作又称压栈操作，就是向栈中存放数据
• 入栈操作要在栈顶进行，每次向栈中压入一个数据，top指针就要+1，直到栈满为止

#define STACKINCREMENT 10
Push(sqStack *s, ElemType e)
{
    //如果栈满，追加空间
    if ( s->top - s->base >= stackSize )
    {
        s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
        if ( !s->base )
            exit(0);
        s->top = s->base + s->stackSize; //设置栈顶
        s->stackSize = s->stackSize + STACKINCREMENT; //设置栈的最大容量
    }
    *(s->top) = e;
    s->top++;
}

4.3.3 出栈操作

• 出栈操作就是在栈顶取出数据，栈顶指针随之下移的操作
• 每当从栈内弹出一个数据，栈的当前容量就-1

Pop(sqStack *s, ElemType *e)
{
    if ( s->top == s->base )
        return;
    *e = *--(s->top);
}

4.3.4 清空一个栈

• 所谓的清空一个栈，就是将栈中的元素全部作废，但栈本身的物理空间并不发生改变（不是销毁）

ClearStack(sqStack *s)
{
    s->top = s->base;
}

4.3.5 销毁一个栈

• 销毁一个栈和清空一个栈不同，销毁一个栈是要释放掉该栈所占据的物理内存空间

DestoryStack(sqStack *s)
{
    int i, len;
    len = s->stackSize;
    for ( i=0; i < len; i++ )
    {
        free( s->base );
        s->base++;
    }
    s->base = s->top =  NULL;
    s->stackSize = 0;
}

4.3.6 计算栈的当前容量

• 计算栈的当前容量也就是计算栈中元素的个数，因此只要返回s.top-s.base即可
• 栈的最大容量是指该栈占据内存空间的大小，与当前容量不是一个概念

int Stacklen(sqStack s)
{
    return(s.top - s.base);
}

4.3.7 实例分析

例利用栈的数据结构特点，将二进制转换为十进制数。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define STACK_INIT_SIZE 20
#define STACKINCREMENT    10
typedef char ElemType;
typedef struct 
{
    ElemType *base;
    ElemType *top;
    int stackSize;
}sqStack;
void InitStack(sqStack *s)
{
    s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if ( ! s->base )
        exit(0);
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}
void Push(sqStack *s, ElemType e)
{
    if( s->top - s->base >= s->stackSize )
    {
        s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
        if ( ! s->base )
            exit(0);
    }
    *(s->top) = e;
    s->top++;
}
void Pop(sqStack *s, ElemType *e)
{
    if ( s->top == s->base )
        return;
    *e = *--(s->top);
}
int StackLen(sqStack s)
{
    return (s.top - s.base);
}
int main()
{
    ElemType c;
    sqStack s;
    int len, i, sum = 0;
    InitStack(&s);
    printf("请输入二进制数，输入#符号表示结束！\n");
    scanf("%c", &c);
    while ( c != '#' )
    {
        Push(&s, c);
        scanf("%c", &c);
    }
    getchar(); //把'\n'从缓冲区去掉
    len = StackLen(s);
    printf("栈的当前容量是：%d\n", len);
    for (i=0; i<len; i++)
    {
        Pop(&s, &c);
        sum = sum + (c-48) * pow(2, i);
    }
    printf("转换为十进制数是：%d\n", sum);
    return 0;
}

例利用栈的数据结构特点，将二进制转换为八进制数。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define STACK_INIT_SIZE 20
#define STACKINCREMENT    10
typedef char ElemType;
typedef struct 
{
    ElemType *base;
    ElemType *top;
    int stackSize;
}sqStack;
void InitStack(sqStack *s)
{
    s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if ( ! s->base )
        exit(0);
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}
void Push(sqStack *s, ElemType e)
{
    if( s->top - s->base >= s->stackSize )
    {
        s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
        if ( ! s->base )
            exit(0);
    }
    *(s->top) = e;
    s->top++;
}
void Pop(sqStack *s, ElemType *e)
{
    if ( s->top == s->base )
        return;
    *e = *--(s->top);
}
int StackLen(sqStack s)
{
    return (s.top - s.base);
}
int main()
{
    ElemType c,e;
    sqStack s, p;
    int len, len2, i, sum = 0;
    InitStack(&s);
    InitStack(&p);
    printf("请输入二进制数，输入#符号表示结束！\n");
    scanf("%c", &c);
    while ( c != '#' )
    {
        Push(&s, c);
        scanf("%c", &c);
    }
    getchar(); //把'\n'从缓冲区去掉
    len = StackLen(s);
    printf("栈的当前容量是：%d\n", len);
    int count = 0;
    int num = len/3;
    int j = 0;
    for (i=0; i<len; i++)
    {
        j = i%3;
        int l = len%3;
        if ( num > 0 )
        {   
            Pop(&s, &c);
            sum = sum + (c-48) * pow(2, j);
            count++;
            if ( count == 3 )
            {
                num--;
                Push(&p, sum);
                sum = 0;
                count = 0;
            }
        }
        else 
        { 
            Pop(&s, &c);
            sum = sum + (c-48) * pow(2, j);
            count++; 
            if ( count == l )
            {
                Push(&p, sum);
            }
        }
    }
    len2 = StackLen(p);
    printf("八进制栈的当前容量是：%d\n", len2);     
    printf("转换为八进制数是：");
    int k;
    for ( k=0; k<len2; k++ )    
    {
        Pop(&p, &sum);
        printf("%d", sum);
    }
    printf("\n");
    return 0;
}

4.4 栈的链式存储结构

• 栈的链式存储结构，简称栈链。
• 栈因为只是栈顶用来做插入和删除操作，所以比较好的方法就是将栈顶放在单链表的头部，栈顶指针和单链表的头指针合二为一。

typedef struct StackNode
{
    ElemType data;//存放栈的数据
    struct StackNode *next;
} StackNode, *LinkStackPtr;
typedef struct LinkStack
{
    LinkStackPtr top; //top指针
    int count; //栈元素计数器
};

4.4.1 进栈操作

• 对于栈链的Push操作，假设元素值为e的新结点是s，top为栈顶指针

Status Push(LinkStack *s, ElemType e)
{
    LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
    p->data = e;
    p->next = s->top;
    s->top = p;
    s->count++;
    return OK;
}

4.4.2 出栈操作

• 假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可

Status Pop(LinkStack *s, ElemType *e)
{
    LinkStackPtr p;
    if( StackEmpty(*s) ) //判断是否为空栈
        return ERROR;
    *e = s->top->data;
    p = s->top;
    s->top = s->top->next;
    free(p);
    s->count--;
    return OK;
}

4.4.3 逆波兰表达式

• 一种不需要括号的后缀表达式，通常把它称为逆波兰表达式（RPN）

例 (1-2) * (4+5) = -9

• 数字 1 和 2 进栈，遇到减号运算符则弹出两个元素进行运算并把结果入栈

• 4 和 5 入栈，遇到加号运算符，4 和 5 弹出栈，相加后将结果 9 入栈

• 然后又遇到乘法运算符，将 9 和 -1 弹出栈进行乘法计算，此时栈空并无数据压栈，-9 为最终运算结果

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define STACK_INIT_SIZE 30
#define STACKINCREMENT 10
#define MAXBUFFER 20
typedef double ElemType;
typedef struct
{
    ElemType *base;
    ElemType *top;
    int stackSize;
} sqStack;
void InitStack(sqStack *s)
{
    s->top = s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if ( !s->base )
    {
        exit(0);
    }
    s->base = s->top;
    s->stackSize = STACK_INIT_SIZE;
}
void Push(sqStack *s, ElemType e)
{
    if ( s->top - s->base >= s->stackSize )
    {
        s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
        if ( !s->base )
        {
            exit(0);
        }
    }
    *(s->top) = e;
    s->top++;
}
void Pop(sqStack *s, ElemType *e)
{
    if( s->base == s->top )
    {
        return;
    }
    *e = *--(s->top);
}
int StackLen(sqStack s)
{
    return (s.top - s.base);
}
 int main()
 {
    sqStack s;
    char c;
    double d, e;
    int i = 0;
    char str[MAXBUFFER];
    InitStack( &s );
    printf("请按逆波兰表达式输入待计算数据，数据与运算符之间用空格隔开，以#作为结束标志： \n");
    scanf("%c", &c);
    while ( c != '#' )
    {
        while ( isdigit(c) || c == '.' ) //用于过滤数字
        {
            str[i++] = c;
            str[i] = '\0';
            if ( i >= 10 )
            {
                printf("出错：输入的单个数据过大！\n");
                return -1;
            }
            scanf("%c", &c);
            if ( c == ' ')
            {
                d = atof(str); //将字符串转换为浮点数
                Push(&s, d);
                i = 0;
                break;
            }       
        }
        switch( c )
        {
            case '+':
                Pop(&s, &e);
                Pop(&s, &d);
                Push(&s, d+e);
                break;
            case '-':
                Pop(&s, &e);
                Pop(&s, &d);
                Push(&s, d-e);
                break;
            case '*':
                Pop(&s, &e);
                Pop(&s, &d);
                Push(&s, d*e);
                break;
            case '/':
                Pop(&s, &e);
                Pop(&s, &d);
                if ( e != 0)
                {
                    Push(&s, d/e);
                }
                else
                {
                    printf("出错：除数为零！\n");
                    return -1;
                }
                break;
        }
        scanf("%c", &c);
    }
    Pop(&s, &d);
    printf("\n最终的计算结果为： %f\n", d);
    return 0;
 }

4.4.4 中缀表达式转换为后缀表达式

例 1 + (2-3) * 4 + 10/5 = -1

• 首先遇到第一个输入是数字1，数字在后缀表达式中都是直接输出，接着是符号 ‘+’，入栈
• 第三个字符是‘(’，依然是符号，入栈，接着是数字2，输出，然后是符号‘-’，入栈
• 接下来是数字3，输出，紧跟着是‘)’，此时，需要去匹配栈例的‘(’，然后再匹配前将栈顶数据依次出栈
• 紧接着是符号‘*’，直接入栈
• 遇到数字4，输出，之后是符号‘+’，此时栈顶元素是符号‘*’，按照先乘除后加减，此时栈顶的乘号优先级比即将入栈的加号大，所以出栈
• 栈中的第二个元素是加号，按照先来后到的原则，栈里的加号出栈（同理如果栈里还有其他的操作符，也是出栈）
• 然后是数字10，输出，最后是符号‘/’，进栈

• 最后一个数字5，输出，所有的输入处理完毕，但是栈中仍有数据，所以将栈中符号依次出栈

• 总结规则：从左到右遍历中缀表达式的每个数字和符号，若是数字则直接输出，若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号，则栈顶元素依次出栈并输出，直到遇到左括号或栈空才将后来的符号入栈。

#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef char ElemType;
typedef struct 
{
    ElemType *base;
    ElemType *top;
    int stackSize;
} sqStack;
void InitStack(sqStack *s)
{
    s->top = s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
    if( !s->base )
        exit(0);
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}
void Push(sqStack *s, ElemType e)
{
    if( s->top - s->base >= STACK_INIT_SIZE )
    {
        s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
        if( !s->base )
            exit(0);
    }
    *(s->top) = e;
    s->top++;
}
void Pop(sqStack *s, ElemType *e)
{
    if( s->base == s->top )
        return;
    *e = *--(s->top);
}
int StackLen(sqStack s)
{
    return (s.top - s.base);
}
int main()
{
    sqStack s;
    char c, e;
    InitStack( &s );
    printf("请输入中缀表达式，以#作为结束标志： ");
    scanf("%c", &c);
    while( c != '#' )
    {
        while( c >= '0' && c <= '9' )
        {
            printf("%c", c);
            scanf("%c", &c);
            if( c < '0' || c > '9')
            {
                printf(" ");
            }
        }
        if( ')' == c )
        {
            Pop(&s, &e);
            while( '(' != e )
            {
                printf("%c ", e);
                Pop(&s, &e);
            }
        } 
        else if( '+' == c || '-' == c )
        {
            if ( !StackLen(s) )
            {
                Push(&s, c);
            }
            else 
            {
                do
                {
                    Pop(&s, &e);
                    if( '(' == e )
                    {
                        Push(&s, e);
                    }
                    else
                    {
                        printf("%c ", e);
                    }
                }while( StackLen(s) && '(' !=e );
                Push(&s, c);
            }
        }
        else if( '(' ==c || '*' == c || '/' == c )
        {
            Push(&s, c);
        }
        else if( '#' == c )
        {
            break;
        }
        else
        {
            printf("\n出错：输入格式错误！\n");
            return -1;
        }
        scanf("%c", &c);
    } 
    while( StackLen(s) )
    {
        Pop(&s, &e);
        printf("%c ", e);
    }
    return 0;
}

4.4.5 输入中缀表达式计算出结果

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define STACK_INIT_SIZE 30
#define STACKINCREMENT 10
#define MAXBUFFER 20
typedef double ElemTypes;
typedef char ElemType;
typedef struct
{
    ElemType *base;
    ElemType *top;
    int stackSize;
} sqStack;
typedef struct
{
    ElemTypes *base;
    ElemTypes *top;
    int stackSize;
} sqStacks;
void InitStack(sqStack *s)
{
    s->top = s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
//  memset(s->top, 0, STACK_INIT_SIZE * sizeof(ElemType));
    if ( !s->base )
    {
        exit(0);
    }
    s->base = s->top;
    s->stackSize = STACK_INIT_SIZE;
}
void InitStacks(sqStacks *s)
{
    s->top = s->base = (ElemTypes *)malloc(STACK_INIT_SIZE * sizeof(ElemTypes));
//  memset(s->top, 0, STACK_INIT_SIZE * sizeof(ElemTypes));
    if ( !s->base )
    {
        exit(0);
    }
    s->base = s->top;
    s->stackSize = STACK_INIT_SIZE;
}
void Push(sqStack *s, ElemType e)
{ 
    if ( s->top - s->base >= s->stackSize )
    {
        s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
        if ( !s->base )
        {
            exit(0);
        }
    }
    *(s->top) = e;
    s->top++;
}
void Pushs(sqStacks *s, ElemTypes e)
{ 
    if ( s->top - s->base >= s->stackSize )
    {
        s->base = (ElemTypes *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemTypes));
        if ( !s->base )
        {
            exit(0);
        }
    }
    *(s->top) = e;
    s->top++;
}
void Pop(sqStack *s, ElemType *e)
{
    if( s->base == s->top )
    {
        return;
    }
    *e = *--(s->top);
}
void Popp(sqStack *s, ElemType *e)
{
    if( s->base == s->top )
    {
        return;
    }
    *e = *(s->base);
    s->base++;
}
void Pops(sqStacks *s, ElemTypes *e)
{
    if( s->base == s->top )
    {
        return;
    }
    *e = *--(s->top);
}
int StackLen(sqStack s)
{
    return (s.top - s.base);
}
int StackLens(sqStacks s)
{
    return (s.top - s.base);
}
int main()
{
    sqStack s, p;
    sqStacks q;
    char c, e;
    double d, f;
    char str[MAXBUFFER];
    InitStack( &s );
    InitStack( &p );
    InitStacks( &q );
    int i = 0;
    printf("请输入中缀表达式，以#作为结束标志： ");
    scanf("%c", &c);
    while( c != '#' )
    {
        while( c >= '0' && c <= '9' )
        {
            printf("%c", c);
            Push(&p, c);
            scanf("%c", &c);
            if( c < '0' || c > '9')
            {
                printf(" ");
                Push(&p, ' ');
            }
        }
        if( ')' == c )
        {
            Pop(&s, &e);
            while( '(' != e )
            {
                printf("%c ", e);
                Push(&p, e);
                Push(&p, ' ');
                Pop(&s, &e);
            }
        } 
        else if( '+' == c || '-' == c )
        {
            if ( !StackLen(s) )
            {
                Push(&s, c);
            }
            else 
            {
                do
                {
                    Pop(&s, &e);
                    if( '(' == e )
                    {
                        Push(&s, e);
                    }
                    else
                    {
                        printf("%c ", e);
                        Push(&p, e);
                        Push(&p, ' ');
                    }
                }while( StackLen(s) && '(' !=e );
                Push(&s, c);
            }
        }
        else if( '(' ==c || '*' == c || '/' == c )
        {
            Push(&s, c);
        }
        else if( '#' == c )
        {
            break;
        }
        else
        {
            printf("\n出错：输入格式错误！\n");
            return -1;
        }
        scanf("%c", &c);
    } 
    while( StackLen(s) )
    {
        Pop(&s, &e);
        printf("%c ", e);
        Push(&p, e);
        Push(&p, ' ');
    }
    Popp(&p, &c);
    int flag = 0;
    while ( StackLen(p) )
    {
        while ( c >= '0' && c <= '9' ) 
        {
            str[i++] = c;
            Popp(&p, &c);
            flag = 1;
        }
        if (flag)
        {
            str[i] = '\0';
            d = atof(str);
            Pushs(&q, d);
//          printf("d=%f", d);
            i = 0;
            flag = 0;
        }
        switch( c )
        {
            case '+':
                Pops(&q, &f);
                Pops(&q, &d);
                Pushs(&q, d+f);
//              printf("d+f=%f ", d+f);
                break;
            case '-':
                Pops(&q, &f);
                Pops(&q, &d);
                Pushs(&q, d-f);
//              printf("d-f=%f ", d-f);
                break;
            case '*':
                Pops(&q, &f);
                Pops(&q, &d);
                Pushs(&q, d*f);
//              printf("d*f=%f ", d*f);
                break;
            case '/':
                Pops(&q, &f);
                Pops(&q, &d);
                if ( f != 0 )
                {
                    Pushs(&q, d/f);
//                  printf("d/f=%f ", d/f);
                }
                else
                {
                    printf("出错：除数为零！\n");
                    return -1;
                }
                break;
        }
        Popp(&p, &c);
    } 
    Pops(&q, &d);
    printf("\n最终的计算结果为： %f\n", d);
    return 0;
 }