【C】队列与栈的相互转换

  栈与队列是两种特点相反的数据布局，一个特点是后进先出，一个特点是先辈先出，但是他们之间是可以相互转换的。

---

目次
1  用队列实现栈
1） 标题剖析
2） 算法剖析
（1） 布局(MyStack)
（2） 初始化(myStackCreate)
（3） 入栈(myStackPush)
（4） 出栈(myStackPop)
（5） 取栈顶元素(myStackTop)
（6）判空(myStackEmpty)
（7） 烧毁栈(myStackFree)
3） 代码
2  用栈来实现队列
1） 标题剖析
2） 算法剖析 
3） 代码

---

1  用队列实现栈

leetcode链接

https://leetcode.cn/problems/implement-stack-using-queues/
1） 标题剖析

  请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持平凡栈的全部四种利用（push、top、pop 和 empty）。
我们再来看一下标题中所给的函数：

1. typedef struct {
2.    
3. } MyStack;
5. MyStack* myStackCreate() {
6.    
7. }
9. void myStackPush(MyStack* obj, int x) {
10.    
11. }
13. int myStackPop(MyStack* obj) {
14.    
15. }
17. int myStackTop(MyStack* obj) {
18.    
19. }
21. bool myStackEmpty(MyStack* obj) {
22.    
23. }
25. void myStackFree(MyStack* obj) {
26.    
27. }

复制代码

  显然，这个题是想要让我们通过两个队列来实现一个栈，此中栈具有初始化(myStackCreate)、入栈(myStackPush)、出栈(myStackPop)、取栈顶元素(myStackTop)、判空(myStackEmpty)以及烧毁栈(myStackFree)，只不外这里须要注意是Pop的返回值为int，也就是要返回栈顶元素。

---

2） 算法剖析

  要完成用队列实现栈我们应该充实思量他们俩之间的特点。接下来是我们来看这四个几个函数的实现：

（1） 布局(MyStack)

   标题中说了用两个队列来实现一个栈，以是MyStack内里只须要有两个队列就可以了，我们将这两个队列定名为q1 和 q2。
（2） 初始化(myStackCreate)

  上面的函数要求我们返回一个 MyStack 的指针，以是起首我们须要用 malloc 函数开辟一块 MyStack 的空间，然后初始化该布局内里的两个队列就可以了，末了返回谁人指针即可。
（3） 入栈(myStackPush)

  入栈的时间，我们选择往非空的队列内里入数据，如许会更好的共同出栈的逻辑。
（4） 出栈(myStackPop)

  入栈的时间是不绝向非空的队列内里入数据，以是出栈的时间肯定会有一个空队列，一个非空队列，以是实验出栈利用的时间，我们可以让非空队列除队尾末了一个元素外的数据全都入到空队列里，然后老师存非空队列里的队尾末了一个数据，然后让末了一个数据出队列，返回这个值即可，其过程如图所示：

  通过两个队列之间把数据往返变更，就可以实现数据的后入先出，而且如许也可以包管出栈之后，还是一个空队列和一个非空队列，下一次入栈和出栈的时间也不会出标题。
（5） 取栈顶元素(myStackTop)

  既然入栈的时间有一个空队列和一个非空队列，要取到栈顶元素，也就是末了一个入栈的数据，这里只须要返回非空队列的队尾数据就可以了。
（6）判空(myStackEmpty)

  判空很简朴，只需判断两个队列 q1 和 q2 是否都为空就可以了，假如都为空，那就返回 true，假如都不为空，那就返回 false。
（7） 烧毁栈(myStackFree)

  烧毁栈就是烧毁布局中的两个队列，只须要调用 QueueDestroy 烧毁两个队列就可以了，只不外须要注意的是在初始化的时间开辟了一块 MyStack 的空间，以是末了不要忘记把这块空间也开释掉。

---

3） 代码

