数据结构：栈与队列OJ题

目次
前言
一、用栈实现队列
 二、用队列实现栈
 三、括号匹配题目

---

前言

    前面讲了栈和队列的基础知识，今天来巩固一下加深理解，这里说明一下，由于现在都是在用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]
      题目要求用两个栈实现队列，可以想一下，栈是先辈后出，队列先辈先出，先创建两个栈，数据进队列时放入一个栈中，出队列时就把一个栈中数据再按相反的序次放进另一个栈中，要出队列的那个数据就成了栈顶，实现了用两个栈模拟出队列，其他操作雷同。
    下面放代码（代码片断后都有解释），这里就不放栈的实现的代码了，可以去前面的章节看，链接我前面放了。

1. typedef struct {
2.     Stack z1;
3.     Stack z2;
4. } MyQueue;
7. MyQueue* myQueueCreate() {
8.     MyQueue* s=(MyQueue*)malloc(sizeof(MyQueue));
9.     StackInit(&s->z1);
10.     StackInit(&s->z2);
11.     return s;
12. }

复制代码

创建两个栈,用到了前面栈的初始化。

1. bool myQueueEmpty(MyQueue* obj)
2. {
3.     return StackEmpty(&obj->z1)&&StackEmpty(&obj->z2);
4. }

复制代码

 两个栈都为空那么这个队列就是空的。

1. void myQueuePush(MyQueue* obj, int x) {
2.     if(!StackEmpty(&obj->z1))
3.     {
4.         StackPush(&obj->z1,x);
5.     }
6.     else
7.     {
8.         StackPush(&obj->z2,x);
9.     }
10. }
12. int myQueuePop(MyQueue* obj) {
13.    Stack* empty = &obj->z1;
14. Stack* noempty = &obj->z2;
15. if (!StackEmpty(&obj->z1))
16. {
17.         empty = &obj->z2;
18.         noempty = &obj->z1;
19. }
20. while (!StackEmpty(noempty))
21. {
22.         StackPush(empty, StackTop(noempty));
23.         StackPop(noempty);
24. }
25. int a = StackTop(empty);
26. StackPop(empty);
27. while (!StackEmpty(empty))
28. {
29.         StackPush(noempty, StackTop(empty));
30.         StackPop(empty);
31. }
32. return a;
33. }

复制代码

    模拟进队列就像前面说的，除了第一次数据入栈，后面都是找一个有数据的栈入栈，出队列先要分清有数据的栈和空栈，把数据按相反的序次入到空栈中，再删除栈顶元素。 

1. int myQueuePeek(MyQueue* obj) {
2.     if(!StackEmpty(&obj->z1))
3.     {
4.         return obj->z1.a[0];
5.     }
6.     else
7.     {
8.         return obj->z2.a[0];
9.     }
10. }

复制代码

    模拟返回队列开头元素，只要找到有数据的栈，返回栈底元素，由于我前面栈的实现是用数组写的，这里可以直接取栈底元素。

1. void myQueueFree(MyQueue* obj) {
2.     StackDestroy(&obj->z1);
3.     StackDestroy(&obj->z2);
4.     free(obj);
5. }

复制代码

     模拟队列销毁，这个没什么好说的，把两个栈销毁就行。
 二、用队列实现栈

     和前面用栈实现队列雷同，创建两个队列，模拟入栈时就是把数据放入一个队列中，出栈时就把一个队列的数据按相反的序次放入另一个队列中，取队头数据模拟出栈，其他操作思路雷同，其实就是围绕栈和队列的性质写。这里题目链接（用队列实现栈），还有实现队列的代码（数据结构：队列），可以自己去尝试一下，下面放代码就不解释了。

1. typedef struct {
2.     Queue q1;
3.     Queue q2;
4. } MyStack;
7. MyStack* myStackCreate()
8. {
9.     MyStack*s=(MyStack*)malloc(sizeof(MyStack));
10.     QueueInit(&s->q1);
11.     QueueInit(&s->q2);
12.     return s;
13. }
15. void myStackPush(MyStack* obj, int x) {
16.     if(!QueueEmpty(&obj->q2))
17.     {
18.         QueuePush(&obj->q2,x);
19.     }
20.     else
21.     {
22.         QueuePush(&obj->q1,x);
23.     }
24. }
26. int myStackPop(MyStack* obj) {
27.     Queue* empty=&(obj->q1);
28.     Queue* noempty=&(obj->q2);
29.     if(!QueueEmpty(&(obj->q1)))
30.     {
31.         empty=&(obj->q2);
32.         noempty=&(obj->q1);
33.     }
34.     while(QueueSize(noempty)>1)
35.     {
36.         QueuePush(empty,QueueFront(noempty));
37.         QueuePop(noempty);
38.     }
39.     int a=QueueFront(noempty);
40.     QueuePop(noempty);
41.     return a;
42. }
44. int myStackTop(MyStack* obj) {
45.     if(QueueEmpty(&obj->q1))
46.     {
47.         return QueueBack(&obj->q2);
48.     }
49.     else
50.     {
51.         return QueueBack(&obj->q1);
52.     }
53. }
55. bool myStackEmpty(MyStack* obj) {
56.     return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
57. }
59. void myStackFree(MyStack* obj) {
60.     QueueDestroy(&obj->q1);
61.     QueueDestroy(&obj->q2);
62.     free(obj);
63.     obj=NULL;
64. }

复制代码

 三、括号匹配题目

    这里先给题目链接（有用的括号）
   给定一个只包罗 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有用。
  有用字符串需满足：
  1.左括号必须用相同范例的右括号闭合。
2.左括号必须以正确的序次闭合。
3.每个右括号都有一个对应的相同范例的左括号。
    示例 1：
  输入：s = "()"
输出：true
示例 2：
  输入：s = "()[]{}"
输出：true
示例 3：
  输入：s = "(]"
输出：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.             if(StackEmpty(&st))
13.             return false;
14.             char top=StackTop(&st);
15.             if(top=='('&&*s!=')'||top=='{'&&*s!='}'||top=='['&&*s!=']')
16.             {
17.                 return false;
18.             }
19.             StackPop(&st);
20.         }
21.         s++;
22.     }
23.     if(StackEmpty(&st))
24.     {
25.           return true;
26.     }
27.     return false;
28. }

复制代码

      先对字符串中的括号进行判断，如果是左括号就入栈，如果是右括号就开始匹配，匹配时入过栈中没有数据就说明没有左括号，那么就肯定匹配失败，返回false，如果有数据，就开始判断左括号是否与之对应从而得出结果，不相同就返回false，相同就把栈中的这歌数据删除，继续下一对的判断，直到字符串没有后续字符了，注意：出循环后如果栈中还有数据，那也是匹配失败，说明没有与之对应的右括号。

---

     本篇内容就到这里了，每个题目都给了链接，还是要多练手，希望对各位有帮助。

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。