一. 栈

1.1 基本概念

栈是只允许在一端进行插入或删除操作的线性表

  1. 栈顶：线性表允许进行插入或删除的那一端
  2. 栈底：固定的， 不允许进行插入和删除的那一端
  3. 空栈：不含任何元素的空表

栈的操作特性可以概括为后进先出

1.2 基本操作

  1. 初始化一个空栈
initStack
  1. 判断一个栈是否为空，栈为空返回 true，否则返回 false
empty
  1. 进栈，若栈未满，将元素 value 加入成为新的栈顶元素
push
  1. 出栈，若栈非空，则弹出栈顶元素
pop
  1. 读栈顶元素，若栈非空，则用 x 返回栈顶元素
getTop
  1. 销毁栈
destoryStack

1.3 栈的顺序存储结构

typedef struct{                                        
    int *data;                                         
    int capacity;                                      
    int top;                                           
}Stack;

int initStack(Stack *stack, int capacity){
    if(stack == NULL)
        return -1;
    stack->data = (int *)calloc(capacity, sizeof(int));
    stack->capacity = capacity;
    stack->top = -1;
    return 0;
}

int destoryStack(Stack *stack){
    if(stack == NULL || stack->data == NULL)
        return -1;
    free(stack->data);
    return 0;
}

int empty(Stack *stack){
    if(stack->top == -1)
        return 1;
    return 0;
}

int push(Stack *stack, int val){
    if(stack == NULL || stack->data == NULL)
        return -1;
    if(stack->top == stack->capacity - 1){
        stack->data = realloc(stack->data, 2 * stack->capacity * sizeof(int));
        stack->capacity *= 2;
    }
    stack->data[++stack->top] = val;
    return 0;
}

int getTop(Stack *stack, int *val){
    if(stack == NULL || stack->data == NULL || stack->top == -1)
        return -1;
    *val = stack->data[stack->top];
    return 0;
}

int pop(Stack *stack){
    if(stack == NULL || stack->data == NULL || stack->top == -1)
        return -1;
    --stack->top;
    return 0;
}

作业

1. 给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 注意空字符串可被认为是有效字符串。

示例 1: 输入: “()” 输出: true

示例 2: 输入: “()[]{}” 输出: true

示例 3: 输入: “(]” 输出: false

示例 4: 输入: “([)]” 输出: false

示例 5: 输入: “{[]}” 输出: true

2. 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入：“abbaca”

输出：“ca”

解释：例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。

3. 编写函数，将由小写字母表示的中缀表达式转换为后缀表达式

示例：

输入：“(a+b)*c”

输出：“ab+c*”

4. 根据逆波兰表示法，求表达式的值。

有效的运算符包括 + ,  - ,  * ,  / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入: [“2”, “1”, “+”, “3”, “*”]

输出: 9

解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入: [“4”, “13”, “5”, “/”, “+”]

输出: 6

解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

5. 请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。