1. typedef int QDataType;
2. //定义队列节点的结构
3. typedef struct QueueNode
4. {
5.         QDataType data;
6.         struct QueueNode* next;
7. }QNode;
9. typedef struct Queue
10. {
11.         QNode* phead;//对头 -- 删除数据
12.         QNode* ptail;//队尾 -- 插入数据
13. }Queue;
15. //队列的初始化
16. void QueueInit(Queue* pq)
17. {
18.         assert(pq);
19.         pq->phead = pq->ptail = NULL;
20. }
21. //队列的销毁
22. void QueueDestroy(Queue* pq)
23. {
24.         assert(pq);
25.         QNode* pcur = pq->phead;
26.         while (pcur)
27.         {
28.                 QNode* next = pcur->next;
29.                 free(pcur);
30.                 pcur = next;
31.         }
32.         pq->phead = pq->ptail = NULL;
33. }
34. //入队
35. void QueuePush(Queue* pq, QDataType x)
36. {
37.         assert(pq);
38.         QNode* newnode = (QNode*)malloc(sizeof(QNode));
39.         if (newnode == NULL)
40.         {
41.                 perror("malloc fail!\n");
42.                 exit(1);
43.         }
44.         newnode->data = x;
45.         newnode->next = NULL;
46.         //如果队列为空
47.         if (pq->phead == NULL)
48.         {
49.                 pq->phead = pq->ptail = newnode;
50.         }
51.         else
52.         {
53.                 //队列不为空
54.                 pq->ptail->next = newnode;
55.                 pq->ptail = pq->ptail->next;
56.         }
57. }
58. //判断是否为空
59. bool QueueEmpty(Queue* pq)
60. {
61.         assert(pq);
62.         return pq->phead == NULL;
63. }
65. //出队
66. void QueuePop(Queue* pq)
67. {
68.         assert(pq);
69.         assert(!QueueEmpty(pq));
70.         //如果只有一个节点
71.         if (pq->phead->next == NULL)
72.         {
73.                 free(pq->phead);
74.                 pq->phead = pq->ptail = NULL;
75.         }
76.         else
77.         {
78.                 QNode* next = pq->phead->next;
79.                 free(pq->phead);
80.                 pq->phead = next;
81.         }
82. }
83. //取队尾元素
84. QDataType QueueBack(Queue* pq)
85. {
86.         assert(pq);
87.         assert(!QueueEmpty(pq));
88.         return pq->ptail->data;
89. }
90. //取对头元素
91. QDataType QueueFront(Queue* pq)
92. {
93.         assert(pq);
94.         assert(!QueueEmpty(pq));
95.         return pq->phead->data;
96. }
97. //返回元素个数
98. int QueueSize(Queue* pq)
99. {
100.         assert(pq);
101.         int size = 0;
102.         QNode* pcur = pq->phead;
103.         while (pcur)
104.         {
105.                 size++;
106.                 pcur = pcur->next;
107.         }
108.         return size;
109. }
111. ////////////////////////数据结构队列///////////////////////////
113. typedef struct {
114.     //创建两个队列
115.     Queue q1;
116.     Queue q2;
117. } MyStack;
119. MyStack* myStackCreate()
120. {
121.     MyStack* st = (MyStack*)malloc(sizeof(MyStack));
122.     QueueInit(&(st->q1));
123.     QueueInit(&(st->q2));
124.     return st;
125. }
127. void myStackPush(MyStack* obj, int x)
128. {
129.     //往非空队列里面插入数据
130.     if (!QueueEmpty(&(obj->q1)))
131.     {
132.         QueuePush(&(obj->q1), x);
133.     }
134.     else{
135.         QueuePush(&(obj->q2), x);
136.     }
137. }
139. bool myStackEmpty(MyStack* obj)
140. {
141.     //只要判断两个队列为不为空就可以
142.     return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
143. }
145. int myStackPop(MyStack* obj)
146. {
147.     //把非空队列的除最后一个元素之外的元素入队到另一个队列
148.     Queue* pn = &(obj->q1);
149.     Queue* ph = &(obj->q2);
150.     if (QueueEmpty(&(obj->q2)))
151.     {
152.         pn = &(obj->q2);
153.         ph = &(obj->q1);
154.     }
155.     while (QueueSize(ph) > 1)
156.     {
157.         //入空队列
158.         QueuePush(pn, QueueFront(ph));
159.         //出队
160.         QueuePop(ph);
161.     }
162.     //把最后一个元素出队
163.     int ret = QueueFront(ph);
164.     QueuePop(ph);
165.     return ret;
166. }
168. int myStackTop(MyStack* obj)
169. {
170.     //返回非空队列的队尾元素
171.     if (!QueueEmpty(&(obj->q1)))
172.     {
173.         return QueueBack(&(obj->q1));
174.     }
175.     else
176.     {
177.         return QueueBack(&(obj->q2));
178.     }
179. }
181. void myStackFree(MyStack* obj)
182. {
183.     QueueDestroy(&(obj->q1));   
184.     QueueDestroy(&(obj->q2));
185.     free(obj);
186.     obj = NULL;   
187. }

