文章的算法实例阅览需求必定的c根底，在涉及算法之前会先完结栈的次序结构与链式结构，希望能帮到你温习栈的常识

文中几个问题的处理，依靠最根底的数据结构，所以，最好的办法是自己完结一遍最根底的栈结构，最好能调试栈的本质办法

至少保证最基本的栈结构能独立完结，这不是一件很难的事情

假如不动手操作一番，这些算法往往便是过眼烟云尔

我自己不是那类聪明人，能传达的经历便是，正儿八经的自己多敲几遍，然后再以这些根底剖析涉及到的几个算法问题

渐渐的你会习惯，习惯着用计算机的思想办法去考虑遇到的问题，但是又会在计算机思想的根底上，发挥咱们人脑特有的笼统演化跟想象力，最终得出处理问题的方案

栈的次序结构完结

// 初始化次序结构SeqStack
bool initSeqStack(struct SeqStack *sStack) {
    sStack->top = -1;
    return true;
}
bool seqStackEmpty(struct SeqStack *sStack) {
  return sStack->top <= -1;
}
void configSeqStackData(struct SeqStack *sStack, int *array, int n) {
    if (n > INIT_SEQSTACK_CAPACITY) {
        n = INIT_SEQSTACK_CAPACITY;
    }
    for (int i = 0; i < n; i++) {
        union SeqStackNode mStackNode;
        mStackNode.data = array[i];
        sStack->nodes[++(sStack->top)] = mStackNode;
    }
}
void configSeqStackCh(struct SeqStack *sStack, char *array, int n) {
    if (n > INIT_SEQSTACK_CAPACITY) {
        n = INIT_SEQSTACK_CAPACITY;
    }
    for (int i = 0; i < n; i++) {
        union SeqStackNode mStackNode;
        mStackNode.ch = array[i];
        sStack->nodes[++(sStack->top)] = mStackNode;
    }
}
// 栈顶元素
union SeqStackNode *topSeqStack(struct SeqStack *sStack) {
    if (sStack->top < 0) {
        return NULL;
    }
    return &sStack->nodes[sStack->top];
}
// 栈长度
int lengthSeqStack(struct SeqStack *sStack) {
    return sStack->top + 1;
}
// 压栈
bool pushSeqStack(struct SeqStack *sStack, union SeqStackNode *node) {
    if (sStack->top >= INIT_SEQSTACK_CAPACITY - 1) {
        printf("栈已满，请pop栈.....\n");
        return false;
    }
    sStack->top = sStack->top + 1;
    sStack->nodes[sStack->top] = *node;
    return true;
}
// 出栈
union SeqStackNode *popSeqStack(struct SeqStack *sStack) {
    if (sStack->top < 0) {
        return NULL;
    }
    sStack->top = sStack->top - 1;
    return &sStack->nodes[sStack->top + 1];
}
// 遍历
void traverseSeqStack1(struct SeqStack *sStack) {
    if (sStack->top < 0) {
        return;
    }
    printf("\n========== stack - s ========== \n");
    for (int i = 0; i < sStack->top + 1; i++) {
        printf(" <<< %i", sStack->nodes[i].data);
    }
    printf("\n========== stack - e ========== \n");
}
void traverseSeqStack2(struct SeqStack *sStack) {
    if (sStack->top < 0) {
        return;
    }
    printf("\n========== stack - s ========== \n");
    for (int i = 0; i < sStack->top + 1; i++) {
        printf(" <<< %c)", sStack->nodes[i].ch);
    }
    printf("\n========== stack - e ========== \n");
}
// 测验 次序结构 stack 基本功能
void testSeqStack(void) {
    struct SeqStack sStack;
    initSeqStack(&sStack);
    int array[10] = {1, 2, 3, 5, 7, 9, 6, 4, 2, 0};
    configSeqStackData(&sStack, array, 10);
    union SeqStackNode node1;
    node1.data = 30;
    printf("--- 压栈: %i---\n", node1.data);
    pushSeqStack(&sStack, &node1);
    traverseSeqStack1(&sStack);
    printf("seq stack 长度: %i\n", lengthSeqStack(&sStack));
    printf("--- 出栈---\n");
    union SeqStackNode *node2 = popSeqStack(&sStack);
    printf("出栈节点 : %i\n", node2->data);
    traverseSeqStack1(&sStack);
    printf("seq stack 长度: %i\n", lengthSeqStack(&sStack));
}

    --- 压栈: 30---
    ========== stack - s ========== 
     <<< 1 <<< 2 <<< 3 <<< 5 <<< 7 <<< 9 <<< 6 <<< 4 <<< 2 <<< 0 <<< 30
    ========== stack - e ========== 
    seq stack 长度: 11
    --- 出栈---
    出栈节点 : 30
    ========== stack - s ========== 
     <<< 1 <<< 2 <<< 3 <<< 5 <<< 7 <<< 9 <<< 6 <<< 4 <<< 2 <<< 0
    ========== stack - e ========== 
    --- 出栈---
    出栈节点 : 0
    ========== stack - s ========== 
     <<< 1 <<< 2 <<< 3 <<< 5 <<< 7 <<< 9 <<< 6 <<< 4 <<< 2
    ========== stack - e ========== 
    seq stack 长度: 9

