扬帆启航于数据结构算法之雅舟旅程，悠然漫步于C++秘境——Leetcode刷题之 ...

   人无完人，持之以恒，方能见真我！！！
共同进步！！
  
  
一、用栈实现队列

   题目链接：用栈实现队列
    还是先来看看题目形貌:
  

1.大抵思绪分析

   题目的大抵寄义就是要求我们使用两个栈模拟实现一个队列，要求要支持一个队列的基本操作，这些操作大抵都写在上面说明白，关键我们要构思一下怎么用两个栈实现队列的操作
    我们都知道栈的特点是先进后出，而队列是先进先出，刚好是相反的，是不是可以从这个方面下手，一个栈和队列是相反的，那么两个栈反复倒腾呢？是不是就能“负负得正”？我们画图来实践一下：
    题目的大抵寄义就是要求我们使用两个栈实现一个队列，要求要支持一个队列的基本操作，这些操作大抵都写在上面说明白，关键我们要构思一下怎么用两个栈实现队列的操作
  

   根据上面我们画的图例，发现我们的想法确实奏效，固然一个栈和队列的性子刚好相反，但是经过两个栈的倒腾，刚好负负得正，实现先进先出
    但是上面也只是我们的大抵思绪，我们只讨论了第一次入队列的情况，那么下一次我们入队列要把数据放在哪个栈中呢？
    很显着就是栈1，因为栈2现在的顺序是正确的，只要正常的出栈，那么就可以模拟出队列的顺序，所以不能扰乱栈2的顺序
    所以我们可以得出，栈1就是我们用来入队列，而栈2则负责出队列操作，当栈2的元素已经出完之后，我们就可以再次把栈1的全部元素再放进栈2，然后再由栈2来出队列，栈1来入队列，如此循环就基本实现了队列的功能，接下来我们就一个函数一个函数分析：
  2.用栈实现队列的结构以及初始化

   这个新队列的结构在题目中也已经提到，就是两个栈，所以我们定义两个栈作为这个新队列的结构，但是我们留意，根据刚刚的分析我们知道，其中一个栈用来入队列，另一个专门用来出队列，所以我们可以取stpush和stpop来进行分辨，如下：

1. typedef struct
2. {
3.     ST stpush;
4.     ST stpop;
5. } MyQueue;

复制代码

  初始化方法也很简单，就是我们申请一个这样的节点大小的空间，然后分别调用栈的初始化函数来对两个栈初始化，如下：

1. MyQueue* myQueueCreate()
2. {
3.     myQueue* pq = (myQueue*)malloc(sizeof(myQueue));
4.     if(pq == NULL)
5.     {
6.         perror("malloc fail\n");
7.         return NULL;
8.     }
9.     STInit(&pq->stpush);//初始化栈1
10.     STInit(&pq->stpop); //初始化栈2
11.     return pq;
12. }

复制代码

3.入队列

   在之前我们分析过，两个栈中stpush这个栈用来专门入数据，也就是入队列，所以我们在入队列函数中直接将数据入到stpush栈中，如下：

1. void myQueuePush(MyQueue* obj, int x)
2. {
3.     STPush(&obj->stpush,x);//入栈1，入队列
4. }

复制代码

4.出队列并返回原队头元素

   stpop栈用来专门出队列的，实现出队列的逻辑就是，如果stpop栈不为空，那么我们直接就先保存；原队头元素，然后让stpop出栈，然后返回保存的队头
    但是如果stpop栈为空，我们就需要先把stpush栈中的元素全部放到stpop栈中，放完之后再进行上面的操作，如下：

1. int myQueuePop(MyQueue* obj)
2. {
3.     if(STEmpty(&obj->stpop))//如果出队列栈为空，就循环入栈
4.     {
5.         while(!STEmpty(&obj->stpush))//将入队列栈全部移入stpop
6.         {
7.             int top = STTop(&obj->stpush);//取出栈1的栈顶元素压栈
8.             STPop(&obj->stpush);
9.             STPush(&obj->stpop,top);//压入栈2
10.         }
11.     }
12.     //通过上面的压栈，stpop栈中已有元素，此时可以出栈
13.     //栈不为空
14.     int top = S TTop(&obj->stpop);
15.     STPop(&obj->stpop);
16.     return top;
17. }

复制代码

5.返回队头元素

   返回队头元素的逻辑跟上面的出队列操作差不多，如果stpop不为空那么直接返回栈顶元素（队头元素），如果stpop为空那么就先把stpush中的元素移动到stpop栈中，然后再去返回栈顶元素
跟上面出栈操作的唯一区别就是不消出栈，只用去取栈顶元素，如下：

