【数据布局初阶】队列接口实现及用队列实现栈超详解 ...

---

1. 概念

概念：只答应在一端举行插入数据操作，在另一端举行删除数据操作的特殊线性表，队列具有先进先出FlFO(First In First Out)的特点。
入队列：举行插入操作的一端称为队尾。
出队列：举行删除操作的一端称为队头。

1. 1 队列底层布局选型

和栈一样，队列也可以数组和链表的布局实现，但是使用链表的布局实现更优一些，因为队列需要在队头出数据，如果使用数组的布局，出队列就是在数组头上出数据，服从会比较低。
1. 2 队列界说

既然使用链表实现队列，那么栈就应该有两个自界说布局，一个是节点布局体，一个是整个队列的布局体。

1. //队列节点
2. typedef int QDataType;
3. typedef struct QListNode
4. {
5.         struct QListNode* next;
6.         QDataType data;
7. }QNode;
9. // 队列的结构
10. typedef struct Queue
11. {
12.         QNode* head;
13.         QNode* tail;
14.         int size;
15. }Queue;

复制代码

队列节点和平凡的单链表节点是一样的，而队列的布局中，需要保存队列的头和尾，方便举行出队列和入队列，除此之外还要保存队列中元素的个数。
2. 接口实现

2. 1 初始化

1. void QueueInit(Queue* q);

复制代码

我们依然接纳先在main函数中创建队列，再在初始化函数中举行初始化处置惩罚的方式，缘故原由已经在栈的实现讲解过了。
对一个Queue类型的布局体举行初始化，就是将所有的元素置为NULL或0就可以了。

1. void QueueInit(Queue* q)
2. {
3.         assert(q);
4.         q->head = NULL;
5.         q->tail = NULL;
6.         q->size = 0;
7. }

复制代码

2. 2 判空

判定队列是不是为空，接下来的几个函数会用到这个接口。
只需要判定头节点或者尾节点是否为空就可以了。

1. int QueueEmpty(Queue* q)
2. {
3.         assert(q);
4.         return q->head == NULL;
5. }

复制代码

2. 3 入队列

入队列是在队尾入队列，有以下几个步调：

• 申请新节点。
  
• 将其接到原来的尾节点的后面，并将尾节点指向新节点。
  
• size++
  

1. void QueuePush(Queue* q, QDataType data)
2. {
3.         assert(q);
4.         //1. 申请新节点
5.         QNode* newnode = (QNode*)malloc(sizeof(QNode));
6.         if (!newnode)
7.         {
8.                 perror("malloc");
9.                 exit(1);
10.         }
11.         newnode->data = data;
12.         //next记得置空
13.         newnode->next = NULL;
14.        
15.         //2. 插入节点
16.         if (!QueueEmpty(q))
17.         {
18.                 q->tail->next = newnode;
19.                 q->tail = q->tail->next;
20.         }
21.         //如果队列为空，要让头结点和尾节点都指向新节点
22.         else
23.                 q->tail = q->head = newnode;
24.        
25.         //3. size++
26.         q->size++;
27. }

复制代码

2. 4 出队列

1. void QueuePop(Queue* q);

复制代码

从队头出队列，有以下几个步调：

• 对链表举行前删，并修改head和tail的指向
  
• size--
  

1. void QueuePop(Queue* q)
2. {
3.         assert(q);
4.         //出队列时要判空，如果为空，就非法
5.         assert(!QueueEmpty(q));
7.         //1. 链表前删
8.         //将头节点的下一个节点保存起来，作为新的头节点
9.         QNode* next = q->head->next;
10.         free(q->head);
11.         //如果原本队列中只有一个元素，那么出队列后tail就指向的是一个野指针了，要置为空
12.         if (q->size == 1)
13.                 q->tail = NULL;
14.         q->head = next;
16.         //2. size--
17.         q->size--;
18. }

复制代码

2. 5 队尾元素和队头元素和队列元素个数

1. // 获取队列头部元素
2. QDataType QueueFront(Queue* q);
3. // 获取队列队尾元素
4. QDataType QueueBack(Queue* q);
5. // 获取队列中有效元素个数
6. int QueueSize(Queue* q);

复制代码

直接返回就可以了，不过要注意判空，否则会发生空指针的解引用。

1. QDataType QueueFront(Queue* q)
2. {
3.         assert(q);
4.         assert(!QueueEmpty(q));
5.         return q->head->data;
6. }
8. QDataType QueueBack(Queue* q)
9. {
10.         assert(q);
11.         assert(!QueueEmpty(q));
12.         return q->tail->data;
13. }
15. int QueueSize(Queue* q)
16. {
17.         assert(q);
18.         return q->size;
19. }