栈的链式结构完结

// 初始化 链式结构SeqStack
bool initLinkStack(struct LinkStack *lStack) {
    lStack->count = 0;
    lStack->top = NULL; // top 指向头节点
    return NULL;
}
void configLinkStackData(struct LinkStack *lStack, int *array, int n) {
    for (int i = 0; i < n; i++) {
        union SeqStackNode mStackNode;
        mStackNode.data = array[i];
        struct LinkStackNode *lStackNode = (struct LinkStackNode *)malloc(sizeof(struct LinkStackNode *));
        lStackNode->item = mStackNode;
        lStackNode->next = NULL;
        if (lStack->top == NULL) {
            lStack->top = lStackNode;
        } else {
            lStackNode->next = lStack->top;
            lStack->top = lStackNode;
        }
        lStack->count = lStack->count + 1;
    }
}
void configLinkStackCh(struct LinkStack *lStack, char *array, int n) {
    for (int i = 0; i < n; i++) {
        union SeqStackNode mStackNode;
        mStackNode.data = array[i];
        struct LinkStackNode *lStackNode = (struct LinkStackNode *)malloc(sizeof(struct LinkStackNode *));
        lStackNode->item = mStackNode;
        lStackNode->next = NULL;
        if (lStack->top == NULL) {
            lStack->top = lStackNode;
        } else {
            lStackNode->next = lStack->top;
            lStack->top = lStackNode;
        }
        lStack->count = lStack->count + 1;
    }
}
// 栈顶元素
union SeqStackNode topLinkStack(struct LinkStack *lStack) {
    return lStack->top->item;
}
// 栈长度
int lengthLinkStack(struct LinkStack *lStack) {
    return lStack->count;
}
// 压栈
bool pushLinkStack(struct LinkStack *lStack, union SeqStackNode *item) {
    struct LinkStackNode *lStackNode = (struct LinkStackNode *)malloc(sizeof(struct LinkStackNode *));
    lStackNode->item = *item;
    lStackNode->next = NULL;
    if (lStack->top == NULL) {
        lStack->top = lStackNode;
    } else {
        lStackNode->next = lStack->top;
        lStack->top = lStackNode;
    }
    lStack->count = lStack->count + 1;
    return true;
}
// 出栈
union SeqStackNode popLinkStack(struct LinkStack *lStack) {
    struct LinkStackNode *q = lStack->top;
    lStack->top = q->next;
    lStack->count = lStack->count - 1;
    union SeqStackNode mStackNode = q->item;
    free(q);
    return mStackNode;
}
// 遍历
void traverseLinkStack1(struct LinkStack *lStack) {
    struct LinkStackNode *q = lStack->top;
    printf("\n========== link stack - s ========== \n");
    while (q != NULL) {
        printf(" <<< %i", q->item.data);
        q = q->next;
    }
    printf("\n========== link stack - e ========== \n");
}
void traverseLinkStack2(struct LinkStack *lStack) {
    struct LinkStackNode *q = lStack->top;
    printf("\n========== link stack - s ========== \n");
    while (q != NULL) {
        printf(" <<< %c", q->item.ch);
        q = q->next;
    }
    printf("\n========== link stack - e ========== \n");
}
void testLinkStack(void) {
    struct LinkStack lStack;
    initLinkStack(&lStack);
    int array[10] = {1, 2, 3, 5, 7, 9, 6, 4, 2, 0};
    configLinkStackData(&lStack, array, 10);
    union SeqStackNode node1;
    node1.data = 30;
    printf("--- 压栈: %i---\n", node1.data);
    pushLinkStack(&lStack, &node1);
    traverseLinkStack1(&lStack);
    printf("link stack 长度: %i\n", lengthLinkStack(&lStack));
    printf("--- 出栈---\n");
    union SeqStackNode node2 = popLinkStack(&lStack);
    printf("出栈节点 : %i\n", node2.data);
    traverseLinkStack1(&lStack);
    printf("link stack 长度: %i\n", lengthLinkStack(&lStack));
    printf("--- 出栈---\n");
    union SeqStackNode node3 = popLinkStack(&lStack);
    printf("出栈节点 : %i\n", node3.data);
    traverseLinkStack1(&lStack);
    printf("link stack 长度: %i\n", lengthLinkStack(&lStack));
}

    --- 压栈: 30---
    ========== link stack - s ========== 
     <<< 30 <<< 0 <<< 2 <<< 4 <<< 6 <<< 9 <<< 7 <<< 5 <<< 3 <<< 2 <<< 1
    ========== link stack - e ========== 
    link stack 长度: 11
    --- 出栈---
    出栈节点 : 30
    ========== link stack - s ========== 
     <<< 0 <<< 2 <<< 4 <<< 6 <<< 9 <<< 7 <<< 5 <<< 3 <<< 2 <<< 1
    ========== link stack - e ========== 
    link stack 长度: 10
    --- 出栈---
    出栈节点 : 0
    ========== link stack - s ========== 
     <<< 2 <<< 4 <<< 6 <<< 9 <<< 7 <<< 5 <<< 3 <<< 2 <<< 1
    ========== link stack - e ========== 
    link stack 长度: 9

