数据结构刷题训练队列实现栈

前言

        我们已经学习了栈和队列，也都实现了它们各自的底层接口，那么接下我们就要开始栈和队列的专项刷题训练。

---

1. 题目：使用队列实现栈

题目描述：

 题目链接：

队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/

 2. 思路

        队列的结构是先进先出，题目的要求是，让我们利用队列的底层接口来实现栈，不可以改变队列的底层逻辑，所以如果你的思路是逆置队列这个链表，那这个思路就被pass掉了。

         那我们要如何利用队列尾进头出的特性来实现栈的尾进尾出呢？题目中给了我们两个队列，我们要使用这两个队列实现栈。

        入栈操作好说，问题在于出栈问题，思路是这样的：我们有两个队列，一个队列用于存储数据，另外一个队列（空队列）用于拷贝数据，将原队列的前n-1个数据拷贝到空队列中，然后再将原队列剩余的最后一个元素出队列，这样就模拟实现了栈的尾出。

" alt="学新通" title="学新通" origin-src="https://blog.csdn.net/2202_75605090/article/details/" data-src="">" alt="学新通" title="学新通" origin-src="https://blog.csdn.net/2202_75605090/article/details/" data-src="">

3. 分析 

         根据上述的思路分析，队列实现栈，入栈不需要什么特殊操作例如我们入栈：1、2、3、4、5，出栈呢就是：5、4、3、2、1。

        上述的思路已经介绍了解决办法，也是非常简单的，但有人可能会问：那这样算法的效率岂不是很低？这种方法的效率确实低，但是这道题目考察的并不是效率的问题，而实性质问题，这也是一道经典的面试题目。这道题目并不难，但它考察对数据结构的理解，各各接口的实现中有很多需要注意的细节。

        首先这道题目是并没有给现成的队列，使用C语言解决需要我们现成造轮子，这也是C语言刷题的弊端，有很多题目都需要造轮子。那么这里我们就可以直接复制前边我们实现的队列。

 接下来就是我们开始注意实现接口：

         首先题目中给了我们两个队列，为了便于传参和使用，我们可以定义一个结构体：

1.  
   typedef struct {
2.  
   Que q1; //注意这里定于的队列类型一定要与自己定义的队列结构体类型对应
3.  
   Que q2;
4.  
   } MyStack;

 这里我们在前边介绍结构体时提到过，匿名结构体。

 3.1 创建栈

1.  
   MyStack* myStackCreate() {
2.  
    
3.  
   }

 题目给出的接口如上，那这里我们要怎么创建我们的栈呢？是这样吗？

1.  
   MyStack* myStackCreate() {
2.  
    
3.  
   MyStack st;
4.  
    
5.  
   //…
6.  
    
7.  
   return &st;
8.  
   }

         对函数和指针比较熟悉的同学可能就已经发现不行，为什么不行？这里就牵扯到了函数相关的知识，函数内创建的变量都是存储在栈区，出了函数就会被销毁，内存已经被销毁，返回指针还有什么意义呢？所以这里需要使用malloc函数，动态内存分配开辟的空间在堆区，程序结束前不主动释放就一直存在。所以上述的创建变量的方法不可取。

正确的方法：

1.  
   MyStack* myStackCreate() {
2.  
   MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
3.  
   QueueInit(&pst->q1);
4.  
   QueueInit(&pst->q2);
5.  
    
6.  
   return pst;
7.  
   }

         这里的pst->q1,就等价于我们在创建的队列的结构体变量：Que q；在调用接口时需要传地址过去。

3.2入栈

        接下来就是入栈，题目中给了我们两个队列，为了后续出栈操作我们需要确保一个队列为空，用于拷贝数据，所以我们入栈时需要在不为空的队列入。

1.  
   void myStackPush(MyStack* obj, int x) {
2.  
   if(!IsEmpty(&obj->q1))
3.  
   {
4.  
   QueuePush(&obj->q1,x);
5.  
   }
6.  
   else
7.  
   {
8.  
   QueuePush(&obj->q2,x);
9.  
   }
10.  
    }

如果两个都为空那就随便选一个都可以。