复制代码

---

2  用栈来实现队列

leetcode链接

https://leetcode.cn/problems/implement-queue-using-stacks/submissions/601751470/
1） 标题剖析

  请你仅使用两个栈实现先入先出队列。队列应当支持一样寻常队列支持的全部利用（push、pop、peek、empty）。
  再来看一下标题中所给的函数：

1. typedef struct {
2.    
3. } MyQueue;
5. MyQueue* myQueueCreate() {
6.    
7. }
9. void myQueuePush(MyQueue* obj, int x) {
10.    
11. }
13. int myQueuePop(MyQueue* obj) {
14.    
15. }
17. int myQueuePeek(MyQueue* obj) {
18.    
19. }
21. bool myQueueEmpty(MyQueue* obj) {
22.    
23. }
25. void myQueueFree(MyQueue* obj) {
26.    
27. }

复制代码

   显然，这个也是像用两个队列实现一个栈一样，是用两个栈来实现一个队列，这个队列包罗以下函数：界说布局(MyQueue)、初始化(myQueueCreate)、入队(myQueuePush)、出队(myQueuePop)、取队头元素(myQueuePeek)、判空(myQueueEmpty) 以及烧毁队列(myQueueFree)。

---

2） 算法剖析 

（1） 布局(MyQueue)
  像用队列实现栈一样，这里也是界说 MyQueue 也是界说两个栈，这里定名为pushst与 popst，一个用来入数据，一个用来出数据。
（2） 初始化(myQueueCreate)
  这里初始化也是让我们返回一个 MyQueue 布局的指针，以是起首先开辟一块 MyQueue 布局巨细的空间，然后让内里的两个栈初始化就可以了。
（3） 入队(myQueuePush)
  入队比力简朴，直接往 pushst 内里插入数据即可。
（4） 出队(myQueuePop)
出队的时间分两种环境：
  a. 假如 popst 不为空，那就直接让 popst 的栈顶元素出栈，然后返回刚才出栈的栈顶元素。
  b. 假如 popst 为空，那就先依次将 pushst的栈顶元素入到 popst 内里，直到 pushst 为空，然后再让 popst 出栈，再返回出栈的栈顶元素。
如先入队1, 2, 3, 4 四个数据，然后出队1，再入队 5 ，再出队 2 的过程如图所示：

  通过先向 pushst 内里入数据，再将 pushst 里的数据入栈到 popst 内里，如许颠末两次先辈后出的调解数据，数据就会变成先辈先出，如上面谁人图，刚开始 pushst 内里由栈顶到栈底的数据为 4,3,2,1，但是入到 popst 内里，栈顶到栈底的数据就变成了1,2,3,4，如许就实现了数据的先入先出。
（5）  取队头元素(myQueuePeek)
  取队头元素是雷同于出栈的过程的，只不外不须要将 popst 的栈顶元素出栈，直接返回 popst 的栈顶数据即可，依然分两种环境：
  a. 假如 popst 不为空，那就直接返回 popst 的栈顶元素。
  b. 假如 popst 为空，那就先依次将 pushst 的栈顶元素入到 popst 内里，直到 pushst 为空，然后返回 popst 的栈顶元素。
（6）  判空(myQueueEmpty)
  判空和用队列实现栈一样，判断 MyQueue 内里的两个栈是否同时为空即可，假如都为空，那么返回 true；假如不为空，那么返回 false。
（7）  烧毁队列(myQueueFree)
  烧毁队列也只需烧毁底层的两个栈 pushst 和 popst 即可，只不外须要注意要让开辟出的 MyQueue 的那一块空间也开释掉，才不会出现内存走漏的环境。

---

3） 代码