有了两种栈结构的视野，接下来就能够考虑以下几个算法问题了

进制转换问题

由于转换需求重复取模运算，而前面取模的成果往往在低位，后取模的成果在高位，输出按从左到右，由高位到低位，正好能够凭借栈的后进先出来处理这个问题

// 十进制 转 二进制
void decimal_to_binary(int n) {
    struct SeqStack sStack;
    initSeqStack(&sStack);
    while (n > 0) {
        union SeqStackNode node;
        node.ch = n % 2 + 48;
        pushSeqStack(&sStack, &node);
        n = n / 2;
    }
    int len = lengthSeqStack(&sStack);
    union SeqStackNode *node1 = popSeqStack(&sStack);
    printf("二进制:  0b");
    for (int i = 0; i < 32 - len; i++) {
        printf("0");
    }
    while (node1 != NULL) {
        printf("%c", node1->ch);
        node1 = popSeqStack(&sStack);
    }
    printf("\n");
}
// 十进制 转 八进制
void decimal_to_octal(int n) {
    struct SeqStack sStack;
    initSeqStack(&sStack);
    while (n > 0) {
        union SeqStackNode node;
        node.ch = n % 8 + 48;
        pushSeqStack(&sStack, &node);
        n = n / 8;
    }
//    int len = lengthSeqStack(&sStack);
    union SeqStackNode *node1 = popSeqStack(&sStack);
    printf("八进制:  0");
    while (node1 != NULL) {
        printf("%c", node1->ch);
        node1 = popSeqStack(&sStack);
    }
    printf("\n");
}
// 十进制 转 十六进制
void decimal_to_hex(int n) {
    struct SeqStack sStack;
    initSeqStack(&sStack);
    while (n > 0) {
        union SeqStackNode node;
        int h = n % 16;
        if (h > 9) {
            node.ch = h - 9 + 97 - 1;
        } else {
            node.ch = h + 48;
        }
        pushSeqStack(&sStack, &node);
        n = n / 16;
    }
    int len = lengthSeqStack(&sStack);
    union SeqStackNode *node1 = popSeqStack(&sStack);
    printf("十六进制: 0x");
    for (int i = 0; i < 8 - len; i++) {
        printf("0");
    }
    while (node1 != NULL) {
        printf("%c", node1->ch);
        node1 = popSeqStack(&sStack);
    }
    printf("\n");
}

