通过前面栈和队列的学习，现在来看这些算法题目
一、有效的括号
本题让判断括号是否有效
第一眼看可能没一点思路，但仔细分析一下；
我们学习过栈数据结构，知道栈先进后出的原则，那我们就可以使用啊；把题目的左括号存储起来，让右括号跟左括号一一比较。
思路：
遍历字符串，遇到左括号就括号入栈，遇到右括号就与栈顶数据进行对比，如果配对就继续；如果不配对，就返回false
画图分析：
现在有这样的括号字符串
遍历字符串，第一个是 { 左括号，就入栈
ps接着遍历， [ 依然是左括号，入栈
ps接着遍历， ( 还是左括号，入栈
ps接着遍历， ) 是右括号，与栈顶数据进行比较，括号匹配，出栈
ps接着遍历， ] 是右括号，与栈顶数据比较，括号匹配，出栈
ps接着遍历， } 是右括号，与栈顶数据进行比较，括号匹配，出栈
ps遍历完字符串，再判断栈是否为空？如果为空，就代表所以括号都匹配了；如果栈不为空，括号就不匹配。
此外，再遍历过程中，有依次括号不匹配就要直接返回false
力扣题代码如下：
typedef char SType; typedef struct Stack { SType* arr; int size; // 栈顶 int num; // 空间大小 } Stack; // 初始化 void STInit(Stack* ps) { assert(ps); ps->arr = NULL; ps->size = ps->num = 0; } // 判断栈是否为空 bool STEmpty(Stack* ps) { assert(ps); return ps->size == 0; } // 入栈 void STPush(Stack* ps, SType x) { assert(ps); // 判断空间大小是否足够 if (ps->num <= ps->size) { int newnum = (ps->num == 0) ? 4 : 2 * ps->num; SType* tmp = (SType*)realloc(ps->arr, newnum * sizeof(Stack)); if (tmp == NULL) { perror("realloc filed"); exit(1); } ps->arr = tmp; ps->num = newnum; } ps->arr[ps->size++] = x; } // 出栈 void STPop(Stack* ps) { assert(ps); // 不能传NULL assert(!STEmpty(ps)); // 栈不能为空 ps->size--; } // 取栈顶数据 SType STtop(Stack* ps) { assert(ps); // 不能传NULL assert(!STEmpty(ps)); // 栈不能为空 return ps->arr[ps->size - 1]; } // 获取栈中数据个数 int STSize(Stack* ps) { assert(ps); return ps->size; } // 栈的销毁 void STDesTroy(Stack* ps) { assert(ps); if (ps->arr) free(ps->arr); ps->arr = NULL; ps->size = ps->num = 0; } bool isValid(char* s) { Stack arr; // 初始化 STInit(&arr); char* ps = s; while (*ps != '\0') { if (*ps == '(' || *ps == '[' || *ps == '{') { // 入栈 STPush(&arr, *ps); } else { // 取栈顶数据 if (STEmpty(&arr)) { return false; } char ch = STtop(&arr); if ((ch == '(' && *ps == ')') || (ch == '[' && *ps == ']') || (ch == '{' && *ps == '}')) { STPop(&arr); } else { return false; } } ps++; } if (STEmpty(&arr)) // 栈为空 { return true; } return false; }
二、用队列实现栈
使用队列来实现栈，我们直到，队列是先进先出，而栈是先进后出。这里我们需要用两个队列来实现栈的相关操作
思路：
保证两个队列中有一个为空，再两个队列之间来回导入导出数据。
入栈：往不为空的队列里面插入数据
出栈：找到不为空的队列，将size-1个数据导入到另一个队列，最后剩余的一个数据，就是要出栈的数据
取栈顶元素：找到不为空的队列，取队尾元素即可
假设依次插入了1，2，3三个数据，现在要出栈
将q1中数据size-1（2个）导入到q2中。
现在q1当中剩余的数据就是要出栈的数据（即栈顶）。这样就满足了栈先进先出的特点。
力扣题代码如下：
typedef int QType; typedef struct QueueNode // 队列节结构 { QType data; struct QueueNode* next; } QueueNode; typedef struct Queue // 队列结构 { int size; // 队列中的数据个数 QueueNode* phead; // 队头 QueueNode* ptial; // 队尾 } Queue; // 初始化 void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptial = NULL; pq->size = 0; } // 判断队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->size == 0; } // 入队列--从队尾插入数据 void QueuePush(Queue* pq, QType x) { assert(pq); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); newnode->data = x; newnode->next = NULL; if (QueueEmpty(pq)) // 队列为空 { pq->phead = pq->ptial = newnode; } else { // 队列不为空 pq->ptial->next = newnode; pq->ptial = newnode; } pq->size++; } // 出队列--从对头删除数据 void QueuePop(Queue* pq) { assert(pq); // 不能传NULL //assert(!QueueEmpty(pq)); // 队列不能为空 QueueNode* del = pq->phead; pq->phead = pq->phead->next; if (pq->size == 1) // 队列只有一个节点 { pq->ptial = NULL; } pq->size--; free(del); del = NULL; } // 取队头数据 QType QueueFront(Queue* pq) { assert(pq); // 不能传NULL //assert(!QueueEmpty(pq)); // 队列不能为空 return pq->phead->data; } // 取队尾数据 QType QueueBack(Queue* pq) { assert(pq); // 不能传NULL //assert(!QueueEmpty(pq)); // 队列不能为空 return pq->ptial->data; } // 获取队列数据个数 int QueueSize(Queue* pq) { assert(pq); // 不能传NULL return pq->size; } // 销毁队列 void QueueDesTroy(Queue* pq) { assert(pq); // 不能传NULL //assert(!QueueEmpty(pq)); // 队列不能为空 QueueNode* pcur = pq->phead; while (pcur) { QueueNode* del = pcur; pcur = pcur->next; free(del); del = NULL; } pq->phead = pq->ptial = NULL; pq->size = 0; } typedef struct { Queue q1; Queue q2; } MyStack; MyStack* myStackCreate() { MyStack* Qst = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&Qst->q1); QueueInit(&Qst->q2); return Qst; } void myStackPush(MyStack* obj, int x) { // 往不为空的队列中插入数据 if (QueueEmpty(&obj->q1)) { QueuePush(&obj->q2, x); } else { QueuePush(&obj->q1, x); } } int myStackPop(MyStack* obj) { // 先找到不为空的队列 Queue* empq = &obj->q1; Queue* noneq = &obj->q2; if (!(QueueEmpty(&obj->q1))) // 如果q1不为空 { empq = &obj->q2; noneq = &obj->q1; } //empq -- 空队列 //noneq -- 非空队列 while(QueueSize(noneq) > 1) { // 将noneq队列的数据导入到empq中去 QueuePush(empq, QueueFront(noneq)); QueuePop(noneq); } int ret = QueueFront(noneq); QueuePop(noneq); return ret; } int myStackTop(MyStack* obj) { if(QueueEmpty(&obj->q1)) { return QueueBack(&obj->q2); }else{ return QueueBack(&obj->q1); } } bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); } void myStackFree(MyStack* obj) { free(obj); obj = NULL; }
【栈和队列】算法题 ---- 力扣（二）https://developer.aliyun.com/article/1621387
