栈的定义

栈是一种只能后进先出（Last In First Out）的数据结构，表现为只能在线性表的尾部进行插入和删除操作。其中，把数据插入栈称为*压栈（Push），把数据从栈中取出来称为*弹栈（Pop）。栈这种数据结构的应用是非常普遍的，比如手机APP的多任务界面，在切换到新页面里，旧页面的内容往往会被压入栈，而点击返回键时，就是把栈里存储的内容再弹出来。
我们把允许插入和弹出数据的一端称为*栈顶（Top），另一端则称为*栈底（Base），不含任何数据的栈称为空栈（注意这个空栈的含义与arm体系结构中的空栈不同）。由于压栈和弹栈只能在栈顶进行，所以，栈底是固定的而栈顶是浮动的。
Alt text

进栈和出栈的形式

考虑有三个整数数据1、2、3依次入栈，会有哪些出栈的次序？

  • 第一种:1进2进3进，3出2出1出，这是最好理解的一种，出栈顺序是3、2、1；
  • 第二种：1进，1出，2进，2出，3进，3出，出栈顺序是1、2、3；
  • 第三种：1进，2进，2出，1出，3进，3出，出栈顺序是2、1、3；
  • 第四种：1进，1出，2进，3进，3出，2出，出栈顺序是1、3、2；
  • 第五种：1进，2进，2出，3进，3出，1出，出栈顺序是2、3、1；

有没有可能是3、1、2这样的出栈顺序呢？答案是肯定不会，因为3先出栈，意味着3曾经进栈，既然3已经进栈，则1和2肯定已经进栈了，这时，2一定在1的上面，所以只能先出2再出1，最终的出栈只能是3、2、1，不然不满足1、2、3依次进栈的要求。

栈的顺序存储结构及实现

栈作为线性表的一种，可以用数组的顺序存储形式或是链表的链式存储形式来实现。

顺序存储结构一

#define MAXSIZE 100
typedef int type_t;            /*栈元素类型*/
struct stack
{
    type_t data[MAXSIZE];/*栈的顺序存储空间*/
    int index;    /*记录栈中元素的个数，同时反映栈顶位置，栈顶位置为index - 1*/
};
typedef struct stack Stack;    /*栈的数据结构*/

顺序存储结构二

#define MAXSIZE 100
typedef int type_t;            /*栈元素类型*/
struct stack
{
    type_t *data;/*栈的顺序存储空间，通过堆内存进行分配*/
    int index;    /*记录栈中元素的个数，同时反映栈顶位置，栈顶位置为index - 1*/
};
typedef struct stack Stack;    /*栈的数据结构*/

栈的操作接口及参考实现

/*定义错误号*/
#define ERROR     -1        
#define OK        0

/*创建栈*/
Stack *stack_create()
{
    Stack *stack = (Stack *)malloc(sizeof(Stack));
    assert(stack);
    stack->index = 0;    /*空栈的index为0*/
    return stack;
}

/*销毁栈*/
void stack_destroy(Stack *stack)
{
    stack->index = 0;
    free(stack);
    return;
}

/*压栈操作，成功返回0，失败返回-1*/
int push(Stack *stack, type_t data)
{
    if(stack->index == MAXSIZE)    /*栈满*/
    {
        return ERROR;
    }
    else
    {
        stack->index++;
        stack->data[stack->index - 1] = data;
        return OK;
    }
}

/*弹栈操作，成功返回0，失败返回-1*/
int pop(Stack *stack, type_t *pData)
{
    if(stack->index == 0)
    {
        return ERROR;
    }
    else
    {
        *pData = stack->data[stack->index - 1];
        stack->index--;
        return OK;
    }
}

/*获取栈顶元素*/
int getHead(Stack *s)
{
    if(s != NULL)
        return s->data[s->index - 1];
}

/*栈顶减一*/
int pop_null(Stack *s)
{
    if(s != NULL)
        s->index--;
}

/*获取栈的当前大小*/
int stack_size(Stack *stack)
{
    return stack->count;
}

测试代码

int main()
{
    Stack *s = stack_create();    /*创建栈*/
    int i = 0;
    while(push(s, i) != ERROR)    /*填满栈空间*/
        i++;
    printf("stack size:%d\n", stack_size(s)); /*获取栈的当前大小*/
    while(pop(s, &i) != ERROR)    /*弹出所有元素*/
        printf("%d ", i);
    printf("\n");
    printf("stack size:%d\n", s->index);
    stack_destroy(s);        /*销毁栈*/
    return 0;
}

栈的链式存储结构及实现

栈的链式存储数据结构

typedef int type_t;            /*栈元素类型*/
struct stackNode
{
    type_t data;            /*栈结点的数据域*/
    struct stackNode *next;    /*栈结点的指针域*/
};
struct linkStack
{
    struct stackNode *top;    /*链栈的栈顶*/
    int count;                /*结点个数*/
};
typedef struct stackNode StackNode;
typedef struct linkStack LinkStack;

链栈的操作接口及参考实现

请参考顺序存储结构的栈代码自己实现。

栈的应用示例——四则运算表达式求值