爬楼梯问题

标题

需求爬n阶楼梯到达楼顶
每次能够挑选爬1或2个台阶

有多少种不同的办法能够爬到楼顶?

剖析

在剖析这个问题之前，我想到曾经有人玩过的一种游戏，比这个标题更生动, 就当个小插曲

A跟B两个人比战略,谁能先加到20就赢
回合制，便是每人在每个回合里挑选 +1 仍是 +2，然后对方执行，紧接着又自己…
你有没有碰到过有人玩这个游戏，总赢，百分百，不论先手仍是后手

假如是你，你能保证不论先手仍是后手永久赢对方么?

假如你能必定，那么你必定是个聪明人，而且必定是个善于顶层设计的高手

秘密其实就在于稳赢的一方总是先把自己置于赢的低位上，然后一步步剖析自己前一步应该到达一个什么样的条件

这便是递归思路了

假如我想一向赢下去, 那么就得保证最终加到20的操作必定得是我来执行，不论我是不是先手
为了保证自己最终这一手，就必须设置安全机制，必定是对手出手之后，我出手完结最终一步加到20，稳赢
我就给对方设置一个到20的间隔，这个间隔，对方够不到，但是我能够接着对方的出手，保证我自己能百分百够得到
- 20之前对方出手之后，要保证我到20的间隔要么是1，要么是2，那么对方出手时的间隔就应该是3，这样不论对方怎样出手，一向我赢
- 为了让对方坚持这个3的间隔，前一步我也得赢17
- 对方到17的间隔就得是3，我得赢14
最终我只要抢占 2 5 8 11 14 17，就能保证从开始一向赢到最终

当然假如对方熟知这个规则，对方先手，就稳赢

忽然想到了这个例子，就当是活跃一下思路了，看看对剖析此问题有没有帮助

回到爬楼梯问题

要么挑选爬一阶，要么挑选爬两阶
最终要么爬一阶到顶，要么爬两阶到顶
爬一阶到顶的话，前面的n-1阶就有f(n-1)种办法
爬两阶到顶的话，前面的n-2阶就有f(n-2)种办法

爬楼梯算法完结

n == 1, f(n) = 1
n == 2, f(n) = 2
n == 3, f(n) = 3 [f(3) = f(1) + f(2)]

由于另一篇博客现已专门针对fibonacci的递归以及优化做了详细阐述，此处就不再赘述了，具体完结及优化 – 从斐波那契 – 谈及动态规划 – 优化

每日气温问题

标题

根据每日气温表，从头生成一个列表，对应方位的输入为需求等候几天温度才会超越该方位对应的温度
例如给定温度列表 [33, 34, 28, 25, 15, 36, 32, 22, 10, 37]

输出列表 [1, 4, 3, 2, 1, 4, 3, 2, 1, 0]

剖析一

咱们跳过不需求思考就能写下的暴力遍历办法，而考虑的是怎样优化复杂度

是否能够比较的次数
每天的气温能够认为是一个随机变量，遍历到具体某一天，这天之后的气温针对于这一天都是一个全新状况
假如早年往后，后边的每一天就需求墨守成规的遍历与当天比较
这样复杂度就为O(n^2)(系数忽略)

减少比较的次数

可否预先存储必定的进程比较成果
考虑从后往前遍历，这样针对于前面的某一天气温，这一天之后的气温就不再是彻底空的状况了，问题在于怎样样存储这些状况，又怎么运用
假如遍历到某一天，这一天之后的每一天都能存储下来气温上升需求的天数差值，也便是后一天存储了气温上升的天数
- 假如后一天气温比当天高，后边就不需求遍历了
- 那么假如后一天气温比当天低，遍历不再是后一天开始挨个往后遍历比较了，而是往后滑动一个窗口间隔再次比较
- 上面的进程重复，当天之后的遍历进程变为一个个窗口遍历，窗口针对于挨个遍历，次数就少了许多
- 除非当天之后的气温是升序的，而且最终一天气温比当天高，其他的每天气温都比当天低，这样窗口便是1，当天比较遍历流程这个回合里，这跟暴力没什么差异
- 这种极点情况也不会造成多大困扰，由于也就仅仅针对当天而已，跨过当天，后续的每一天的比较复杂度都是O(1)