复制代码

2. 6 销毁

1. void QueueDestroy(Queue* q);

复制代码

将底层链表中所有节点free掉，再将Queue布局中所有成员置为NULL或0就可以了。

1. void QueueDestroy(Queue* q)
2. {
3.         assert(q);
4.         //需要判空吗？
5.         //assert(!QueueEmpty(q));
7.         //释放链表节点
8.         QNode* pcur = q->head;
9.         while (pcur)
10.         {
11.                 QNode* next = pcur->next;
12.                 free(pcur);
13.                 pcur = next;
14.                 q->size--;
15.         }
16.         //将Queue结构体中所有成员置为NULL或0
17.         q->head = q->tail = NULL;
18.         q->size = 0;
19. }

复制代码

2. 7 接口的意义

在队列这个数据布局上，我们实现了8个接口，可是其中有些接口，比如判空，元素个数等几个接口内部除了断言以外就一两行代码，为什么还要费力去实现呢？

1. assert(!QueueEmpty(q));
2. assert(q->head!=NULL);

复制代码

下面的写法难道不是更简洁吗？
事实上，这是因为每个人实现的队列中的成员名称可能不同，比如可能有个人的实现中，Queue是这么界说的：

1. typedef struct Queue
2. {
3.         QNode* _head;
4.         QNode* _tail;
5.         int _size;
6. }Queue;

复制代码

那么上面的代码就会报错了。
这样一比较，使用原来的开发者制作的接口就比较安全了。
3. 经典OJ题

3. 1 用队列实现栈

题目链接

1. //题目给出代码：
2. typedef struct {
3.    
4. } MyStack;
7. MyStack* myStackCreate() {
8.    
9. }
11. void myStackPush(MyStack* obj, int x) {
12.    
13. }
15. int myStackPop(MyStack* obj) {
16.    
17. }
19. int myStackTop(MyStack* obj) {
20.    
21. }
23. bool myStackEmpty(MyStack* obj) {
24.    
25. }
27. void myStackFree(MyStack* obj) {
28.    
29. }
31. /**
32. * Your MyStack struct will be instantiated and called as such:
33. * MyStack* obj = myStackCreate();
34. * myStackPush(obj, x);
36. * int param_2 = myStackPop(obj);
38. * int param_3 = myStackTop(obj);
40. * bool param_4 = myStackEmpty(obj);
42. * myStackFree(obj);
43. */

复制代码

这道题需要我们实现以上给出接口和布局体界说。
在开始写这道题之前，我们先想一下怎么用两个队列去实现栈。
首先，包管所有元素都在同一个队列（先称其为q1，另一个为q2）中，插入时只需要直接向q1入队列就可以了。
那么怎么出栈呢？
我们把q1中的元素依次出队列并入队列至q2，这样元素的次序不会变，直到q1中只剩下一个元素，把这个元素出队列而不入队列，不就实现了出栈了吗？
固然，在出栈之后，q1和q2是否存储数据的情况就颠倒了，也就是说，q1和q2哪个存储数据是不肯定的，在实现时要注意这一点。
我们正式来写这道题，第一步是实现队列这个数据布局，因为C语言是没有库提供实在现的，这里做了一些简化：

1. typedef struct QueueNode{
2.     struct QueueNode* next;
3.     int data;
4. }QNode;
6. typedef struct Queue{
7.     QNode *head;
8.     QNode *tail;
9.     int size;
10. }QU;
11. //判空
12. int IsEmpty(QU* qu)
13. {
14.     return qu->head == NULL;
15. }
16. //入队列
17. void PushToBack(QU* qu,int x)
18. {
19.     QNode* newnode = (QNode*)malloc(sizeof(QNode));
20.     newnode->data = x;
21.     newnode->next = NULL;
22.     if(IsEmpty(qu))
23.     {
24.         qu->head = qu->tail=newnode;
25.     }
26.     else
27.     {
28.         qu->tail->next = newnode;
29.         qu->tail = newnode;
30.     }
31.     qu->size++;
32. }
33. //出队列，在这道题中由于不允许使用其他接口，所以出队列函数要额外返回出队列的数据。
34. int PeekFromFront(QU* qu)
35. {
36.     QNode* newhead = qu->head->next;
37.     int ret = qu->head->data;
38.     free(qu->head);
39.     qu->head = newhead;
40.     if(!qu->head)
41.         qu->tail = NULL;
42.     qu->size--;
43.     return ret;
44. }
45. //初始化
46. void InitQU(QU* qu)
47. {
48.     qu->head = qu->tail=NULL;
49.     qu->size = 0;
50. }
51. //销毁，其实在OJ题中，一般不会出现内存溢出，所以可以不考虑内存溢出，但为了代码的严谨性，最好还是释放掉内存。
52. void Destroy(QU* qu)
53. {
54.     QNode* cur = qu->head;
55.     while(cur)
56.     {
57.         QNode* next = cur->next;
58.         free(cur);
59.         cur = next;
60.     }
61.     qu->head = qu->tail = NULL;
62.     qu->size = 0;
63. }