1. int myQueuePeek(MyQueue* obj)
2. {
3.     if(STEmpty(&obj->stpop))//如果出队列栈为空，就循环入栈
4.     {
5.         while(!STEmpty(&obj->stpush))//将入队列栈全部移入stpop
6.         {
7.             int top = STTop(&obj->stpush);//取出栈1的栈顶元素压栈
8.             STPop(&obj->stpush);
9.             STPush(&obj->stpop,top);//压入栈2
10.         }
11.     }
12.     return STTop(&obj->stpop);
13. }

复制代码

6.队列判空和队列销毁

   我们用两个栈实现的队列要判空的话，必须保证两个栈同时为空队列才为空，否则就不是空，如下：

1. bool myQueueEmpty(MyQueue* obj)
2. {
3.     return STEmpty(&obj->stpush) && STEmpty(&obj->stpop);
4. }

复制代码

  队列销毁的本质也就是销毁内里的两个栈，但是由于我们的MyQueue这个指针也是我们动态申请的，也要开释掉，然后置空，如下：

1. void myQueueFree(MyQueue* obj)
2. {
3.     STDestroy(&obj->stpush);
4.     STDestroy(&obj->stpop);
5.     free(obj);
6.     obj = NULL;
7. }

复制代码

7.完整题解代码

   那么关于栈的代码，各人就可以自行拷贝了，在这里拷贝也显得冗余了

1. typedef struct //定义两个栈的结构{   ST stpush;   ST stpop;} MyQueue;MyQueue* myQueueCreate() {    myQueue* pq = (myQueue*)malloc(sizeof(myQueue));    if(pq == NULL)    {        perror("malloc fail\n");        return NULL;    }    STInit(&pq->stpush);//初始化栈1    STInit(&pq->stpop); //初始化栈2}void myQueuePush(MyQueue* obj, int x)
2. {
3.     STPush(&obj->stpush,x);//入栈1，入队列
4. }
5. int myQueuePop(MyQueue* obj)
6. {
7.     if(STEmpty(&obj->stpop))//如果出队列栈为空，就循环入栈
8.     {
9.         while(!STEmpty(&obj->stpush))//将入队列栈全部移入stpop
10.         {
11.             int top = STTop(&obj->stpush);//取出栈1的栈顶元素压栈
12.             STPop(&obj->stpush);
13.             STPush(&obj->stpop,top);//压入栈2
14.         }
15.     }
16.     //通过上面的压栈，stpop栈中已有元素，此时可以出栈
17.     //栈不为空
18.     int top = S TTop(&obj->stpop);
19.     STPop(&obj->stpop);
20.     return top;
21. }
22. int myQueuePeek(MyQueue* obj)
23. {
24.     if(STEmpty(&obj->stpop))//如果出队列栈为空，就循环入栈
25.     {
26.         while(!STEmpty(&obj->stpush))//将入队列栈全部移入stpop
27.         {
28.             int top = STTop(&obj->stpush);//取出栈1的栈顶元素压栈
29.             STPop(&obj->stpush);
30.             STPush(&obj->stpop,top);//压入栈2
31.         }
32.     }
33.     return STTop(&obj->stpop);
34. }
35. bool myQueueEmpty(MyQueue* obj)
36. {
37.     return STEmpty(&obj->stpush) && STEmpty(&obj->stpop);
38. }
39. void myQueueFree(MyQueue* obj)
40. {
41.     STDestroy(&obj->stpush);
42.     STDestroy(&obj->stpop);
43.     free(obj);
44.     obj = NULL;
45. }

复制代码

二、用队列实现栈

   题目链接：用队列实现栈
还是先来看看题目：
  

1.大抵思绪分析

   这道题和上道题类似，就是使用两个队列实现一个栈的各种操作，这道题要比上一题难，因为在上一题中，我们的思绪就是“负负得正”，通过两个栈的互相倒腾就可以还原队列的入队列出队列操作，但是这题不行，我们画个图看看：
  

   根据上图的分析，我们知道了完全使用上一题的思绪行不通，因为栈通过两次倒腾后，内里的元素顺序会反过来，但是队列通过两次倒腾后，内里元素的顺序还是稳定
    所以我们要换个思绪，我们先来看看出栈的思绪： 我们把数据入到队列1中，然后移动到队列2时，不全部挪已往，只留下一个，如图：
  

   这个时间我们发现队列1中留下的，对应到栈上不正是我们的栈顶元素吗？我们在出栈的时间就可以把队列1中剩下的一个元素出队列，4是最后入栈的，最后第一个出栈，符合我们栈的性子
    那么为了保险起见，我们再试一次，先假设我们实现的栈出栈一次，就是把4删掉，让剩下的1,2,3再来模拟一次出栈，如图：
  

   此时我们发现队列2中留下的恰好是新的栈顶元素，让队列2出队列就刚好对应了出栈操作，所以我们的出栈思绪大抵是正确的
    但是我们发现，队列1和队列2是反复倒腾的，没有哪个是专门出栈，哪个专门入栈的，所以我们接下来要分清怎么判断哪个队列什么时间用来入栈，什么时间用来出栈
    经过规律总结我们发现，当我们要出栈的时间，有一个队列总是空着的，另一个队列内里才装有数据，我们在操作时就是让不为空的队列将size-1个元素挪到空队列内里去，然后不为空的队列就只剩下一个元素出队列即可模拟实现出栈
    那么我们入栈的时间，就是往不为空的队列中去入，所以我们在写入栈和出栈操作时最重要的就时判断出哪个队列空，哪个队列不为空，才方便进行操作，那么接下来我们就一个函数一个函数分析
  2.用队列实现栈的结构和初始化

   既然题目明白要求我们用两个队列实现一个栈，所以栈的结构实际上就是两个队列，如下：

