【算法集训】基础数据结构：四、栈

栈理解了两天，所以迟了一天发。

一、栈的概念

栈是一个容器，是一个先进后出的线性表，类似与日常生活中的电梯、杯子等。
仅限在表尾部进行插入和删除操作。
使用链表来模拟栈：

typedef int DataType; 相当于给int起一个别名
struct StackNode;
struct StackNode {
	DataType data;
    struct StackNode * next;
}

data表示数据域，next表示指针域；

1、入栈操作

void StackPushStack(struct Stack * stk, DataType dt) {
    struct StackNode * vtx = (struct StackNode *) malloc(sizeof(struct StackNode));
    vtx->next = stk->head;
    vtx->data = dt;
    stk->head = vtx;
    ++stk->size;
}

2、出栈

void StackPopStack(struct Stack * stk) {
    struct StackNode * temp = stk->head;
    stk->head = temp->next;
    free(temp);
    --stk->size;
}

3、获取栈顶元素

DataType StackGetTop(struct Stack * stk) {
    return stk->head->data;
}

二、题目

1、LCR 123. 图书整理 I

https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/description/

定义两个栈，一个用于入栈存放，一个用于出栈存放，将链表中的数据入栈再出栈就是倒序了

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* reverseBookList(struct ListNode* head, int* returnSize) {
    int *inStack = (int *)malloc(sizeof(int) * 10000);
    int index = 0;
    while(head) {
        inStack[index++] = head->val;
        head = head->next;
    }
     
    *returnSize = 0;
    int *outStack = (int *)malloc(sizeof(int) * 10000);
    while(index--) {
        outStack[(*returnSize)++] = inStack[index];
    }
    free(inStack);
    return outStack;
}

2、1614. 括号的最大嵌套深度

https://leetcode.cn/problems/maximum-nesting-depth-of-the-parentheses/description/
我们都知道括号一定是成对出现的，所以嵌套的括号的（必然是一起的，所以计算（一起出现的最大次数即可。
这里使用栈实现，（入栈，）出栈，最终栈中存放最多的即为答案

int maxDepth(char* s) {
    int top = 0; //定义栈顶
    int len = strlen(s); //获取s长度
    int res = 0;  //结果
    //遍历字符串
    for(int i = 0; i < len; ++i) {
        //如果是(入栈,)出栈
        if(s[i] == '(') {
            top++;
        }else if(s[i] == ')') {
            top--;
        }
        //判断栈里面最大数就是深度
        if(top > res) res = top;
    }
    return res;

}

3、LCR 027. 回文链表

https://leetcode.cn/problems/aMhZSa/description/
判断回文，将给定的数组依次存入栈中，如果从栈顶开始和head比较的每一个值都相等， 则为回文数。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


bool isPalindrome(struct ListNode* head){
    //定义栈
    int * inStack = (int *)malloc(sizeof(int) * 100000);
    int top = 0;  //定义栈顶
    //复制头结点用于存栈
    struct ListNode* t = head;
    // 存入栈
    while(t) {
        inStack[top++] = t->val;
        t = t->next;
    }
    // 栈顶和head从头到尾比较,如果不相等则错误
    while(top--) {
        if(inStack[top] != head->val) {
            return false;
        }
        head = head->next;
    }
    return true;
}

以下两个题目和上题相等。
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
https://leetcode.cn/problems/palindrome-linked-list-lcci/description/