目录
前言
一、用栈实现队列
二、用队列实现栈
三、括号匹配问题
前言
前面讲了栈和队列的基础知识，今天来巩固一下加深理解，这里说明一下，因为现在都是在用C语言写，这些OJ题里都要用到前面实现栈和队列的代码，每道题我都会加上前面的链接方便查看。
一、用栈实现队列
这里先给一下题目链接（用栈实现队列），同时这道题我们需要用到前面实现栈的代码，不清楚的可以看这里（数据结构：栈）。
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
bool empty() 如果队列为空，返回 true ；否则，返回 false
示例 1：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
题目要求用两个栈实现队列，可以想一下，栈是先进后出，队列先进先出，先创建两个栈，数据进队列时放入一个栈中，出队列时就把一个栈中数据再按相反的顺序放进另一个栈中，要出队列的那个数据就成了栈顶，实现了用两个栈模拟出队列，其他操作类似。
下面放代码（代码片段后都有解释），这里就不放栈的实现的代码了，可以去前面的章节看，链接我前面放了。
typedef struct {Stack z1;Stack z2;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* s=(MyQueue*)malloc(sizeof(MyQueue));StackInit(&s->z1);StackInit(&s->z2);return s;
}创建两个栈,用到了前面栈的初始化。
bool myQueueEmpty(MyQueue* obj)
{return StackEmpty(&obj->z1)&&StackEmpty(&obj->z2);
}两个栈都为空那么这个队列就是空的。
void myQueuePush(MyQueue* obj, int x) {if(!StackEmpty(&obj->z1)){StackPush(&obj->z1,x);}else{StackPush(&obj->z2,x);}
}int myQueuePop(MyQueue* obj) {Stack* empty = &obj->z1;
Stack* noempty = &obj->z2;
if (!StackEmpty(&obj->z1))
{empty = &obj->z2;noempty = &obj->z1;
}
while (!StackEmpty(noempty))
{StackPush(empty, StackTop(noempty));StackPop(noempty);
}
int a = StackTop(empty);
StackPop(empty);
while (!StackEmpty(empty))
{StackPush(noempty, StackTop(empty));StackPop(empty);
}
return a;
}模拟进队列就像前面说的，除了第一次数据入栈，后面都是找一个有数据的栈入栈，出队列先要分清有数据的栈和空栈，把数据按相反的顺序入到空栈中，再删除栈顶元素。
int myQueuePeek(MyQueue* obj) {if(!StackEmpty(&obj->z1)){return obj->z1.a[0];}else{return obj->z2.a[0];}
}模拟返回队列开头元素，只要找到有数据的栈，返回栈底元素，因为我前面栈的实现是用数组写的，这里可以直接取栈底元素。
void myQueueFree(MyQueue* obj) {StackDestroy(&obj->z1);StackDestroy(&obj->z2);free(obj);
}模拟队列销毁，这个没什么好说的，把两个栈销毁就行。
二、用队列实现栈
和前面用栈实现队列类似，创建两个队列，模拟入栈时就是把数据放入一个队列中，出栈时就把一个队列的数据按相反的顺序放入另一个队列中，取队头数据模拟出栈，其他操作思路类似，其实就是围绕栈和队列的性质写。这里题目链接（用队列实现栈），还有实现队列的代码（数据结构：队列），可以自己去尝试一下，下面放代码就不解释了。
typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate()
{MyStack*s=(MyStack*)malloc(sizeof(MyStack));QueueInit(&s->q1);QueueInit(&s->q2);return s;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q2)){QueuePush(&obj->q2,x);}else{QueuePush(&obj->q1,x);}
}int myStackPop(MyStack* obj) {Queue* empty=&(obj->q1);Queue* noempty=&(obj->q2);if(!QueueEmpty(&(obj->q1))){empty=&(obj->q2);noempty=&(obj->q1);}while(QueueSize(noempty)>1){QueuePush(empty,QueueFront(noempty));QueuePop(noempty);}int a=QueueFront(noempty);QueuePop(noempty);return a;
}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) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj=NULL;
}三、括号匹配问题
这里先给题目链接（有效的括号）
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：输入：s = "()[]{}"
输出：true
示例 3：输入：s = "(]"
输出：false
这道题用栈写，可以用到栈的先进后出的性质，先上代码后面解释。
bool isValid(char* s) {Stack st;StackInit(&st);while(*s){if(*s=='('||*s=='{'||*s=='['){StackPush(&st,*s);}else{if(StackEmpty(&st))return false;char top=StackTop(&st);if(top=='('&&*s!=')'||top=='{'&&*s!='}'||top=='['&&*s!=']'){return false;}StackPop(&st);}s++;}if(StackEmpty(&st)){return true;}return false;
}先对字符串中的括号进行判断，如果是左括号就入栈，如果是右括号就开始匹配，匹配时入过栈中没有数据就说明没有左括号，那么就一定匹配失败，返回false，如果有数据，就开始判断左括号是否与之对应从而得出结果，不相同就返回false，相同就把栈中的这歌数据删除，继续下一对的判断，直到字符串没有后续字符了，注意：出循环后如果栈中还有数据，那也是匹配失败，说明没有与之对应的右括号。
本篇内容就到这里了，每个题目都给了链接，还是要多练手，希望对各位有帮助。
