数据结构 栈（顺序栈，链式栈，用栈实现计算器）

一、栈的概念

1. 栈是一个特殊的线性表，只能在一端操作：栈顶（top）：允许操作 的一端

                                                                    栈底（bottom）：不允许操作的一端

2. 特点：后进先出

二、顺序栈 

1. 若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize

    若栈存在一个元素，top = 0；空栈的条件：top = -1；

2. 结构体定义：struct sqStack

                        {

                    int top;

                    int *data;

                };

3. （1）栈的初始化（两次malloc分配）

                 (*s) = (Stack *)malloc(sizeof(Stack) * 1);  //分配一个结构体,用于保存信息

                 (*s)->top = -1; //空栈,栈顶指针为-1
                 (*s)->data = (ElemType *)malloc(sizeof(ElemType) * SIZE);   //为栈分配空间

    （2）进栈 s - > data[ s - > top + 1 ] = e;   //先放入内容，再移动top指针
            s - > top++;

    （3）出栈 e = s - > data[ s -> top ];    //先取出内容，再移动top指针
            s - > top - -;

    （4）清空栈 s -> top = -1;

    （5）销毁栈 free( ( *s ) - > data );
               free( *s );
               *s = NULL;

三、链式栈

1. 栈顶放在单链表的头部；

    链栈不需要头结点；

    链栈不存在栈满的情况。

2. 结构体定义：

/*结点信息*/
struct node
{
    ElemType data;  //数据域
    struct node *next;   //指针域
};
typedef struct node Node;

/*栈的信息*/
struct stack
{
    Node *top;  //头指针
    int count;  //结点个数
};

3. 链式栈初始化时只要分配stack空间，即malloc一次，里面节点的空间是放一个分配一个

4. 栈的链式存储 源代码

（1）LinkStack.h

#ifndef _LINKSTACK_H
#define _LINKSTACK_H

#define SUCCESS  10000
#define FAILURE  10001
#define TRUE     10002
#define FALSE    10003

typedef int ElemType;

/*结点信息*/
struct node
{
    ElemType data;  //数据域
    struct node *next;   //指针域
};
typedef struct node Node;

/*栈的信息*/
struct stack
{
    Node *top;  //头指针
    int count;  //结点个数
};
typedef struct stack Stack;

int StackInit(Stack **s);
int StackEmpty(Stack *s);
int push(Stack **s, ElemType e);
int GetTop(Stack *s);
int pop(Stack **s);
int StackClear(Stack **s);
int StackDestroy(Stack **s);

#endif

（2）LinkStack.c

#include "LinkStack.h"
#include <stdlib.h>

/*初始化*/
int StackInit(Stack **s)
{
    if(NULL == s)
    {
        return FAILURE;
    }

    (*s) = (Stack *)malloc(sizeof(Stack) * 1);  //分配stack的空间
    if(NULL == (*s))
    {
        return FAILURE;
    }

    (*s)->top = NULL;
    (*s)->count = 0;

    return SUCCESS;
}

/*判断是否为空*/
int StackEmpty(Stack *s)
{
    if(NULL == s)
    {
        return FAILURE;
    }

    return (s->top == NULL) ? TRUE : FALSE;
}

/*进栈*/
int push(Stack **s, ElemType e)
{
    if(NULL == s || NULL == (*s))
    {
        return FAILURE;
    }

    Node *p = (Node *)malloc(sizeof(Node));
    if(NULL == p)
    {
        return FAILURE;
    }

    p->data = e;
    p->next = (*s)->top;
    (*s)->top = p;
    (*s)->count++;

    return SUCCESS;
}

/*取栈顶元素*/
int GetTop(Stack *s)
{
    if(NULL == s || NULL == s->top)
    {
        return FAILURE;
    }

    return s->top->data;
}

/*出栈*/
int pop(Stack **s)
{
    if(NULL == s || NULL == *s)
    {
        return FAILURE;
    }

    Node *p = (*s)->top;
    ElemType e = p->data;
    (*s)->top = p->next;
    (*s)->count--;
    free(p);

    return e;
}

/*清空*/
int StackClear(Stack **s)
{
    if(NULL == s || NULL == *s)
    {
        return FAILURE;
    }

    Node *p = (*s)->top;

    while(p)
    {
        (*s)->top = p->next;
        free(p);
        p = (*s)->top;
        (*s)->count--;
    }

    return SUCCESS;
}

/*销毁*/
int StackDestroy(Stack **s)
{
    if(NULL == s || NULL == *s)
    {
        return FAILURE;
    }

    free(*s);
    (*s) = NULL;

    return SUCCESS;
}

3.  TestLinkStack.c （main函数）

#include "LinkStack.h"
#include <stdio.h>

