栈有啥用

为什么需要栈

因为要模拟回溯。

递归

递归从形式上来看，是函数自己调用自己。从具体过程来看，是一个回溯的过程。

吐槽

很多技术书上真是惜字如金，微言大义呀，难道是不写的形式化一点就显得自己不专业？您确实挺专业的，但我觉得还有一个专业是把事情说明白， 多写点人话。

实现栈（c）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdlib.h>
#include <stdio.h>

int const STACK_INIT_SIZE = 100;
int const STACKINCREMENT = 10;

typedef int Status;

typedef struct Stack {
    void **base;
    void **top;
    int stackSize;
} Stack;

/**
 * 初始化
 * @return
 */
Status init_stack(Stack *);

/**
 * 获取栈顶元素
 * @return
 */
Status get_top(Stack, void **);

/**
 * 压栈
 * @return
 */
Status push(Stack *, void *);

/**
 * 弹栈
 * @return
 */
Status pop(Stack *, void **);

/**
 * 是否空栈
 * @return
 */
Status is_StackEmpty(Stack);

// code
Status init_stack(Stack *S) {
    (*S).base = (void **) malloc(STACK_INIT_SIZE * sizeof(void *));

    if (!(*S).base)
        exit(-1);

    (*S).top = (*S).base;
    (*S).stackSize = STACK_INIT_SIZE;

    return 0;
}

Status get_top(Stack S, void **e) {
    if (S.top == S.base) {
        return -1;
    }

    *e = *(S.top - 1);
    return 0;
}

Status push(Stack *S, void *e) {
    // 如果栈满，就开辟新空间
    if ((*S).top - (*S).base >= (*S).stackSize) {
        (*S).base = (void **) realloc((*S).base, ((*S).stackSize + STACKINCREMENT) * sizeof(void *));

        if (!(*S).base) {
            exit(-1);
        }

        (*S).top = (*S).base + (*S).stackSize;
        (*S).stackSize = (*S).stackSize + STACKINCREMENT;
    }

    *(S->top) = e;
    (S->top)++;

    return 0;
}

//
Status pop(Stack *S, void**e)
{
    if ((*S).top == (*S).base)
        return -1;

    (*S).top--;
    *e = *((*S).top);

    return 0;
};

Status is_StackEmpty(Stack S)
{
    if(S.top==S.base)
        return 1;
    else
        return -1;
}

遍历二叉树

二叉树的遍历也是一个回溯的过程，直接用递归来实现二叉树遍历是容易理解的，也可以用栈来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Status inorder_travese(BinaryTree T)
{
    Stack S;
    BinaryTree root = T;
    BinaryTree node;

    init_stack(&S);
    node = (BinaryTree)malloc(sizeof(BinaryTreeNode));

    while (root || !is_StackEmpty(S))
    {
        if (root)
        {
            push(&S, root);   // 根节点进栈
            root = root->Lchild; // 访问左子树
        }
        else
        {
            pop(&S, &node);     // 退栈
            printf(node->data); // 访问根节点
            root = node->Rchild;   // 访问右子树
        }
    }

    return 0;
}