1. typedef struct
2. {
3.     Queue q1;//队列1
4.     Queue q2;//队列2
5. } MyStack;

复制代码

  初始化也很简单，起首动态开发一个MyStack大小的空间，然后就只需要调用队列的初始化方法分别初始化两个队列即可，如下：

1. MyStack* myStackCreate()
2. {
3.     MyStack* st = (MyStack*)malloc(sizeof(MyStack));
4.     if(st == NULL)
5.     {
6.         perror("malloc fail\n");
7.         return NULL;
8.     }
9.     QueueInit(&st->q1);
10.     QueueInit(&st->q2);
11.     return st;
12. }

复制代码

3.入栈

   我们刚刚分析过了，我们入栈就是往不为空的队列中去入，所以我们在入栈时只需要判断一下哪个栈不为空即可，如下：

1. void myStackPush(MyStack* obj, int x)
2. {
3.     //往不是空栈的栈中放数据,如果都是空那么无所谓
4.     if(!QueueEmpty(&obj->q1))
5.     {
6.         QueuePush(&obj->q1,x);
7.     }
8.     else
9.     {
10.         QueuePush(&obj->q2,x);
11.     }
12. }

复制代码

4.出栈

   我们的出栈操作刚刚也重点分析了，就是先找出哪个是空队列，哪个是非空队列，然后将非空队列中size-1个数据挪动到空队列中，然后非空队列剩下的一个元素就是我们要出栈的元素，题目要求出栈前返回栈顶元素，所以我们创建一个变量用来保存栈顶元素，最后用来返回即可，如下：

1. int myStackPop(MyStack* obj)
2. {
3.     //先假设q1是空队列，q2是非空队列
4.     Queue* empty = &obj->q1;
5.     Queue* noempty = &obj->q2;
6.     //如果q1非空，那么q2就是空队列，q1为非空队列
7.     if(!QueueEmpty(&obj->q1))
8.     {
9.         empty = &obj->q2;
10.         noempty = &obj->q1;
11.     }
12.     //找到非空队列要移动的size-1的大小
13.     int sum = QueueSize(noempty) - 1;
14.     //找到大小后，循环移动
15.     while(sum--)
16.     {
17.         //取出队头元素放入空队列
18.         int top = QueueFront(noempty);
19.         QueuePop(noempty);
20.         QueuePush(empty,top);
21.     }
22.     //最后保存非空队列剩余的栈顶元素，就可以出栈了
23.     int top = QueueFront(noempty);
24.     QueuePop(noempty);
25.     return top;
26. }

复制代码

5.取栈顶元素

   按照我们上面的思想，取栈顶元素其实就是取非空队列中的队尾元素，如下：

1. int myStackTop(MyStack* obj)
2. {
3.     //取栈顶元素，其实就是返回非空队列的队尾元素
4.     if(!QueueEmpty(&obj->q1))
5.     {
6.         return QueueBack(&obj->q1);
7.     }
8.     else
9.     {
10.         return QueueBack(&obj->q2);
11.     }
12. }

复制代码

6.判空和销毁栈

   只有两个队列同时为空，我们的栈才为空，如下：

1. bool myStackEmpty(MyStack* obj)
2. {
3.      return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
4. }

复制代码

  销毁栈就只需要调用队列的销毁函数，分别销毁掉两个队列即可，不要忘了最后把整个栈的结构也销毁掉，如下：

1. void myStackFree(MyStack* obj)
2. {
3.     QueueDestroy(&obj->q1);
4.     QueueDestroy(&obj->q2);
5.     free(obj);
6.     obj = NULL;
7. }

复制代码

7.完整题解

