【算法集訓】基礎數據結構：四、棧

棧理解了兩天，所以遲了一天發。

一、棧的概念

棧是一個容器，是一個先進后出的線性表，類似與日常生活中的電梯、杯子等。
僅限在表尾部進行插入和刪除操作。
使用鏈表來模擬棧：

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;
}