声明：由于C的局限性，以下OJ题所用到的接口(如Init、Pop、Push等)都需要自己实现，详情请看C语言实现栈和队列
1. 有效的括号
思路：利用栈的结构特性：先进后出。
假设输入()[]{}
- 将所有的左括号压入栈中(
([{) - 剩下的右括号与离它最近的左括号匹配。如何匹配？——出栈
- 函数调用的接口是自己实现的，唯一需要改动的是数据类型
typedef char STDataType;此处体现了类型重命名的好处。 - 匹配前注意判空
- 注意字符串的迭代
bool isValid(char * s){ struct Stack st; StackInit(&st); while(*s) { if(*s == '[' || *s == '(' || *s == '{') { StackPush(&st, *s);//压栈 s++;//字符串迭代 } else { if(StackEmpty(&st))//前面无括号 { StackDestroy(&st); return false; } else { char top = StackTop(&st);//得到栈顶元素 if((top == '[' && *s != ']')//不匹配的情况 || (top == '(' && *s != ')') || (top == '{' && *s != '}')) { StackDestroy(&st); return false; } else//剩下的是匹配的情况 { StackPop(&st);//出栈，下次循环开始得到下一个元素 s++;//字符串迭代 } } } } //如果栈中都匹配完了，就不会剩下括号 bool ret = StackEmpty(&st);//改接口判断栈是否为空 StackDestroy(&st); return ret; }
2. 用队列实现栈
思路：用队列实现栈，实际上就是用先进先出实现先进后出的效果。可以用两个队列来实现。
- 入数据：往非空的队列入数据
- 出数据：将最后一个元素之前的所有元素放到另一个空队列中，然后把剩下的一个返回后删除
2.1 结构的定义
用队列实现栈，MyStack这个结构就要用两个队列作为成员
typedef struct { Queue q1; Queue q2; } MyStack;
2.2 队列的初始化和销毁
要先为结构体（队列）开辟空间，然后再初始化两个队列
MyStack* myStackCreate() { MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); QueueInit(&pst->q1); QueueInit(&pst->q2); return pst; }
注意free的顺序，从结构体内到外
void myStackFree(MyStack* obj) { QueueDestroy(&obj->q1); QueueDestroy(&obj->q2); free(obj); }
2.3 模拟入栈
用入队模拟入栈。
- 注意入队的是非空队列
void myStackPush(MyStack* obj, int x) { if(!QueueEmpty(&obj->q1)) { QueuePush(&obj->q1, x); } else { QueuePush(&obj->q2, x); } }
2.4 模拟出栈
假设入栈的是1、2、3、4，出栈第一个数据是4
首先假设空的是q1，非空是q2，如果事实相反，则用条件判断反置
然后将非空队列的前size-1个(要调用size接口)放到空的队列，边放边删除(这样才能放下一个)。
放完以后把剩下的那一个没放的删掉。但是这个数据(4)就是要出栈的数据，所以要用一个变量保存它并 返回，这样就达到了出栈的效果。
int myStackPop(MyStack* obj) { //假设 Queue* pEmpty = &obj->q1; Queue* pNonEmpty = &obj->q2; if(!QueueEmpty(&obj->q1))//如果假设不成立，反置赋值语句 { pEmpty = &obj->q2; pNonEmpty = &obj->q1; } while(QueueSize(pNonEmpty) > 1)//留下最后一个要出栈的数据 { //将数据放到空队列中 QueuePush(pEmpty, QueueFront(pNonEmpty)); //边放边删除非空队列的数据 QueuePop(pNonEmpty); } //在删除最后一个要出栈的数据之前保存并返回它 int front = QueueFront(pNonEmpty); QueuePop(pNonEmpty); return front; }
2.5 模拟获取栈顶数据
队列一定是一个为空，一个非空，将非空队列中的队尾数据返回
例如1、2、3、4，栈顶数据为4，它处于队尾
int myStackTop(MyStack* obj) { if(!QueueEmpty(&obj->q1)) { return QueueBack(&obj->q1); } else { return QueueBack(&obj->q2); } }
2.6 判空
因为模拟的栈中是两个队列，所以两个队列都要判断
bool myStackEmpty(MyStack* obj) { return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); }
3. 用栈实现队列
思路：
思路和上一题类似，同样是用两个栈(先进后出)模拟实现队列(先进先出)。不同的是，两个栈各自的功能不同，一个只出栈，一个只入栈。
ps：这里的思路有点像反转字符串。每次出栈都是调换一次顺序，出两次栈就抵消了。
3.1 结构的定义
用栈模拟实现队列，需要连续出栈两次，所以要定义两个栈
typedef struct { Stack pushSt; Stack popSt; } MyQueue;
3.2 栈的初始化和销毁
首先要为队列开辟空间，然后初始化栈
MyQueue* myQueueCreate() { MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue)); StackInit(&q->pushSt); StackInit(&q->popSt); return q; }
销毁注意顺序
void myQueueFree(MyQueue* obj) { StackDestroy(&obj->pushSt); StackDestroy(&obj->popSt); free(obj); }
3.3 判空
判断队列是否为空，即判断两个栈是否为空
bool myQueueEmpty(MyQueue* obj) { return StackEmpty(&obj->pushSt) && StackEmpty(&obj->popSt); }
3.4 压栈
直接压入即可
void myQueuePush(MyQueue* obj, int x) { StackPush(&obj->pushSt, x); }
3.5 获取栈顶元素
- 要把非空的pushST的所有元素放到空的popST中，注意判断条件
- 在把pushST元素放入popST中后，记得删除该元素
- 最后才是返回popST的栈顶元素
int myQueuePeek(MyQueue* obj) { if(StackEmpty(&obj->popSt)) { while(!StackEmpty(&obj->pushSt)) { StackPush(&obj->popSt, StackTop(&obj->pushSt)); StackPop(&obj->pushSt); } } return StackTop(&obj->popSt); }
3.6 出栈
边出栈，边删除，用top保存popST的栈顶元素并返回
int myQueuePop(MyQueue* obj) { int top = myQueuePeek(obj); StackPop(&obj->popSt); return top; }
4. 设计循环队列
详见循环队列
日志
4/23/2022
