一、有效的括号

20. 有效的括号

思路一：使用栈来解决

1、左括号：入栈

2、右括号：出栈顶的左括号跟右括号判断是否匹配：

匹配->继续

不匹配->终止

typedef char STDataType;typedef struct Stack{// 一般使用动态，不使用静态STDataType * a;// 表示栈顶int top;int capacity;
}ST;// 0.初始化
void StackInit(ST * ps);// 0.销毁
void StackDestory(ST * ps);// 栈一定是在栈顶操作
// 1.入栈
void StackPush(ST * ps,STDataType x);// 删除栈顶元素
// 2.出栈
void StackPop(ST * ps);// 3.取栈顶数据
STDataType StackTop(ST * ps);// 4.求数据个数
int StackSize(ST * ps);// 5.判断是否为空,bool判断真假
bool StackEmpty(ST * ps);// 0.初始化
void StackInit(ST * ps){// 正常结构体的地址给我，是不能为空的assert(ps);// 开辟空间：先开辟4个intps->a = (STDataType*)malloc(sizeof(STDataType)*4);if(ps->a == NULL){ // 表示未分配成功printf("malloc fail\n");exit(-1);}// 容量,可以存4个数据ps->capacity =4;// 栈顶开始为0，指向的是栈顶元素的下一个ps->top = 0;
}// 0.销毁
void StackDestory(ST * ps){// 正常结构体的地址给我，是不能为空的assert(ps);// 释放psfree(ps->a);ps->a = NULL;// 同时将容量和栈顶置为0ps->top = ps->capacity = 0;
}// 1.入栈
void StackPush(ST * ps,STDataType x){assert(ps);// 容量满了就需要扩容if(ps->top == ps->capacity){// 直接扩容2倍STDataType * tmp = (STDataType*)realloc(ps->a,ps->capacity*2*sizeof(STDataType));// 如果扩容失败if(tmp == NULL){printf("realloc fail\n");// 终止程序exit(-1);}else{// 分配成功，赋值给ps->aps->a = tmp;// 容量变成原来2倍ps->capacity *= 2;}}// 插入一个元素，然后栈顶++ps->a[ps->top] = x;ps->top++;/** 如果之前top在栈顶，就要先++在放数据*/
}// 2.出栈
void StackPop(ST * ps){assert(ps);// 栈空了,调用pop,直接终止程序报错assert(ps->top > 0);// 直接减减ps->top--;
}// 3.取栈顶数据
STDataType StackTop(ST * ps){assert(ps);// 栈空了，调用pop,直接中止程序报错assert(ps->top > 0);return ps->a[ps->top-1];
}// 4.求数据个数
int StackSize(ST * ps){assert(ps);return ps->top;
}// 5.判断是否为空,bool判断真假
bool StackEmpty(ST * ps){assert(ps);// 等于0则为真，为空；不等于0则为假不为空return ps->top == 0;
}

