1.[20]有效的括号

解题记录：
1.括号匹配是栈的典型应用，主要是一些情况的判断需要细致。
2.当输入括号总数为奇数时，一定匹配失败。
3.当输入为左括号时，直接入栈。
4.当输入为右括号时，若指针指向0，表示已无左括号可以匹配，匹配失败，若有左括号，则用match函数判断。
5.最后top指向0表示全部匹配完毕，匹配成功。

C语言代码：

char match(char c){ //符号匹配
    if (c == ')') return '(';
    else if (c == ']') return '[';
    else return '{';
}

bool isValid(char * s){
    int i, len = strlen(s), top = 0;
    char *stack = (char*)malloc(sizeof(char) * len); //利用栈，动态分配空间
    if (len % 2 == 1) return false; //奇数情况必不匹配
    for (i = 0; i < len; i++)
    {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') //左括号入栈
            stack[top++] = s[i]; //入栈
        else
        {
            if (!top) return false; //右括号多于左括号
            else if (stack[--top] != match(s[i])) return false; //不匹配返回false
        }
    }
    if (!top) return true; //全部匹配结束
    else return false;
}

2.[155]最小栈

解题记录：
1.使用链表表示栈，将栈中最小值记录在栈顶元素的结构体中，压栈操作用头插法效率更高。
2.每次压栈时将新入栈元素和原栈顶元素记录的栈中最小值进行比较，将更小的元素记录在新入栈元素的结构体中。
3.出栈和获取栈顶元素操作类似，obj->next表示栈顶元素，出栈后需要释放内存。
4.获取栈中最小值只需要读取栈顶元素中记录的min即可。

C语言代码：

typedef struct MinStack{
    int data; //数据
    int min; //最小值
    struct MinStack *next; //指向下一结点指针
} MinStack;

MinStack* minStackCreate() {
    MinStack *obj = (MinStack *)malloc(sizeof(MinStack)); //分配空间
    obj->next = NULL;
    return obj;
}

void minStackPush(MinStack* obj, int x) {
    MinStack *t = (MinStack *)malloc(sizeof(MinStack)); //新结点
    t->data = x;
    if (obj->next == NULL) //空链表
        t->min = x;
    else{
        if ((t->data) < (obj->next->min)) t->min = t->data; //新插入值比原链表最小值还要小，修改最小值
        else t->min = obj->next->min; //原最小值写在新结点中
    }
    t->next = obj->next;
    obj->next = t; //头插法
}

void minStackPop(MinStack* obj) {
    MinStack *tmp = obj->next; //指向栈顶
    if (tmp != NULL) //栈不为空
        obj->next = obj->next->next; //断链
    free(tmp);
}

int minStackTop(MinStack* obj) {
    return obj->next->data;
}

int minStackGetMin(MinStack* obj) {
    return obj->next->min;
}

void minStackFree(MinStack* obj) {
    free(obj);
}

3.[225]用队列实现栈

解题记录：
1.使用queue数组表示队列，头尾指针初始指向-1，元素入队时移动尾指针，出队时移动头指针。
2.因为要用队列实现栈，栈的特点是先入后出，因此每次入队时，要计算出队列元素有多少，只要它大于等于2，就要将原来的元素依次排到新元素后面，这样保证队头元素永远是后进的元素。
3.出栈操作只需要将头指针后移即可。
4.获取队头元素方法类似，但不移动头指针。
5.当队头队尾指针相等时，可判断栈空。

C语言代码：

typedef struct {
    int queue[100]; //长度为100的队列，因为题目说最多push操作100次
    int front; //头指针
    int rear; //尾指针
} MyStack;

MyStack* myStackCreate() { //创建栈
    MyStack *obj = (MyStack*)malloc(sizeof(MyStack));
    obj->front = -1;
    obj->rear = -1;
    return obj;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
    obj->queue[++obj->rear] = x;
    int len = obj->rear - obj->front; //目前有多少数据存储
    for (int i = 0, temp; i < len - 1; i++) //依次出队并入队，空出第一个位置
    {
        temp = obj->queue[++obj->front];
        obj->queue[++obj->rear] = temp;
    }
}

/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
    obj->front++;
    return obj->queue[obj->front];
}

/** Get the top element. */
int myStackTop(MyStack* obj) {
    return obj->queue[obj->front + 1];
}

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
    if (obj->front == obj->rear)
        return true;
    return false;
}

void myStackFree(MyStack* obj) {
    free(obj);
}