• 【栈与队列面试题】用队列实现栈（动图演示）

    两个队列实现一个栈

    前言：

    💥🎈个人主页:​​​​​​Dream_Chaser～ 🎈💥

    ✨✨刷题专栏:http://t.csdn.cn/UlvTc

    ⛳⛳本篇内容:力扣上栈与队列的面试OJ题目

    目录

    两个队列实现一个栈

    队列的实现（前提准备）

    一.题目描述

    1.自定义栈的结构

    2.自定义栈的初始化

    3.将元素压入栈顶

    4.移除并返回栈顶元素

    5.返回栈顶元素

    6.判断栈是否为空栈

    7.栈的销毁

    自定义栈的代码实现 

    队列的实现（前提准备）

    1. #include<stdio.h>
    2. #include<assert.h>
    3. #include<stdbool.h>
    4. #include<stdlib.h>
    5. typedef int QDataType;
    6. typedef struct QueueNode
    7. {	
    8. 	QDataType data;
    9. 	struct QueueNode* next;
    10. }QNode;
    11.  
    12. typedef struct Queue
    13. {
    14. 	QNode* phead;
    15. 	QNode* ptail;
    16. 	int size;
    17. }Queue;//表示队列整体,一个是出数据，一个是入数据.
    18.  
    19. void QueueInit(Queue* pq);// 初始化队列
    20. void QueueDestroy(Queue* pq);// 销毁队列
    21. void QueuePush(Queue* pq, QDataType x);// 队尾入队列
    22. void QueuePop(Queue* pq);// 队头出队列
    23. QDataType QueueFront(Queue* pq);// 获取队列头部元素
    24. QDataType QueueBack(Queue* pq);// 获取队列队尾元素
    25. int QueueSize(Queue* pq);// 获取队列中有效元素个数
    26. bool QueueEmpty(Queue* pq);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
    27.  
    28.  
    29.  
    30. void QueueInit(Queue* pq)
    31. {
    32. 	assert(pq);// 检查指针是否为空
    33.  
    34. 	pq->phead=NULL; // 将队列的头指针置为空
    35. 	pq->ptail = NULL;// 将队列的头指针置为空
    36. 	pq->size = 0;// 将队列的头指针置为空
    37. }
    38.  
    39. // void QPrint(Queue* pq)
    40. // {
    41. // 	assert(pq);
    42.  
    43. // 	QNode* cur = pq->phead;
    44. // 	QNode* next = cur;
    45. // 	while (cur != NULL)
    46. // 	{
    47. // 		printf("%d ", cur->data);
    48. // 		cur = cur->next;
    49. // 	}
    50. // }
    51.  
    52. void QueueDestroy(Queue* pq)
    53. {
    54. 	assert(pq);// 检查指针是否为空
    55. 	
    56.     QNode* cur = pq->phead;// 创建一个指针 cur，指向队列的头指针
    57. 	while (cur)
    58. 	{
    59. 		QNode* next = cur->next;// 创建一个指针 cur，指向队列的头指针
    60. 		free(cur);// 释放当前节点的内存
    61. 		cur = next;// 将指针 cur 移动到下一个节点
    62. 	}
    63. 	
    64.     pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空
    65. 	pq->size = 0;// 将队列的大小置为0
    66. }
    67.  
    68. void QueuePush(Queue* pq, QDataType x)
    69. {
    70. 	assert(pq);
    71. 	
    72.     QNode* newnode = (QNode*)malloc(sizeof(QNode));// 创建一个新的节点
    73.  
    74. 	if (newnode == NULL)
    75. 	{
    76. 		perror("malloc fail\n");// 检查内存分配是否成功
    77. 		return;
    78. 	}
    79. 	
    80.     newnode->data = x;// 设置新节点的数据为传入的元素值
    81. 	newnode->next = NULL;// 将新节点的指针域置空
    82.  
    83. 	//一个节点
    84. 	//多个节点
    85. 	if (pq->ptail == NULL)// 判断队列是否为空
    86. 	{
    87. 		//assert(pq->phead == NULL);// 如果队列为空，头指针也应为空
    88. 		
    89.         pq->phead = pq->ptail = newnode;// 将新节点同时设置为队列的头节点和尾节点
    90. 	}
    91. 	
    92.     else
    93. 	{
    94. 		pq->ptail->next = newnode;// 将新节点同时设置为队列的头节点和尾节点
    95. 		pq->ptail = newnode;// 更新队列的尾指针为新节点
    96. 	}
    97. 	pq->size++;// 增加队列的大小计数
    98. }
    99.  
    100. void QueuePop(Queue* pq)
    101. {
    102. 	assert(pq);// 检查指针是否为空
    103. 	assert(!QueueEmpty(pq));// 检查队列是否非空
    104. 	//assert(pq->phead);// 检查队列的头指针是否存在
    105. 	//1.一个节点
    106. 	if (pq->phead->next == NULL) // 队列只有一个节点的情况
    107. 	{
    108. 		free(pq->phead); // 释放队列头节点的内存
    109. 		pq->phead = pq->ptail = NULL;// 将队列的头指针和尾指针置为空
    110. 	}
    111. 	else
    112. 	{
    113. 		//头删
    114. 		QNode* next = pq->phead->next; //保存队列头节点的下一个节点指针
    115. 		free(pq->phead);// 释放队列头节点的内存
    116. 		pq->phead = next;// 更新队列的头指针为下一个节点
    117. 	}
    118. 	pq->size--;//减少队列的大小计数
    119. }
    120.  
    121.  
    122. QDataType QueueFront(Queue* pq)
    123. {
    124. 	assert(pq);
    125. 	assert(!QueueEmpty(pq));// 检查队列是否非空
    126. 	//assert(pq->phead);// 检查队列的头指针是否存在
    127.  
    128. 	return pq->phead->data;// 返回队列头节点的数据
    129. }
    130.   
    131. QDataType QueueBack(Queue* pq)
    132. {
    133. 	assert(pq);// 检查队列是否非空
    134. 	assert(!QueueEmpty(pq));// 检查队列是否非空
    135. 	//assert(pq->phead);// 检查队列的头指针是否存在
    136. 	
    137. 	return pq->ptail->data;//返回队列尾节点的数据
    138. }
    139.  
    140.  
    141.  
    142. int QueueSize(Queue* pq)
    143. {
    144. 	assert(pq);//检查指针是否为空
    145.  
    146. 	return pq->size;//返回队列的大小（元素个数）
    147. }
    148. bool QueueEmpty(Queue* pq)
    149. {
    150. 	assert(pq);
    151. 	
    152. 	//方法一,将队列的头指针以及尾指针置空
    153. 	//return pq->phead = NULL && pq->ptail==NULL;
    154. 	
    155. 	//方法二,将队列的有效元素置空
    156. 	return pq->size == 0;
    157. }
    158.

    一.题目描述

    来源:225. 用队列实现栈 - 力扣（LeetCode）

    请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

    实现 MyStack 类：

    • void push(int x) 将元素 x 压入栈顶。
    • int pop() 移除并返回栈顶元素。
    • int top() 返回栈顶元素。
    • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

    需要了解的知识：

    栈(Stack)：

    1. 后进先出(LIFO)顺序:最后压入栈的元素,第一个弹出栈。它像一堆盘子,最后放上的盘子,先拿走。

    2. 在栈顶添加,在栈顶删除:所有新元素都放在栈顶,操作栈时只有栈顶元素可以被访问。

    3. 压栈和出栈操作不可逆:当一个元素被压入栈后,要等到它到栈顶位置才能将其弹出。栈不允许非栈顶元素先出栈。

    4. 有大小限制:每个栈都有最大容量限制,栈满时不能继续压入新元素。

    5. 主要操作:栈主要支持两种操作 - 入栈(push)和出栈(pop),所有元素都从栈顶压入/弹出。

    6. 适合处理后进先出的任务:栈这种后进先出的特性,适合模拟那些需要后操作的先完成的场景,如函数调用堆栈。

    总结：是一种后进先出的线性表,只允许在表的一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据,先进入的元素最后才能取出,具有先进后出的逻辑顺序。

    队列(Queue)：

    1. 先进先出(FIFO)顺序:先进入队列的元素会先出队列,后进入的元素后出队列。

    2. 在队尾添加,在队头删除:所有新元素都添加在队尾,删除元素时都从队头删除元素。

    3. 出队操作不可取消:已进入队列的元素不能中途删除,只能等待它到队头后再删除它。

    4. 有大小限制:队列通常有最大容量限制,队列满时不能再加入新元素,必须等待队头元素出队后才能加入。

    5. 主要操作:队列主要支持两种操作 - 入队(enqueue)和出队(dequeue),入队是将元素加入队尾,出队是从队头删除元素。

    6. 适合处理先进先出的任务:队列适合去处理需要先进先出顺序的任务,比如打印任务队列、排队等。

    总结：是一个先进先出、有顺序的线性表,它只允许在一端进行插入,在另一端进行删除,遵循先进先出的原则。这使其非常适合模拟现实生活中的排队等情形。

    1.自定义栈的结构

       MyStack 这个结构体模拟了一个栈的数据结构,它使用两个队列 q1 和 q2 来实现栈的功能。

    1. typedef struct {
    2. 	Queue q1;
    3. 	Queue q2;
    4. } MyStack;

    2.自定义栈的初始化

            使用 malloc 函数为 MyStack 结构体对象分配内存空间。sizeof(MyStack) 表示要分配的内存大小等于 MyStack 结构体的大小。返回的指针类型是 void* 。

            因此需要进行类型转换为 MyStack* 类型并将其赋值给 obj 变量,初始化 obj 指向的 MyStack 结构体中的队列 q1 和 q2。如果内存分配和初始化成功，最后，函数返回指向新创建的MyStack对象的指针obj

    代码实现：

    1. MyStack* myStackCreate() {
    2.     MyStack *obj=(MyStack*)malloc(sizeof(MyStack));
    3.  
    4.     if(obj == NULL)
    5.     {
    6.         perror("malloc fail");
    7.         return NULL; 
    8.     }
    9.    //用于初始化 obj 指向的 MyStack 结构体中的队列 q1 和 q2
    10.     QueueInit(&obj->q1);//初始化q1队列
    11.     QueueInit(&obj->q2);//初始化q2队列
    12.  
    13.     //返回指向已创建并初始化的 MyStack 结构体对象的指针 obj
    14.     return obj;
    15. }

    3.将元素压入栈顶

    将元素推入栈时：

    1. 如果队列 q1 不为空，就将元素直接推入 q1 中；
    2. 如果 q1 为空，就将元素推入 q2 中。

            这样的实现方式可以确保在栈中的元素都集中在一个队列中（要么是 q1，要是 q2），而另一个队列则保持为空。这种实现方式的优势在于在执行出栈操作时，可以将非空队列中的元素转移到另一个空队列中，以便实现栈的先进后出特性。  

            

    1. void myStackPush(MyStack* obj, int x) {
    2. 	if (!QueueEmpty(&obj->q1))// 如果 q1 不为空，将元素推入 q1
    3. 	{
    4. 		QueuePush(&obj->q1, x);
    5. 	}
    6. 	else// 如果 q1 为空，将元素推入 q2
    7. 	{
    8. 		QueuePush(&obj->q2, x);
    9. 	}
    10. }

    4.移除并返回栈顶元素

    演示一遍出栈过程 

    演示全程出栈过程(只演示栈内部的队列)

    代码实现: 

    1. int myStackPop(MyStack* obj)//栈出元素
    2.  {
    3.     //假设q1队列是空队列,q2非空队列
    4.     Queue* pEmptyQ=&obj->q1;
    5.     Queue* pNonEmptyQ=&obj->q2;
    6.     if(!QueueEmpty(&obj->q1))//如果q1不为空
    7.     {
    8. 			//此时空队列指针指向q2
    9.       pEmptyQ=&obj->q2;
    10.       pNonEmptyQ=&obj->q1;//非空队列指针指向q1
    11.     }
    12.     //挪数据,结束条件是非空队列的元素个数为1
    13.     while(QueueSize(pNonEmptyQ)>1)
    14.     {
    15.         QueuePush(pEmptyQ,QueueFront(pNonEmptyQ));//获取非队列头部元素，把非空队列的元素入到空队列，
    16.         QueuePop(pNonEmptyQ);//接着非空队列出元素
    17.     }
    18. 		//此时非空队列只有一个元素
    19.     int top=QueueFront(pNonEmptyQ);//获取此时非空队列的头部元素
    20.     QueuePop(pNonEmptyQ);//到这步,非空队列出完所有元素
    21. 	 // 返非空队列元素
    22.     return top;
    23. }

    5.返回栈顶元素

            q1队列如果不为空，那么返回q1队列的队尾元素当作自定义栈的栈顶元素，反之q2亦然。

    1. int myStackTop(MyStack* obj)//返回栈顶元素
    2. {
    3.     if(!QueueEmpty(&obj->q1))//q1队列如果不为NULL
    4.     {
    5.         return QueueBack(&obj->q1);//返回q1队尾元素
    6.     }
    7.     else//q2队列如果不为NULL
    8.     {
    9.         return QueueBack(&obj->q2);//返回q2队尾元素
    10.     }
    11. }

    6.判断栈是否为空栈

            判空就是要判断q1队列和q2队列都为空，才证明这个栈为空栈。

    1. bool myStackEmpty(MyStack* obj)//判断自定义栈是否为空栈
    2. {
    3.     return QueueEmpty(&obj->q1) &&
    4.     QueueEmpty(&obj->q2);
    5. }

    7.栈的销毁

    错误写法：内存泄露

    正确写法：

            先把q1和q2队列指向的节点free掉，接着再free掉整个MyStack，这样确保了不会内存泄露。

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

    自定义栈的代码实现 

    1. typedef struct {
    2.     Queue q1;
    3.     Queue q2;
    4. } MyStack;
    5.  
    6. MyStack* myStackCreate() {
    7.     MyStack *obj=(MyStack*)malloc(sizeof(MyStack));
    8.     if(obj == NULL)
    9.     {
    10.         perror("malloc fail");
    11.         return NULL; 
    12.     }
    13.     QueueInit(&obj->q1);//初始化q1队列
    14.     QueueInit(&obj->q2);//初始化q2队列
    15.  
    16.     return obj;
    17. }
    18.  
    19. // //注意以下写法
    20. // typedef struct
    21. // {
    22. //     Queue* q1;
    23. //     Queue* q2;
    24. // }MyStack;
    25.  
    26. // MyStack* myStackCreate()
    27. // {
    28. //     MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    29. //     if(obj == NULL)
    30. //     {
    31. //         perror("malloc fail");
    32. //         return NULL;
    33. //     }
    34. //     obj->q1=(Queue*)malloc(sizeof(Queue));
    35. //     obj->q2=(Queue*)malloc(sizeof(Queue));
    36.  
    37. //     QueueInit(obj->q1);
    38. //     QueueInit(obj->q2);
    39. // 		return obj;
    40. // }
    41.  
    42.  
    43. void myStackPush(MyStack* obj, int x) {
    44.     if(!QueueEmpty(&obj->q1))//
    45.     {
    46.         QueuePush(&obj->q1,x);
    47.     }
    48.     else
    49.     {
    50.         QueuePush(&obj->q2,x);
    51.     }
    52.       
    53. }
    54.  
    55. int myStackPop(MyStack* obj)//栈出元素
    56.  {
    57.     //假设q1队列是空队列,q2非空队列
    58.     Queue* pEmptyQ=&obj->q1;
    59.     Queue* pNonEmptyQ=&obj->q2;
    60.     if(!QueueEmpty(&obj->q1))//如果q1不为空
    61.     {
    62. 			//此时空队列指针指向q2
    63.       pEmptyQ=&obj->q2;
    64.       pNonEmptyQ=&obj->q1;//非空队列指针指向q1
    65.     }
    66.     //挪数据,结束条件是非空队列的元素个数为1
    67.     while(QueueSize(pNonEmptyQ)>1)
    68.     {
    69.         QueuePush(pEmptyQ,QueueFront(pNonEmptyQ));//获取非队列头部元素，把非空队列的元素入到空队列，
    70.         QueuePop(pNonEmptyQ);//接着非空队列出元素
    71.     }
    72. 		//此时非空队列只有一个元素
    73.     int top=QueueFront(pNonEmptyQ);//获取此时非空队列的头部元素
    74.     QueuePop(pNonEmptyQ);//到这步,非空队列出完所有元素
    75. 	 // 返非空队列元素
    76.     return top;
    77. }
    78.  
    79. int myStackTop(MyStack* obj)//返回栈顶元素
    80. {
    81.     if(!QueueEmpty(&obj->q1))//q1队列如果不为NULL
    82.     {
    83.         return QueueBack(&obj->q1);//返回q1队尾元素
    84.     }
    85.     else//q2队列如果不为NULL
    86.     {
    87.         return QueueBack(&obj->q2);//返回q2队尾元素
    88.     }
    89. }
    90.  
    91. bool myStackEmpty(MyStack* obj)//判断自定义栈是否为空栈
    92. {
    93.     return QueueEmpty(&obj->q1) &&
    94.     QueueEmpty(&obj->q2);
    95. }
    96.  
    97. void myStackFree(MyStack* obj) {
    98.     QueueDestroy(&obj->q1);
    99.     QueueDestroy(&obj->q2);
    100.  
    101.     free(obj);
    102. }

    代码执行：

            到这里文章就结束了，如有错误欢迎指正，感谢你的来访与支持！

  • 相关阅读:
    脱离CRUD苦海 ！性能优化全栈小册来了！
    Docker consul
    机器学习笔记 - 时间序列的混合模型
    【经验总结】Ubuntu 源代码方式安装 Microsoft DeepSpeed
    dart中final和const的区别
    emacs从缓冲中获取信息,并执行shell 命令
    网络基础详解
    【数据结构】栈和队列
    Mobile-ViT (MobileViT)网络讲解
    java的stream让我灵光一现
  • 原文地址：https://blog.csdn.net/weixin_65186652/article/details/132847081