3.3 出栈

        在进行出栈操作的时候，我们需要判断哪一个队列为空，然后将非空队列的前n-1个元素依次拷贝到空队列当中。这里我们可以先假设队列1为空，然后在判断队列1是否为空，如果不为空那就是队列2为空，进行修改。这个假设的方法还是很实用的。

 拷贝过程如下：

        注意这里是拷贝，不是将原队列的节点插入到空队列，而是通过队头数据这个函数接口来将数据传过去，然后入队（调用入队接口），入队之后及时更新队头（出队）。

 

1.  
   int myStackPop(MyStack* obj) {
2.  
   Que* Empty=&obj->q1;
3.  
   Que* NoEmpty=&obj->q2;
4.  
   if(!IsEmpty(&obj->q1))
5.  
   {
6.  
   Empty=&obj->q2;
7.  
   NoEmpty=&obj->q1;
8.  
   }
9.  
   while(QueueSize(NoEmpty)>1)
10.  
    {
11.  
    QueuePush(Empty,QueueFront(NoEmpty));
12.  
    QueuePop(NoEmpty);
13.  
    }
14.  
    int top=QueueFront(NoEmpty);//最后保存非空队列最后一个队列节点的数据，便于返回
15.  
    QueuePop(NoEmpty); //最后一个元素出队。
16.  
    return top;
17.  
    }

 3.4 栈顶数据

         栈顶数据接口实现就简单了，我们前边对队列进行实现时，有队头和队尾数据的接口，我们可以直接调用。

1.  
   int myStackTop(MyStack* obj) {
2.  
   if(!IsEmpty(&obj->q1))
3.  
   {
4.  
   return QueueBlack(&obj->q1);
5.  
   }
6.  
   else
7.  
   {
8.  
   return QueueBlack(&obj->q2);
9.  
   }
10.  
    }

 3.5 判空和 “ 栈 ” 的销毁

         判空就很简单，如果两个队列都为空，那么这个 “ 栈 ” 也就为空。

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

         “ 栈 ”的销毁，这里就不能直接free掉obj了，如果直接释放那我们程序中的两个队列就会丢失无法释放，所以在释放掉obj之前，我们需要先将两个队列销毁。

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

 4. 题解

 完整代码如下：

1.  
   typedef int Datatype;
2.  
   typedef struct QueueNode
3.  
   {
4.  
   struct QueueNode* next;
5.  
   Datatype data;
6.  
   }QueueNode;
7.  
   typedef struct Queue
8.  
   {
9.  
   QueueNode* head;
10.  
    QueueNode* tail;
11.  
    int size;
12.  
    }Que;
13.  
    //初始化队列
14.  
    void QueueInit(Que* pq);
15.  
    //入队
16.  
    void QueuePush(Que* pq, Datatype x);
17.  
    //出队
18.  
    void QueuePop(Que* pq);
19.  
    //队头数据
20.  
    Datatype QueueFront(Que* pq);
21.  
    //队尾数据
22.  
    Datatype QueueBlack(Que* pq);
23.  
    //判空
24.  
    bool IsEmpty(Que* pq);
25.  
    //队列大小
26.  
    int QueueSize(Que* pq);
27.  
    //销毁队列
28.  
    void DestoryQueue(Que* pq);
29.  
     
30.  
    void QueueInit(Que* pq)
31.  
    {
32.  
    assert(pq);
33.  
    pq->head = pq->tail = NULL;
34.  
    pq->size = 0;
35.  
    }
36.  
    void QueuePush(Que* pq, Datatype x)
37.  
    {
38.  
    assert(pq);
39.  
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
40.  
    if (newnode == NULL)
41.  
    {
42.  
    perror("malloc");
43.  
    exit(-1);
44.  
    }
45.  
    newnode->data = x;
46.  
    newnode->next = NULL;
47.  
    if (pq->tail == NULL)
48.  
    {
49.  
    pq->head = pq->tail = newnode;
50.  
    }
51.  
    else
52.  
    {
53.  
    pq->tail->next = newnode;
54.  
    pq->tail = newnode;
55.  
     
56.  
    }
57.  
    pq->size ;
58.  
    }
59.  
    void QueuePop(Que* pq)