bool isValid(char* s) {ST st;StackInit(&st);while(*s != '\0'){switch(*s){case '{':case '[':case '(':// 是以上的就直接入栈{StackPush(&st,*s);++s;break;}// 如果是右括号，就取栈顶的元素case '}':case ']':case ')':{// 这里一个右括号肯定是false,因为栈已经为空if(StackEmpty(&st)){// 空间依然要销毁StackDestory(&st);return false;}char top = StackTop(&st);// 取值后将栈顶元素给pop掉StackPop(&st);// 三种之中不匹配if((*s == '}' && top != '{')||(*s == ']' && top != '[')||(*s == ')' && top != '(')){// 在return之间也要销毁掉StackDestory(&st);return false;}else{ // 匹配++s; // 继续走}break;}default:break;}}// 如果是空的表示匹配完了,表示为真,为假表示未匹配上bool ret = StackEmpty(&st);StackDestory(&st);return ret;
}

针对于OJ快速构建链表进行测试方法：

二、用队列实现栈

225. 用队列实现栈

思路一：

实现细节：

1. 入数据往不为空的队列入
2. 出数据，把不为空的数据导入到为空的，直到只剩余最后一个元素

typedef int QDataType;// 链式结构:表示队列
typedef struct QueueNode {struct QueueNode *next;QDataType data;
} QNode;// 队列结构：队头指针和队尾指针结构体
typedef struct Queue {QNode *head;QNode *tail;
} Queue;// 0.初始化
void QueueInit(Queue *pq);// 0.销毁
void QueueDestory(Queue *pq);// 1、队尾入
void QueuePush(Queue *pq, QDataType x);// 2.队头出
void QueuePop(Queue *pq);// 3.取队头数据
QDataType QueueFront(Queue *pq);// 4.取队尾数据
QDataType QueueBack(Queue *pq);// 5.取数据的个数
int QueueSize(Queue *pq);// 6.判断是否为空
bool QueueEmpty(Queue *pq);// 0.初始化
void QueueInit(Queue *pq) {assert(pq);// 最开始将队首指针和队尾指针初始化为空pq->head = pq->tail = NULL;
}// 1.队尾入
void QueuePush(Queue *pq, QDataType x) {assert(pq);// 搞一个新节点QNode *newnode = (QNode *) malloc(sizeof(QNode));if (newnode == NULL) {printf("malloc fail\n");exit(-1);}// 对新开的节点初始化一下newnode->data = x;newnode->next = NULL;// 如果尾指针都是空的，那么就把节点给它if (pq->tail == NULL) {pq->head = pq->tail = newnode;} else {// 不是空，有节点就连接到节点的后面pq->tail->next = newnode;// 将tail移动到最后pq->tail = newnode;}
}// 2.队头出
void QueuePop(Queue *pq) {assert(pq);// 判断队列是不等于空的assert(pq->head);// 分为一个节点和多个节点//  这里表示就只有一个节点了,释放掉后将tail和head都置为空// 防止野指针tailif (pq->head->next == NULL) {free(pq->head);pq->head = pq->tail = NULL;} else {// 保留head的下一个QNode *next = pq->head->next;free(pq->head);pq->head = next;}
}// 3.判断是否为空:等于空则返回true否则false
bool QueueEmpty(Queue *pq) {assert(pq);return pq->head == NULL;
}// 4.取队头数据
QDataType QueueFront(Queue *pq) {assert(pq);// 可以最后添加判断头是否为空,尾空则不调用assert(pq->head);// 直接返回头中的数据return pq->head->data;
}//  5.取队尾数据
QDataType QueueBack(Queue *pq) {assert(pq);assert(pq->head);return pq->tail->data;
}// 6.取数据的个数
int QueueSize(Queue *pq) {assert(pq);int size = 0;QNode *cur = pq->head;while (cur) {++size;cur = cur->next;}return size;
}// 7.销毁
void QueueDestory(Queue *pq) {assert(pq);QNode *cur = pq->head;while (cur) {// 将下一个存储起来QNode *next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;
}
//-------------------------------------------------typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {// 两个队列MyStack* ps = (MyStack*)malloc(sizeof(MyStack));if(ps == NULL){printf("malloc fail");exit(-1);}// 分配之后，初始化下QueueInit(&ps->q1);QueueInit(&ps->q2);return ps;
}void myStackPush(MyStack* obj, int x) {// 不为空，就往里入数据if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}
}int myStackPop(MyStack* obj) {// 假设q1为空，如不为空，则交换Queue* emptyQ = &obj->q1;Queue* nonemptyQ = &obj->q2;if(!QueueEmpty(&obj->q1)){// 如果q1为空不进入,不为空就进入，说明假设错误，进行交换emptyQ = &obj->q2;nonemptyQ = &obj->q1;}// 依次将数据从不是空的队列取出来，直到只剩一个while(QueueSize(nonemptyQ) > 1){QueuePush(emptyQ,QueueFront(nonemptyQ));QueuePop(nonemptyQ);}// 返回栈顶的元素int top = QueueFront(nonemptyQ);// 将最后一个数据出了：后进先出QueuePop(nonemptyQ);return top;
}int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1)){// 取队尾数据就相当于取栈顶数据return QueueBack(&obj->q1);}else{return QueueBack(&obj->q2);}
}bool myStackEmpty(MyStack* obj) {// q1和q2都为空return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {// 先要将里面的队列freeQueueDestory(&obj->q1);QueueDestory(&obj->q2);// 在free objfree(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/