反向遍历办法完结

这其实也包括了动态规划的思想，由于从后往前遍历，前面的每天在进行轮询判别的时分，都依靠往后的每一天的比较成果存储

//- 根据每日气温表，从头生成一个列表，对应方位的输入为
//  需求等候几天温度才会超越该方位对应的温度
//- 例如给定温度列表 [33, 34, 28, 25, 15, 36, 32, 22, 10, 37]
//
//    输出列表 [1, 4, 3, 2, 1, 4, 3, 2, 1, 0]
void day_weather(int array[], int n, int days[]) {
    // 从后往前遍历
    for (int i = n - 2; i >= 0; i--) {
        for (int j = i + 1; j < n; j += days[j]) {
            // 假如判别紧 第i天之后的一天 比当天气温高，就把天数差值存储下来
            if (array[i] < array[j]) {
                days[i] = j - i;
                break;
            } else if (days[j] == 0) {
                // 第i天之后的 第j天 不存在比第j天气温更高的 日子，
                // 那么 第i天 之后 也不存在比 第i天气温更高的 日子
                // 由于 第i天 现已比 第j天 气温高
                days[i] = 0;
            }
        }
    }
}

剖析二

上面的剖析一战略并没有最终把复杂度彻底降解到一个线性的维度

假如咱们靠空间换时间战略是否能够做到

通过额定空间缓存之前的每一步进程及状况信息，怎么做到呢？

之前的每一步记载都会缓存，为的是当前的节点与记载比较
并不是缓存之前一切的每一步记载
要点在于回溯进程

可能描绘仍是比较笼统，直接操作一遍流程，就比较明晰了

结合上面的流程

遍历进程中，事先并不知道后续还有没有比当天气温高的天
栈的作用便是让之前的比较进程能有时机先把index缓存起来
碰到日气温高的一天，当天index跟 pop栈index 差值存放在成果数组，方位就放在pop栈index处

最终成果便是 1 4 3 2 1 4 3 2 1 0

栈办法有没有下降时间复杂度呢，并没有，但是在处理复杂问题的时分，凭借栈能够处理

栈办法完结

void day_weather1(int array[], int n, int days[]) {
    struct SeqStack indexStack;
    initSeqStack(&indexStack);
    for (int i = 0; i < n; i++) {
        if (seqStackEmpty(&indexStack)) {
            union SeqStackNode sStackNode;
            sStackNode.data = i;
            pushSeqStack(&indexStack, &sStackNode);
            continue;
        }
        union SeqStackNode *topNode = topSeqStack(&indexStack);
        while (!seqStackEmpty(&indexStack) && array[topNode->data] < array[i]) {
            popSeqStack(&indexStack);
            days[topNode->data] = i - topNode->data;
            topNode = topSeqStack(&indexStack);
        }
        union SeqStackNode mNode;
        mNode.data = i;
        pushSeqStack(&indexStack, &mNode);
    }
}

去除重复字母，坚持字典序最小

标题

给定一个字符串，仅包括小写字母
需求除掉字符串中的重复字母，使得每个字母仅呈现一次
要求回来的成果字符串字典序列最小
不打乱其他字符的相对方位
给定 bccbbcadbaec, adbec 就比 bcade 字典序小

剖析

去重问题不大，便是完结简略与复杂的问题
去重，去哪些，留哪个，由字典序成果而定
怎么处理挑选进程
字典序 – 比较字母ascii
有先后次序，能够用栈来操控
需求一个记载容器，记载字符呈现的次数

完结

char *remove_dup_chars(char *src) {
    if (src == NULL) {
        return "";
    }
    int records[26] = {0};      // char - 'a' = index
    int len = (int)strlen(src);
    char *stack = malloc((len + 1) * sizeof(char));
    memset(stack, 0, (len + 1) * sizeof(char));
    if (len <= 1) {
        return src;
    }
    int top = -1;
    for (int i = 0; i < len; i++) {
        records[src[i] - 'a']++;
    }
    for (int i = 0; i < len; i++) {
        bool ifExist = false;
        for (int j = 0; j <= top; j++) {
            if (stack[j] == src[i]) {
                ifExist = true;
                break;
            }
        }
        if (ifExist) { // 假如栈现已存在字符，就不需求再压栈了 记载中呈现次数--
            records[src[i] - 'a']--;
        } else {
            while (top > -1 && stack[top] > src[i] && records[stack[top] - 'a'] > 1) {
                records[stack[top] - 'a']--;
                top--;
            }
            stack[++top] = src[i];
        }
    }
    stack[++top] = '\n';
    return stack;
}