60.  
    {
61.  
    assert(pq);
62.  
    assert(!IsEmpty(pq));
63.  
     
64.  
    if (pq->head->next == NULL)
65.  
    {
66.  
    free(pq->head);
67.  
    pq->head = pq->tail = NULL;
68.  
    }
69.  
    else
70.  
    {
71.  
    QueueNode* next = pq->head->next;
72.  
    free(pq->head);
73.  
    pq->head = next;
74.  
     
75.  
    }
76.  
    pq->size--;
77.  
    }
78.  
    Datatype QueueFront(Que* pq)
79.  
    {
80.  
    assert(pq);
81.  
    assert(!IsEmpty(pq));
82.  
     
83.  
    return pq->head->data;
84.  
    }
85.  
    Datatype QueueBlack(Que* pq)
86.  
    {
87.  
    assert(pq);
88.  
    assert(!IsEmpty(pq));
89.  
    return pq->tail->data;
90.  
    }
91.  
    bool IsEmpty(Que* pq)
92.  
    {
93.  
    assert(pq);
94.  
    return (pq->head == NULL);
95.  
    }
96.  
    int QueueSize(Que* pq)
97.  
    {
98.  
    assert(pq);
99.  
    return pq->size;
100.  
     }
101.  
     void DestoryQueue(Que* pq)
102.  
     {
103.  
     assert(pq);
104.  
     QueueNode* cur = pq->head;
105.  
     while (cur)
106.  
     {
107.  
     QueueNode* next = cur->next;
108.  
     free(cur);
109.  
     cur = next;
110.  
     }
111.  
     pq->head = pq->tail = NULL;
112.  
     pq->size = 0;
113.  
     }
114.  
     typedef struct {
115.  
     Que q1;
116.  
     Que q2;
117.  
     } MyStack;
118.  
      
119.  
      
120.  
     MyStack* myStackCreate() {
121.  
     MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
122.  
     QueueInit(&pst->q1);
123.  
     QueueInit(&pst->q2);
124.  
      
125.  
     return pst;
126.  
     }
127.  
      
128.  
     void myStackPush(MyStack* obj, int x) {
129.  
     if(!IsEmpty(&obj->q1))
130.  
     {
131.  
     QueuePush(&obj->q1,x);
132.  
     }
133.  
     else
134.  
     {
135.  
     QueuePush(&obj->q2,x);
136.  
     }
137.  
     }
138.  
      
139.  
     int myStackPop(MyStack* obj) {
140.  
     Que* Empty=&obj->q1;
141.  
     Que* NoEmpty=&obj->q2;
142.  
     if(!IsEmpty(&obj->q1))
143.  
     {
144.  
     Empty=&obj->q2;
145.  
     NoEmpty=&obj->q1;
146.  
     }
147.  
     while(QueueSize(NoEmpty)>1)
148.  
     {
149.  
     QueuePush(Empty,QueueFront(NoEmpty));
150.  
     QueuePop(NoEmpty);
151.  
     }
152.  
     int top=QueueFront(NoEmpty);
153.  
     QueuePop(NoEmpty);
154.  
     return top;
155.  
     }
156.  
      
157.  
     int myStackTop(MyStack* obj) {
158.  
     if(!IsEmpty(&obj->q1))
159.  
     {
160.  
     return QueueBlack(&obj->q1);
161.  
     }
162.  
     else
163.  
     {
164.  
     return QueueBlack(&obj->q2);
165.  
     }
166.  
     }
167.  
      
168.  
     bool myStackEmpty(MyStack* obj) {
169.  
     return (IsEmpty(&obj->q1)&&IsEmpty(&obj->q2));
170.  
     }
171.  
      
172.  
     void myStackFree(MyStack* obj) {
173.  
     DestoryQueue(&obj->q1);
174.  
     DestoryQueue(&obj->q2);
175.  
      
176.  
     free(obj);
177.  
     }

---

总结

        本文队列模拟实现栈，让我们在实践中深入思考了数据结构的本质和应用，为我们的编程能力和问题解决能力提供了锻炼。本期内容到此结束，感谢阅读！

这篇好文章是转载于：学新通技术网