前言：
前面已经为大家讲解了栈和队列的概念以及如何实现，接下来本博主为大家整理了几道题目，帮助大家更好的理解栈和队列，请大家看完本文后不要忘记练习哦。
一、括号匹配问题
1.题目描述
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
2.解题思路
大家在看到此题时，相信会有以下思路：既然要解决括号匹配，那么，我用一个变量left来记录左括号的数量，用变量right来记录右括号的数量，咋一听似乎是可行的，那么，我们使用如下的代码经行测试。
1. bool isValid(char* s) { 2. int left = 0; 3. int right = 0; 4. while(*s) 5. { 6. if(*s == '(' || *s == '{' || *s == '[') 7. { 8. left++; 9. } 10. if(*s == ')' || *s == '}' || *s == ']') 11. { 12. right++; 13. } 14. s++; 15. } 16. if(right == left) 17. { 18. return true; 19. } 20. else 21. { 22. return false; 23. } 24. }
结果如下： 
很显然官方也知道我们会有这样的想法，提前准备好用例来隔绝此种可能。那么，我们就束手无策了吗？当然不能，坐以待毙不是我们的风格，对吧？
我们之前学习过了栈，那么，这道题我们用栈来考虑一下：
我们首先 开辟一个栈用来放左括号，当有右括号要来匹配时，我们拿出最后入栈的左括号与之匹配，若能匹配成功，就继续比较下一组，若不行就反回false。
这个思路明显可行，那我们就来实现一下吧！
1. bool isValid(char* s) { 2. Stack st; 3. StackInit(&st); 4. while(*s) 5. { 6. if(*s == '(' || *s == '[' || *s == '{') 7. { 8. StackPush(&st,*s); 9. } 10. else 11. { 12. int top = StackTop(&st); 13. StackPop(&st); 14. if(top == '(' && *s != ')'|| top == '{' && *s != '}' || top == '[' && *s != ']') 15. { 16. return false; 17. } 18. } 19. s++; 20. } 21. return true; 22. }
使用以上代码进行测试，至于栈的底层实现，相信大家都很乐意当CV工程师（手动dogo）。这样写，测试用例也可以通过，但提交会失败。 
这是为什么呢？大家这时把这个带入到代码中试一下，我们会发现无右括号与之匹配，那么，我们怎么处理比较好？我们可不可以在最后去判空一下，因为有右括号在时，我们才会进行Pop，这时又来个问题，如果只有右括号，没左括号，那还是true，对吧。所以，我们也应该在else那经行判空。这次思路代码如下：
1. bool isValid(char* s) { 2. Stack st; 3. StackInit(&st); 4. while(*s) 5. { 6. if(*s == '(' || *s == '[' || *s == '{') 7. { 8. StackPush(&st,*s); 9. } 10. else 11. { 12. if(StackEmpty(&st)) 13. { 14. return false; 15. } 16. int top = StackTop(&st); 17. StackPop(&st); 18. if(top == '(' && *s != ')'|| top == '{' && *s != '}' || top == '[' && *s != ']') 19. { 20. return false; 21. } 22. } 23. s++; 24. } 25. bool ret = StackEmpty(&st); 26. StackDestroy(&st); 27. return ret; 28. }
这次的提交不就通过了，所以，我们今后写代码一定要考虑周全。
3.题目链接
二、用队列实现栈
1.题目描述
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop和empty）。实现
MyStack类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。注意：
- 你只能使用队列的标准操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。- 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
2.解题思路
题目要求使用队列来实现栈，首先，我们都明白队列和栈的特点。队列：先进先出。栈：先进后出。那么使用两个队列来实现栈，就要使用其特性来进行实现。这里，给大家说一说思路： 
代码实现思路如下：
1. typedef struct { 2. Queue q1; 3. Queue q2; 4. } MyStack; 5. 6. MyStack* myStackCreate() { 7. MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); 8. QueueInit(&(pst->q1)); 9. QueueInit(&(pst->q2)); 10. return pst; 11. } 12. 13. void myStackPush(MyStack* obj, int x) { 14. if (!QueueEmpty(&(obj->q1))) 15. { 16. QueuePush(&(obj->q1), x); 17. } 18. else { 19. QueuePush(&(obj->q2), x); 20. } 21. }int myStackPop(MyStack* obj) { 22. Queue* empty = &obj->q1; 23. Queue* nonempty = &obj->q2; 24. if (!QueueEmpty(&obj->q1)) 25. { 26. nonempty = &obj->q1; 27. empty = &obj->q2; 28. } 29. while (QueueSize(nonempty) > 1) 30. { 31. QueuePush(empty, QueueFront(nonempty)); 32. QueuePop(nonempty); 33. } 34. int tmp = QueueFront(nonempty); 35. QueuePop(nonempty); 36. return tmp; 37. } 38. 39. int myStackTop(MyStack* obj) { 40. if (!QueueEmpty(&obj->q1)) 41. { 42. return QueueBack(&obj->q1); 43. } 44. else 45. { 46. return QueueBack(&obj->q2); 47. } 48. } 49. 50. bool myStackEmpty(MyStack* obj) { 51. return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2); 52. } 53. 54. void myStackFree(MyStack* obj) { 55. QueueDestroy(&obj->q1); 56. QueueDestroy(&obj->q2); 57. free(obj); 58. }
对于底层代码大家若是想练习敲一遍即可，如果熟悉了即可成为CV工程师。
3.题目链接
三、用栈实现队列
1.题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（
push、pop、peek、empty）：实现
MyQueue类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false说明：
- 你 只能 使用标准的栈操作 —— 也就是只有
push to top,peek/pop from top,size, 和is empty操作是合法的。- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
2.题目分析
此题与上题类似，都是互相实现对方的题目。此类题目都要求我们掌握其特性以及都对其底层代码都能熟练掌握。话不多说，我们来分析一下此题，大家都可以思考一下，此题大致思路与上题类似。 
代码实现思路如下：
1. typedef struct { 2. Stack p1; 3. Stack p2; 4. } MyQueue; 5. 6. 7. MyQueue* myQueueCreate() { 8. MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue)); 9. StackInit(&pst->p1); 10. StackInit(&pst->p2); 11. return pst; 12. } 13. 14. void myQueuePush(MyQueue* obj, int x) { 15. StackPush(&obj->p1,x); 16. } 17. 18. int myQueuePop(MyQueue* obj) { 19. int front = myQueuePeek(obj); 20. StackPop(&obj->p2); 21. return front; 22. } 23. 24. int myQueuePeek(MyQueue* obj) { 25. if(StackEmpty(&obj->p2)) 26. { 27. while(!StackEmpty(&obj->p1)) 28. { 29. int top = StackTop(&obj->p1); 30. StackPop(&obj->p1); 31. StackPush(&obj->p2,top); 32. } 33. } 34. return StackTop(&obj->p2); 35. } 36. 37. bool myQueueEmpty(MyQueue* obj) { 38. return StackEmpty(&obj->p1) && StackEmpty(&obj->p2); 39. } 40. 41. void myQueueFree(MyQueue* obj) { 42. StackDestory(&obj->p1); 43. StackDestory(&obj->p2); 44. free(obj); 45. }
3.题目链接
四、设计循环队列
在开始说此题前，先简单对大家解释一下什么为循环队列。
大家，可这样理解：相信大家对循环链表不陌生（博主之前讲解链表习题时说过）。那么，大家可以把链表换成数组想象一下即可。 
当我们简单知道了这是一个什么东西后，我们一定要明白的知识点为：如何判断此时的链表是空还是满？
如何断定是空？相信大家有办法即：因为要记录其头地址和尾地址，在开始时，使头地址和尾地址指向一致，此时该队列为空。
那么？如何判断该队列为满的情况呢？相信有人说：使头（head）和尾（tatil）一致即可。可是，咱们不是规定为空吗？这不就矛盾了吗？别慌，我将介绍两种方法供大家参考使用。
法一：设一个size常量。刚开始使之为0，数组长度为k，若size % k == 0，认为队列满了。相信此方法大家都能理解。
法二：多开辟一个一个空间，注意：此空间不放元素。判断队列满了的条件为：（tail+1）%k + 1 == head。大家可画图理解都不难。（常用法二）
此处，教大家一个计算队列元素的方法：（ tail-head+size（MAX）） %size（MAX）。可帮助大家解决选择题。
好了，我们一起来看看题目吧！
1.题目描述
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。
2. 题目分析
此题考查循环队列，其实就是上面我给大家说的知识，此题难点为：如何删除元素以及获取尾元素。
删除元素：使head++，然后确定其下标即可。操作很简单，该如何理解呢？ 
获取尾元素：有人说，这个简单取tail--的值即可，是不错。那要是tail此时指向头呢？估计会有人说：不可能，绝对不可能。怎么不可能呢？别忘了，这可是循环队列,都有可能 。
为了应对这种情况可以用这种写法:(tail-1+k+1) % (k+1) 。这个是常规写法,既然有常规,那肯定还有不常规了,不常规也可以称之为:装逼写法 。只要你一键三连便可解锁,即:(tail+k) %(k+1) 。这时,有人说了:就这?也没啥吗?你们这样想,如果没上面的写法,你能看懂这种写法吗?都看到这了,记得承诺哦 。
难点已解决,接下来,展示本题代码:
1. typedef struct { 2. int* a; 3. int head; 4. int ptail; 5. int k; 6. } MyCircularQueue; 7. 8. MyCircularQueue* myCircularQueueCreate(int k) { 9. MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); 10. obj->a = (int*)malloc(sizeof(int) * (k + 1)); 11. obj->head = obj->ptail = 0; 12. obj->k = k; 13. return obj; 14. } 15. bool myCircularQueueIsEmpty(MyCircularQueue* obj); 16. bool myCircularQueueIsFull(MyCircularQueue* obj); 17. bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { 18. if (myCircularQueueIsFull(obj)) { 19. return false; 20. } 21. obj->a[obj->ptail] = value; 22. obj->ptail++; 23. obj->ptail %= (obj->k + 1); 24. 25. return true; 26. } 27. 28. bool myCircularQueueDeQueue(MyCircularQueue* obj) { 29. if (myCircularQueueIsEmpty(obj)) { 30. return false; 31. } 32. ++obj->head; 33. obj->head %= (obj->k + 1); 34. return true; 35. } 36. 37. int myCircularQueueFront(MyCircularQueue* obj) { 38. if (myCircularQueueIsEmpty(obj)) { 39. return -1; 40. } else { 41. return obj->a[obj->head]; 42. } 43. } 44. 45. int myCircularQueueRear(MyCircularQueue* obj) { 46. if (myCircularQueueIsEmpty(obj)) { 47. return -1; 48. } else { 49. return obj->a[(obj->ptail + obj->k ) %( obj->k + 1)]; 50. } 51. } 52. 53. bool myCircularQueueIsEmpty(MyCircularQueue* obj) { 54. return obj->head == obj->ptail; 55. } 56. 57. bool myCircularQueueIsFull(MyCircularQueue* obj) { 58. return (obj->ptail + 1) % (obj->k + 1) == obj->head; 59. } 60. void myCircularQueueFree(MyCircularQueue* obj) { 61. free(obj->a); 62. free(obj); 63. }
3.题目链接
最后
以上便是全部内容,记得练习 。如有问题可私信也可评论区见!
完!
