基础数据结构练习（栈）

一、图书整理

• 算法题目

图书整理

• 题目简介

• 涉及知识点

链表，栈

• 算法分析

1. 创建栈，将链表元素依次传给栈
2. 创建数组，将栈顶元素依次弹出放入数组
3. 返回数组

• 源码分析

int* reverseBookList(struct ListNode* head, int* returnSize) {
   int* stack = (int*)malloc(sizeof(int) * 10000);
   int top = 0;
   //链表元素赋给栈
   while(head)
   {
       stack[top++] = head->val;
       head = head->next;
   }
    //从栈顶依次弹出元素
    int* ret = (int*)malloc(sizeof(int) * 10000);
    *returnSize = 0;
    //卡点,误认为top是在这个循环结束后才--的。只要top被调用一次，就--
    while(top--)
    {
        ret[(*returnSize)++] = stack[top];
    }

    free(stack);
    return ret;
}

此题思路与回文链表相同

二 、括号的最大嵌套深度

• 算法题目

括号的最大嵌套深度

• 题目简介

• 涉及知识点

栈，字符串数组元素遍历

• 算法分析

1. 创建一个栈（类似的机制即可）
2. 碰到左括号进栈，再判断是否是最大嵌套深度
3. 碰到右括号就出栈，直到字符串结束

• 源码分析

//有几个左括号就有几个右括号
int maxDepth(char* s) {
    int top = 0;
    int i;
    int ret = 0;
    for(i=0;s[i]!='\0';i++)
    {
        if(s[i] == '(')
        {    top++;//进栈
            if(top > ret)
                ret = top;
        }
        else if(s[i] == ')')
        {
            top--;//出栈
        }
    }
    return ret;
}

这里top的++和–就相当于进出栈了，并不用重新创建一个栈

• FAQ

容易将问题复杂化，扩展思路，可以根据情景用这种方法模拟进出栈效果