按照“从左到右，先乘除，后加减，有括号先算括号”的规则，对输入的一串四则运算表达式求值，比如输入“9 + (3 - 1) * 3 + 6 / 2”，该如何计算？

本题的在于，从左往右扫描时，乘除在加减后面，却要先运算，加入括号之后，就变得更复杂。
想要对四则运算进行计算，需要借助后缀表示法，也称为逆波兰表示法。后缀表示法是一种不需要括号的表示法，并且所有运算符号都出现在要运算的数字后面。比如，上面这个表达式的后缀表示法为“9 3 1 – 3 * + 6 2 / +”。此处先不急于求解如何推导后缀表达式，先看看如何通过后缀表达式计算整个表达式的值。
后缀表达式求解规则：从左到右遍历表达式的每个数字和字符，遇到是数字就进栈，遇到是符号，就将位于栈顶的两个数字出栈，计算后将结果进栈，一直到获得最终结果。

后缀表达式的求值算法

#define EXPR "931-3*+62/+"    /*待求解的后缀表达式*/
#define YES 1
#define NO 0
static int isOperator(int c)
{
    if(c == '+' || c == '-' || c == '*' || c == '/')
        return YES;
    else
        return NO;
}
static int char2int(int c)
{
    return c - '0';
}
static int calculate(int a, int b, int c)
{
    int ret = 0;
    switch (c)
    {
        case '+':ret = a + b;break;
        case '-':ret = a - b;break;
        case '*':ret = a * b;break;
        case '/':ret = a / b;break;
        default:break;
    }
    return ret;
}
int main()
{
    int tmp1, tmp2, result;
    int i = 0;
    char expr[] = EXPR;
    Stack *s = stack_create();    /*创建栈*/
    while(expr[i] != '\0')
    {
        if(isOperator(expr[i]) == NO)    /*如果不是运算符号，则入栈*/
        {
            push(s, char2int(expr[i]));
            //printf("push:%d\n", char2int(expr[i]));
        }
        else    /*是运算符号，则弹出栈顶两个元素进行计算后再压栈*/
        {
            pop(s, &tmp1);
            //printf("pop:%d\n", tmp1);
            pop(s, &tmp2);
            //printf("pop:%d\n", tmp2);
            push(s, calculate(tmp2, tmp1, expr[i]));
            //printf("push:%d\n", calculate(tmp1, tmp2, expr[i]));
        }
        i++;
    }
    pop(s, &result);    /*计算完毕后，栈里应该只剩下一个最终结果，将该结果弹出即可*/
    printf("result is:%d\n", result);
    stack_destroy(s);        /*销毁栈*/
    return 0;
}

中缀表达式转后缀表达式算法

中缀表达式即我们平时所用的标准四则运算表达式，如“9 + (3 - 1) * 3 + 6 / 2”，因为所有的运算符位于运算数字的中间。现在我们的转换算法还剩的一步就是将中缀表达式转换成后缀表达式。

转换规则：

  1. 从左到右遍历中缀表达式的每个数字和符号
  2. 遇到数字，直接输出
  3. 栈为空时，遇到运算符，直接入栈
  4. 遇到左括号，直接入栈
  5. 遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出的是左括号，左右括号不输出
  6. 遇到其他运算符，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符入栈
  7. 最终将该栈中的元素依次出栈并输出

参考算法：

/*判断是否是数字字符*/
static int isDigital(int c)
{
    if(c >= '0' && c <= '9')
        return YES;
    else
        return NO;
}
/*判断op1的优先级是否大于或等于op2*/
static int higher(int op1, int op2)
{
    if(op1 == '(')
        return NO;
    if(op1 == '*' || op1 == '/')
    {
        return YES;
    }
    else
    {
        if(op2 == '*' || op2 =='/')
            return NO;
        else
            return YES;
    }
}
/*中缀转后缀表达式*/
static void mid2post(char *dst, const char *src)
{
    int i = 0;
    int j = 0;
    Stack *s = stack_create();
    while(src[i] != '\0')
    {
        if(isDigital(src[i]) == YES) /*数字直接输出*/
        {
            dst[j++] = src[i];
        }
        else    /*符号*/
        {
            if(stack_size(s) == 0) /*栈为空，则符号直接入栈*/
            {
                push(s, src[i]);
            }
            else if(src[i] == '(') /*左括号也直接入栈*/
            {
                push(s, src[i]);
            }
            else if(src[i] == ')') /*右括号需要弹出栈顶，直到左括号出栈*/
            {
                while(getHead(s) != '(')
                {
                    dst[j++] = getHead(s);
                    pop_null(s);
                }
                pop_null(s); /*把左括号出栈*/
            }
            else /*比较栈顶元素的符号优先级与当前字符的优先级，如果栈顶优先级高，则栈顶出栈*/
            {
                while(higher(getHead(s), src[i]) == YES && stack_size(s) > 0)
                {
                    dst[j++] = getHead(s);
                    pop_null(s);
                }
                push(s, src[i]); /*将当前元素压栈*/
            }
        }
        i++;
    }
    while(stack_size(s) > 0) /*弹出栈中剩余的数据*/
    {
        dst[j++] = getHead(s);
        pop_null(s);
    }
    stack_destroy(s);
    return;
}

  • 无标签