1. typedef int QDataType;//队列中一个节点的定义//看起来和链表差不多//但是要留意这里它已经酿成队列的节点了typedef struct QueueNode{        QDataType data;        struct QueueNode* next;}QueueNode;//真正使用的对列的定义typedef struct Queue{        int size;        //指向队头的指针        QueueNode* phead;        //指向队尾的指针        QueueNode* ptail;}Queue;//队列的初始化void QueueInit(Queue* pq){        assert(pq);        pq->size = 0;        pq->phead = pq->ptail = NULL;//首尾置空}//队列的销毁void QueueDestroy(Queue* pq){        assert(pq);        QueueNode* pcur = pq->phead;        while (pcur)//循环置空        {                QueueNode* del = pcur;//保存开释节点                pcur = pcur->next;                free(del);                del = NULL;        }        pq->phead = pq->ptail = NULL;        pq->size = 0;}//队列的节点申请QueueNode* QueueBuyNode(QDataType x){        QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));        if (newnode == NULL)        {                perror("malloc fail\n");                return NULL;        }        newnode->data = x;        newnode->next = NULL;        return newnode;}//入队列void QueuePush(Queue* pq, QDataType x){        assert(pq);        QueueNode* newnode = QueueBuyNode(x);        //如果队列中没有节点        if (pq->phead == NULL)        {                pq->phead = pq->ptail = newnode;                 pq->size++;                return;        }        //队列中已有节点        pq->ptail->next = newnode;//链接        pq->ptail = newnode;//更新尾结点        pq->size++;}//队列判空bool QueueEmpty(Queue* pq){        assert(pq);        return pq->phead == NULL;}//出队列void QueuePop(Queue* pq){        assert(!QueueEmpty(pq));        QueueNode* next = pq->phead->next;        free(pq->phead);        pq->phead = next;        pq->size--;}//取队头元素QDataType QueueFront(Queue* pq){        assert(pq);        return pq->phead->data;}//取队尾元素QDataType QueueBack(Queue* pq){        assert(pq);        return pq->ptail->data;}//队列的有效元素个数int QueueSize(Queue* pq){        assert(pq);        return pq->size;}typedef struct
2. {
3.     Queue q1;//队列1
4.     Queue q2;//队列2
5. } MyStack;
6. MyStack* myStackCreate()
7. {
8.     MyStack* st = (MyStack*)malloc(sizeof(MyStack));
9.     if(st == NULL)
10.     {
11.         perror("malloc fail\n");
12.         return NULL;
13.     }
14.     QueueInit(&st->q1);
15.     QueueInit(&st->q2);
16.     return st;
17. }
18. void myStackPush(MyStack* obj, int x)
19. {
20.     //往不是空栈的栈中放数据,如果都是空那么无所谓
21.     if(!QueueEmpty(&obj->q1))
22.     {
23.         QueuePush(&obj->q1,x);
24.     }
25.     else
26.     {
27.         QueuePush(&obj->q2,x);
28.     }
29. }
30. int myStackPop(MyStack* obj)
31. {
32.     //先假设q1是空队列，q2是非空队列
33.     Queue* empty = &obj->q1;
34.     Queue* noempty = &obj->q2;
35.     //如果q1非空，那么q2就是空队列，q1为非空队列
36.     if(!QueueEmpty(&obj->q1))
37.     {
38.         empty = &obj->q2;
39.         noempty = &obj->q1;
40.     }
41.     //找到非空队列要移动的size-1的大小
42.     int sum = QueueSize(noempty) - 1;
43.     //找到大小后，循环移动
44.     while(sum--)
45.     {
46.         //取出队头元素放入空队列
47.         int top = QueueFront(noempty);
48.         QueuePop(noempty);
49.         QueuePush(empty,top);
50.     }
51.     //最后保存非空队列剩余的栈顶元素，就可以出栈了
52.     int top = QueueFront(noempty);
53.     QueuePop(noempty);
54.     return top;
55. }
56. int myStackTop(MyStack* obj)
57. {
58.     //取栈顶元素，其实就是返回非空队列的队尾元素
59.     if(!QueueEmpty(&obj->q1))
60.     {
61.         return QueueBack(&obj->q1);
62.     }
63.     else
64.     {
65.         return QueueBack(&obj->q2);
66.     }
67. }
68. bool myStackEmpty(MyStack* obj)
69. {
70.      return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
71. }
72. void myStackFree(MyStack* obj)
73. {
74.     QueueDestroy(&obj->q1);
75.     QueueDestroy(&obj->q2);
76.     free(obj);
77.     obj = NULL;
78. }

复制代码

  OK，那么本日的刷题也就到这里了，咱们下一篇再见啦~~

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