复制代码

在写OJ题时，不需要考虑malloc失败的情况，也不需要任何断言（固然加上也可以）。
以上是队列的实现，下面我们逐一来看栈的实现：
3. 1. 1 栈的界说

1. typedef struct {
2.     QU* q1;
3.     QU* q2;
4.     int size;
5. } MyStack;

复制代码

两个队列指针，一个int变量存储数据的个数。
3. 1. 2 栈的初始化

1. MyStack* myStackCreate();

复制代码

由于函数声明由题目给出，以是我们必须写成在函数内部动态申请内存然后返回的情势。
不仅申请MyStack这个布局体的内存，还要为其中的两个队列申请内存，因为MyStack布局体中只存在两个指向QU类型的指针变量而不是QU变量。

1. MyStack* myStackCreate() {
2.     MyStack* MS = (MyStack*)malloc(sizeof(MyStack));
3.     //为两个队列申请空间
4.     MS->q1 = (QU*)malloc(sizeof(QU));
5.     MS->q2 = (QU*)malloc(sizeof(QU));
6.     //分别对两个队列进行初始化
7.     InitQU(MS->q1);
8.     InitQU(MS->q2);
9.     MS->size = 0;
10.     return MS;
11. }

复制代码

3. 1. 3 入栈

1. void myStackPush(MyStack* obj, int x);

复制代码

上面已经说过了，只需要向有数据的队列入队列这个数据就可以了**，如果都没有数据，向任意队列入数据**就行。

1. void myStackPush(MyStack* obj, int x) {
2.         //找有数据的队列，都没有就用 q1
3.     QU* use = obj->q1;
4.     if (IsEmpty(use))
5.         use = obj->q2;
6.     //在找到的队列入队列这个数据
7.     PushToBack(use, x);
8.     obj->size++;
9. }

复制代码

3. 1. 4 出栈

1. int myStackPop(MyStack* obj);

复制代码

这个出栈函数需要返回出栈的数据。
按照我们前面所说的，有几个步调：

• 找到有数据的队列
  
• 将有数据的队列中的除了最后一个元素外全部出队列并入队列到另一个队列中
  
• 将本来有数据的队列的最后一个元素出队列并返回
  

1. int myStackPop(MyStack* obj) {
2.         // 1. OJ题一般不需要考虑两个队列都为空的情况
3.     QU* use = obj->q1;
4.     QU* other = obj->q2;
5.     if (IsEmpty(use)) {
6.         use = obj->q2;
7.         other = obj->q1;
8.     }
9.     // 2
10.     while (use->head->next) {
11.         PushToBack(other, PeekFromFront(use));
12.     }
13.     // 3
14.     return PeekFromFront(use);
15. }

复制代码

3. 1. 5 取栈顶元素

1. int myStackTop(MyStack* obj);

复制代码

实在步调和出栈是险些一样的，只是最后的谁人元素在出队列之后还需要入队列到另一个队列中。

1. int myStackTop(MyStack* obj) {
2.     QU* use = obj->q1;
3.     QU* other = obj->q2;
4.     if (IsEmpty(use)) {
5.         use = obj->q2;
6.         other = obj->q1;
7.     }
8.     while (use->head->next) {
9.         PushToBack(other, PeekFromFront(use));
10.     }
11.     //以上都和出栈一样
12.     //将最后一个元素的值保存起来方便返回
13.     int ret = PeekFromFront(use);
14.     //将其入队列到另一个队列中
15.     PushToBack(other, ret);
16.     return ret;
17. }

复制代码

3. 1. 6 判空

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

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

复制代码

3. 1. 7 销毁

将两个队列销毁，再将两个队列本身和栈本身都free掉就可以了。

1. void myStackFree(MyStack* obj) {
2.     Destroy(obj->q1);
3.     Destroy(obj->q2);
4.     //栈和队列都是动态开辟的，所以都需要释放
5.     free(obj->q1);
6.     free(obj->q2);
7.     free(obj);
8. }

复制代码

这道题的Leetcode官方题解使用的是以数组为底层的队列去实现栈，但是由于本文是用的链表，以是还是用的链表，感爱好可以研究一下怎么使用数组实现队列。
谢谢你的阅读，喜欢的话来个点赞收藏评论关注吧！
我会连续更新更多优质文章

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