2.7日学习总结

深入探究栈、队列与二叉树

一、栈的深度剖析

1. 进阶特性：除了常规的入栈、出栈操作，栈在处理函数调用、表达式求值等场景时，展现出独特的递归模拟能力。利用栈可以将递归算法转化为非递归形式，有效避免因递归过深导致的栈溢出问题。例如，计算斐波那契数列，递归方式简单直观但效率低且易栈溢出，通过栈模拟递归过程，能精准控制计算流程，提升性能。

2. 题目（括号匹配）：

   题目描述：给定一个只包含括号字符（如 ()、[]、{}）的字符串，判断括号是否匹配正确。例如，{[()]} 是匹配的，{[(])} 是不匹配的。

解题思路：使用栈来存储左括号，遍历字符串，遇到左括号则入栈，遇到右括号时，检查栈顶元素是否与之匹配的左括号，若匹配则出栈，否则说明括号不匹配。最后检查栈是否为空，为空则表示所有括号匹配成功。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAX_SIZE 100typedef struct {char data[MAX_SIZE];int top;
} Stack;void initStack(Stack *s) {s->top = -1;
}int isEmpty(Stack *s) {return s->top == -1;
}void push(Stack *s, char c) {if (s->top == MAX_SIZE - 1) {printf("Stack Overflow!\n");return;}s->top++;s->data[s->top] = c;
}char pop(Stack *s) {if (isEmpty(s)) {printf("Stack Underflow!\n");return '\0';}char c = s->data[s->top];s->top--;return c;
}int isMatch(char left, char right) {if (left == '(' && right == ')') return 1;if (left == '[' && right == ']') return 1;if (left == '{' && right == '}') return 1;return 0;
}int bracketMatch(char *str) {Stack s;initStack(&s);for (int i = 0; i < strlen(str); i++) {if (str[i] == '(' || str[i] == '[' || str[i] == '{') {push(&s, str[i]);} else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {if (isEmpty(&s) ||!isMatch(pop(&s), str[i])) {return 0;}}}return isEmpty(&s);
}int main() {char str[MAX_SIZE];printf("请输入括号字符串：");scanf("%s", str);if (bracketMatch(str)) {printf("括号匹配成功！\n");} else {printf("括号匹配失败！\n");}return 0;
}

二、队列的进阶探索

1. 优化应用：在多线程编程环境下，队列常用于实现线程间的安全通信。生产者线程将数据放入队列，消费者线程从队列中取出数据处理，通过合理的同步机制（如互斥锁、信号量）确保数据一致性与操作的有序性，避免资源竞争冲突。

1. 题目示例 - 滑动窗口最大值：

题目描述：给定一个整数数组 nums 和一个整数 k，表示滑动窗口的大小，求滑动窗口在数组上滑动时，每个窗口内的最大值。例如，nums = [1,3,-1,-3,5,3,6,7]，k = 3，输出应为 [3,3,5,5,6,7]。

解题思路：利用双端队列（一种特殊的队列结构，两端均可进出元素），队列中存储数组元素的下标，保证队列头部始终为当前窗口内的最大值下标。遍历数组，当新元素入队时，将小于新元素的队尾元素依次出队，确保队列单调递减，然后根据窗口移动，判断队头元素是否在窗口内，若不在则出队，最后取队头元素对应的值作为当前窗口最大值。

#include <stdio.h>
#include <stdlib.h>typedef struct Node {int index;struct Node *next;
} Node;typedef struct Deque {Node *front;Node *rear;
} Deque;void initDeque(Deque *dq) {dq->front = dq->rear = NULL;
}int isEmptyDeque(Deque *dq) {return dq->front == NULL;
}void pushBack(Deque *dq, int index) {Node *newNode = (Node *)malloc(sizeof(Node));newNode->index = index;newNode->next = NULL;if (dq->rear == NULL) {dq->front = dq->rear = newNode;} else {dq->rear->next = newNode;dq->rear = newNode;}
}void pushFront(Deque *dq, int index) {Node *newNode = (Node *)malloc(sizeof(Node));newNode->index = index;newNode->next = dq->front;if (dq->front == NULL) {dq->front = dq->rear = newNode;} else {dq->front = newNode;}
}int popFront(Deque *dq) {if (isEmptyDeque(dq)) {return -1;}Node *temp = dq->front;int index = temp->index;dq->front = dq->front->next;if (dq->front == NULL) {dq->rear = NULL;}free(temp);return index;
}int popBack(Deque *dq) {if (isEmptyDeque(dq)) {return -1;}Node *prev = NULL;Node *curr = dq->front;while (curr->next!= NULL) {prev = curr;curr = curr->next;}int index = curr->index;if (prev == NULL) {dq->front = dq->rear = NULL;} else {prev->next = NULL;dq->rear = prev;}free(curr);return index;
}int getFront(Deque *dq) {if (isEmptyDeque(dq)) {return -1;}return dq->front->index;
}int getBack(Deque *dq) {if (isEmptyDeque(dq)) {return -1;}return dq->rear->index;
}int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {if (numsSize == 0) {*returnSize = 0;return NULL;}Deque dq;initDeque(&dq);int* result = (int*)malloc((numsSize - k + 1) * sizeof(int));*returnSize = numsSize - k + 1;for (int i = 0; i < k; i++) {while (!isEmptyDeque(&dq) && nums[getBack(&dq)] <= nums[i]) {popBack(&dq);}pushBack(&dq, i);}result[0] = nums[getFront(&dq)];for (int i = k; i < numsSize; i++) {if (!isEmptyDeque(&dq) && getFront(&dq) <= i - k) {popFront(&dq);}while (!isEmptyDeque(&dq) && nums[getBack(&dq)] <= nums[i]) {popBack(&dq);}pushBack(&dq, i);result[i - k + 1] = nums[getFront(&dq)];}return result;
}int main() {int nums[] = {1,3,-1,-3,5,3,6,7};int k = 3;int returnSize;int* result = maxSlidingWindow(nums, sizeof(nums) / sizeof(nums[0]), k, &returnSize);for (int i = 0; i < returnSize; i++) {printf("%d ", result[i]);}printf("\n");free(result);return 0;
}

三、二叉树的深度挖掘

1. 高级遍历技巧：在二叉树遍历基础上，衍生出了 Morris 遍历算法，它能在不使用额外栈空间（仅利用原树的空指针）的情况下，实现前序、中序、后序遍历，极大地优化了空间复杂度，对于大规模二叉树处理优势明显。

1. 题目示例 - 二叉树的最近公共祖先：

题目描述：给定一个二叉树，找出两个指定节点 p、q 的最近公共祖先。例如，在下面这棵二叉树中：

  3/ \5 1/ \ / \6 2 0 8/ \7 4

若 p = 5，q = 4，则最近公共祖先为 3。

解题思路：可以采用递归方法，从根节点开始遍历，若当前节点为空或等于 p 或 q，则返回当前节点；分别递归左子树和右子树，若左右子树返回值都不为空，则当前节点为最近公共祖先；若只有一个子树返回值不为空，则返回该子树的返回值。

四、总结

通过对栈、队列和二叉树的深入探究，结合实例题目演练，我们解锁了它们更多隐藏的潜能。这些知识不仅丰富了我们的编程技能库，更是在面对复杂算法设计、系统优化等任务时，为我们提供了多样化的解决方案。持续钻研、反复实践，定能让这些数据结构在你的指尖焕发出更强大的创造力，助力你攀登 C 语言编程的更高峰。