在C语言的基础上用栈实现积水问题

栈是一种先进后出的数据结构，使用栈可以实现积水问题的解决，具体实现如下：

1. 定义一个栈结构体，包括栈顶指针和栈数组；

2. 定义一个函数push，将元素压入栈中；

3. 定义一个函数pop，将栈顶元素弹出；

4. 定义一个函数isEmpty，判断栈是否为空；

5. 定义一个函数isFull，判断栈是否已满；

6. 定义一个函数findWater，求解积水问题，具体思路如下：

   （1）遍历数组，如果当前元素小于等于栈顶元素，则将当前元素入栈；

   （2）如果当前元素大于栈顶元素，则弹出栈顶元素，并计算积水量；

   （3）重复步骤（1）和（2），直到遍历完整个数组。

下面是代码实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// 定义栈结构体
typedef struct {
    int top;
    int data[MAX_SIZE];
} Stack;

// 函数声明
void push(Stack *stack, int x);
int pop(Stack *stack);
int isEmpty(Stack *stack);
int isFull(Stack *stack);
int findWater(int *height, int n);

int main() {
    int height[] = {0,1,0,2,1,0,1,3,2,1,2,1};
    int n = sizeof(height)/sizeof(height[0]);
    int water = findWater(height, n);
    printf("The amount of water is: %d\n", water);
    return 0;
}

void push(Stack *stack, int x) {
    if (isFull(stack)) {
        printf("Error: Stack is full\n");
        exit(1);
    }
    stack->data[++stack->top] = x;
}

int pop(Stack *stack) {
    if (isEmpty(stack)) {
        printf("Error: Stack is empty\n");
        exit(1);
    }
    return stack->data[stack->top--];
}

int isEmpty(Stack *stack) {
    return stack->top == -1;
}

int isFull(Stack *stack) {
    return stack->top == MAX_SIZE - 1;
}

int findWater(int *height, int n) {
    Stack stack;
    stack.top = -1;
    int water = 0;
    for (int i = 0; i < n; i++) {
        while (!isEmpty(&stack) && height[i] > height[stack.data[stack.top]]) {
            int top = pop(&stack);
            if (isEmpty(&stack)) {
                break;
            }
            int distance = i - stack.data[stack.top] - 1;
            int h = (height[i] < height[stack.data[stack.top]]) ? height[i] - top : height[stack.data[stack.top]] - top;
            water += distance * h;
        }
        push(&stack, i);
    }
    return water;
}

其中，height数组表示给定的高度数组，n为数组长度，findWater函数返回积水量。

这里的积水量计算方法与之前介绍的相同，通过栈来记录高度递减的位置，当遇到高度递增的位置时，弹出栈顶元素，并计算积水量。需要注意的是，如果弹出栈顶元素后栈为空，则不计算积水量。积水量的计算公式为distance * h，其中distance表示两个高度递减位置之间的距离，h表示两个高度递减位置之间的积水高度。