字符串编码

标题

给定一个经过编码的字符串，回来它解码后的字符串
k[encoded_string] -> encoded_string 重复k次
encoded_string 没有额定的空格
3[a]2[bc] -> aaabcbc
3[a2[c]] -> accaccacc
2[abc]3[cd]ef -> abcabccdcdcdef

剖析

解析字符串，字符串中包括指令字符跟文本字符及操控字符需求解析的，栈是最合适的成果
[] 界定问题
假如数字是1位以上的字符处理，如13

完结

实例中栈结构用模仿办法处理

仔细揣摩判别的进程

举例 – 3[a2[c]]

碰到 3 压栈
[ 压栈
a 压栈
2 压栈
[ 压栈
c 压栈
] 解析 cc -> 3[acc
] 解析 accaccacc

char * str_decode(char *src_str) {
    int stack_size = 20;
    int append_size = 10;
    char *stack = (char *)malloc(stack_size * sizeof(char));
    int top = -1;
    int len = (int)strlen(src_str);
    // 字符入栈
    for (int i = 0; i < len; i++) {
        if (src_str[i] != ']') {
            if (top == stack_size - 1) {
                stack_size += append_size;
                stack = realloc(stack, stack_size * sizeof(char));
            }
            stack[++top] = src_str[i];
        } else {
            // i方位碰到了 ]
            // 界说一个 结构 pop出来的元素
            int m_size = 10;
            int m_append_size = 5;
            int m_top = -1;
            char *mstack = (char *)malloc(sizeof(char));
            while (stack[top] != '[') {
                if (m_top == m_size - 1) {
                    m_size += m_append_size;
                    mstack = realloc(mstack, m_size *sizeof(char));
                }
                mstack[++m_top] = stack[top--];
            }
            // '[' 出栈
            top--;
            // 解析数字
            char str_num[10];
            int len_str_num = 0;
            while (top > -1 && stack[top] >= '0' && stack[top] <= '9') {
                str_num[len_str_num++] = stack[top--];
            }
            int num = atoi(str_num);
            int temp_top = m_top;
            for (int i = 0; i < num; i++) {
                m_top = temp_top;
                while (m_top > -1) {
                    if (top == stack_size - 1) {
                        stack_size += append_size;
                        stack = realloc(stack, stack_size * sizeof(char));
                    }
                    stack[++top] = mstack[m_top--];
                }
            }
            free(mstack);
            mstack = NULL;
        }
    }
    stack = realloc(stack, (top + 1) * sizeof(char));
    stack[top + 1] = '\0';
    return stack;
}

我正在参加掘金技能社区创作者签约方案招募活动，点击链接报名投稿

栈递归算法应用实现

栈的次序结构完结

栈的链式结构完结

进制转换问题

爬楼梯问题

标题

剖析

爬楼梯算法完结

每日气温问题

标题

剖析一

反向遍历办法完结

剖析二

栈办法完结

去除重复字母，坚持字典序最小

标题

剖析

完结

字符串编码

标题

剖析

完结

作者信息

栈 递归 算法应用实现

栈的次序结构完结

栈的链式结构完结

进制转换问题

爬楼梯问题

标题

剖析

爬楼梯算法完结

每日气温问题

标题

剖析一

反向遍历办法完结

剖析二

栈办法完结

去除重复字母，坚持字典序最小

标题

剖析

完结

字符串编码

标题

剖析

完结

相关文章

线程池封装及拒绝策略

37 岁老码农写的脚手架生成工具，两年赚了 10 几万美元

为Android构建现代应用——应用架构

Python编程：从入门到实践 第14章 pygame

作者信息

栈递归算法应用实现

Python编程：从入门到实践第14章 pygame