int main()
{
    int ret, i;
    Stack *stack = NULL;

    /*初始化*/
    ret = StackInit(&stack);
    if(ret == SUCCESS)
    {
        printf("Init Link Stack Success!\n");
    }
    else
    {
        printf("Init Failure!\n");
    }

    /*判断是否为空*/
    ret = StackEmpty(stack);
    if(ret == TRUE)
    {
        printf("Stack is Empty!\n");
    }
    else if(ret == FALSE)
    {
        printf("Stack is not Empty!\n");
    }
    else
    {
        printf("Stack error!\n");
    }

    /*进栈*/
    for(i = 0; i < 10; i++)
    {
        ret = push(&stack, i);
        if(ret = FAILURE)
        {
            printf("Push %d Failure!\n", i);
        }
        else
        {
            printf("Push %d Success!\n", i);
        }
    }

    /*取栈顶元素*/
    ret = GetTop(stack);
    if(ret == FAILURE)
    {
        printf("Gettop Failure!\n");
    }
    else
    {
        printf("Top is %d\n", ret);
    }

    /*出栈*/
    for(i = 0; i < 5; i++)
    {
        ret = pop(&stack);
        if(ret == FAILURE)
        {
            printf("Pop Failure!\n");
        }
        else
        {
            printf("Pop %d is Success!\n", ret);
        }
    }

    /*清空*/
    ret = StackClear(&stack);
    if(ret == FAILURE)
    {
        printf("Clear Failure!\n");
    }
    else
    {
        printf("Clear Success!\n");
    }

    /*清空后判断是否为空*/
    ret = StackEmpty(stack);
    if(ret == TRUE)
    {
        printf("Stack is Empty!\n");
    }
    else if(ret == FALSE)
    {
        printf("Stack is not Empty!\n");
    }
    else
    {
        printf("Stack error!\n");
    }

    /*销毁*/
    ret = StackDestroy(&stack);
    if(ret == FAILURE)
    {
        printf("Destroy Failure!\n");
    }
    else
    {
        printf("Destroy Success!\n");
    }

    /*销毁后进栈*/
    for(i = 0; i < 2; i++)
    {
        ret = push(&stack, i);
        if(ret = FAILURE)
        {
            printf("Push %d Failure!\n", i);
        }
        else
        {
            printf("Push %d Success!\n", i);
        }
    }

    return 0;
}

四、用栈的链式存储结构实现计算器功能

中缀表达式转后缀表达式情况归纳：

1. 操作数 ：进栈

2. 操作符 ：（1）进栈：空栈

                                       优先级高

                                       栈顶是‘（ ’同时表达式不是‘ ）’

                   （2）出栈并计算：表达式符号的优先级不高于栈顶符号

                                                  表达式为‘ ）’同时栈顶不为‘（ ’

                                                  表达式为‘\0’（即表达式结束）同时栈不为空

                   （3）出栈但不计算：表达式为‘ ）’同时栈顶为‘（ ’

#include "LinkStack.h"
#include <stdio.h>

int Priority(char ch)
{
    switch(ch)
    {
        case '(':
            return 3;
        case '*':
        case '/':
            return 2;
        case '+':
        case '-':
            return 1;
        default:
            return 0;
    }
}

int main()
{
    Stack *s_opt, *s_num;
    char opt[1024] = {0};   //存放表达式
    int i = 0, num1 = 0, num2 = 0, temp = 0;

    if(StackInit(&s_opt) != SUCCESS || StackInit(&s_num) != SUCCESS) //栈的初始化
    {
        printf("Init Failure!\n");
    }

    printf("Please input:\n");
    scanf("%s", opt);

    while(opt[i] != '\0' || StackEmpty(s_opt) != TRUE) //表达式没结束或操作符栈不为空
    {
        if(opt[i] >= '0' && opt[i] <= '9')
        {
            temp = temp * 10 + opt[i] - '0';
            i++;
            if(opt[i] > '9' || opt[i] < '0') //操作符
            {
                push(&s_num, temp);
                temp = 0;
            }
        }
        else //操作符
        {
            if(opt[i] == ')' && GetTop(s_opt) == '(') //出栈不计算
            {
                pop(&s_opt);
                i++;
                continue;
            }

            if(StackEmpty(s_opt) == TRUE ||
                    (Priority(opt[i]) > Priority(GetTop(s_opt)))
                     || (GetTop(s_opt)) == '(' && opt[i] != ')') //出栈计算
                    {
                         push(&s_opt, opt[i]);
                         i++;
                         continue;
                    }

            if((opt[i] == '\0' && StackEmpty(s_opt) != TRUE)
                    || (opt[i] == ')' && GetTop(s_opt) != '(') ||
                        (Priority(opt[i]) <= Priority(GetTop(s_opt)))) //全部进栈完成开始计算
            {
                switch(pop(&s_opt))
                {
                    case '+':
                        num1 = pop(&s_num);
                        num2 = pop(&s_num);
                        push(&s_num, (num1 + num2));
                        break;
                    case '-':
                        num1 = pop(&s_num);
                        num2 = pop(&s_num);
                        push(&s_num, (num2 - num1));
                        break;
                    case '*':
                        num1 = pop(&s_num);
                        num2 = pop(&s_num);
                        push(&s_num, (num1 * num2));
                        break;
                    case '/':
                        num1 = pop(&s_num);
                        num2 = pop(&s_num);
                        push(&s_num, (num2 / num1));
                        break;
                }
            }
        }
    }

    printf("%d\n", GetTop(s_num));
    return 0;
}