1. typedef int STDataType;
2. //定义栈的结构--用数组来实现
3. typedef struct Stack
4. {
5.         STDataType* arr;
6.         int top;//指向栈顶
7.         int capacity;//容量
8. }Stack;
10. //初始化
11. void StackInit(Stack* ps)
12. {
13.         assert(ps);
14.         ps->arr = NULL;
15.         ps->capacity = ps->top = 0;
16. }
17. //销毁
18. void StackDestroy(Stack* ps)
19. {
20.         assert(ps);
21.         if (ps->arr)
22.                 free(ps->arr);
23.         ps->capacity = ps->top = 0;
24. }
25. //入栈
26. void StackPush(Stack* ps, STDataType x)
27. {
28.         assert(ps);
29.         if (ps->top == ps->capacity)
30.         {
31.                 //增容
32.                 int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
33.                 STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * newCapacity);
34.                 if (tmp == NULL)
35.                 {
36.                         perror("realloc fail!\n");
37.                         exit(1);
38.                 }
39.                 ps->arr = tmp;
40.                 ps->capacity = newCapacity;
41.         }
42.         ps->arr[ps->top++] = x;
43. }
44. //判空
45. bool StackEmpty(Stack* ps)
46. {
47.         assert(ps);
48.         return ps->top == 0;
49. }
50. //出栈
51. void StackPop(Stack* ps)
52. {
53.         assert(ps);
54.         assert(!StackEmpty(ps));
55.         ps->top--;
56. }
58. //取栈顶元素
59. STDataType StackTop(Stack* ps)
60. {
61.         assert(!StackEmpty(ps));
62.         return ps->arr[ps->top - 1];
63. }
64. //有效元素个数
65. int StackSize(Stack* ps)
66. {
67.         assert(ps);
69.         return ps->top;
70. }
72. ////////////////////////////////数据结构栈/////////////////////////////////////////////
74. typedef struct {
75.     //定义两个栈，一个用来当做入队的队列，另一个当做出队的队列
76.     Stack pushst;
77.     Stack popst;
78. } MyQueue;
80. MyQueue* myQueueCreate()
81. {
82.     MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
83.     if (q == NULL)
84.     {
85.         perror("malloc fail！\n");
86.         exit(1);
87.     }
88.     //初始化队列中的两个栈
89.     StackInit(&q->pushst);
90.     StackInit(&q->popst);
91.     return q;
92. }
94. void myQueuePush(MyQueue* obj, int x)
95. {
96.     //将数据往入队的栈里面入栈
97.     StackPush(&obj->pushst, x);
98. }
100. int myQueuePop(MyQueue* obj)
101. {
102.     //如果出队的栈为空，那就把入队的栈的数据全部入栈到出队的栈   
103.     if (StackEmpty(&obj->popst))
104.     {
105.         while (StackSize(&obj->pushst) > 0)
106.         {
107.             //取栈顶元素
108.             STDataType tmp = StackTop(&obj->pushst);
109.             //出栈
110.             StackPop(&obj->pushst);
111.             //入栈
112.             StackPush(&obj->popst, tmp);
113.         }
114.     }
115.     STDataType ret = StackTop(&obj->popst);
116.     StackPop(&obj->popst);
117.     return ret;
118. }
120. int myQueuePeek(MyQueue* obj)
121. {
122.     //如果出队的栈为空，那就把入队的栈的数据全部入栈到出队的栈   
123.     if (StackEmpty(&obj->popst))
124.     {
125.         while (StackSize(&obj->pushst) > 0)
126.         {
127.             //取栈顶元素
128.             STDataType tmp = StackTop(&obj->pushst);
129.             //出栈
130.             StackPop(&obj->pushst);
131.             //入栈
132.             StackPush(&obj->popst, tmp);
133.         }
134.     }
135.     //不需要出队就可以
136.     STDataType ret = StackTop(&obj->popst);
137.     return ret;
138. }
140. bool myQueueEmpty(MyQueue* obj)
141. {
142.     //如果连个栈都为空，那么队列就为空
143.     return StackEmpty(&obj->popst) && StackEmpty(&obj->pushst);
144. }
146. void myQueueFree(MyQueue* obj)
147. {
148.     //销毁两个栈就可以
149.     if (!StackEmpty(&obj->popst))
150.     {
151.         StackDestroy(&obj->popst);
152.     }
153.     if (!StackEmpty(&obj->pushst))
154.     {
155.         StackDestroy(&obj->pushst);
156.     }
157.     //最后别忘了释放obj
158.     free(obj);
159.     obj = NULL;
160. }

复制代码

---

  通过栈与队列的相互转换，信赖各人对于栈和队列的明确会更加深入。