文章的算法实例阅览需求必定的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;
}

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

栈递归算法应用实现

栈的次序结构完结

栈的链式结构完结

进制转换问题

爬楼梯问题

标题

剖析

爬楼梯算法完结

每日气温问题

标题

剖析一

反向遍历办法完结

剖析二

栈办法完结

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

标题

剖析

完结

字符串编码

标题

剖析

完结

作者信息

推广

栈 递归 算法应用实现

栈的次序结构完结

栈的链式结构完结

进制转换问题

爬楼梯问题

标题

剖析

爬楼梯算法完结

每日气温问题

标题

剖析一

反向遍历办法完结

剖析二

栈办法完结

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

标题

剖析

完结

字符串编码

标题

剖析

完结

相关文章

ChatGPT 助力开发人员改进代码的5个方式

时间都去哪儿｜2022年

GPT4技术面试利器——遇事不决，可问GPT

88年大龄前端：转行前端不到两年|2022年年中总结

作者信息

推广

栈递归算法应用实现