用队列实现栈——数据结构与算法

😶‍🌫️Take your time ! 😶‍🌫️
💥个人主页：🔥🔥🔥大魔王🔥🔥🔥
💥代码仓库：🔥🔥魔王修炼之路🔥🔥
💥所属专栏：🔥魔王的修炼之路–数据结构🔥
如果你觉得这篇文章对你有帮助，请在文章结尾处留下你的点赞👍和关注💖，支持一下博主。同时记得收藏✨这篇文章，方便以后重新阅读。

---

一、题目

力扣链接

二、思路

栈是后进先出，队列是先进先出.

出队列：队列入了1，2，3，4后只能1，2，3，4出，栈入了1，2，3，4后只能4，3，2，1出，所以需要两个队列，当栈出元素时，先让前n-1个入到另一个队列并删除原队列中这n-1个数据，那么原来队列只剩下4了，然后把这个4删除就行。

入队列：根据出队列发现，把一个队列数据放到另一个数据里面，原来的数据顺序不变，所以入队列时只需要入在那个不为空的队列里就行。

三、代码

1、队列代码

首先先把之前实现队列的代码粘贴上去，这样就不用再实现一遍队列了。

#include <stdlib.h>typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QInit(Queue* q)
{assert(q);q->head = q->tail = NULL;q->size = 0;
}void QDestroy(Queue* q)
{assert(q);while (q->head){QNode* next = q->head->next;free(q->head);q->head = next;}q->tail = NULL;q->size = 0;
}QNode* BuyNewnode(QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc error");assert(newnode);}newnode->data = x;newnode->next = NULL;return newnode;
}void QPush(Queue* q, QDataType x)
{assert(q);QNode* newnode = BuyNewnode(x);if (q->head == NULL){assert(q->head == q->tail);q->head = q->tail = newnode;}else{q->tail->next = newnode;q->tail = newnode;}q->size++;
}void QPop(Queue* q)
{assert(q);assert(q->head && q->tail);if (q->head->next == NULL){assert(q->head == q->tail);free(q->head);q->head = q->tail = NULL;}else{QNode* newhead = q->head->next;free(q->head);q->head = newhead;}q->size--;
}int QSize(Queue* q)
{assert(q);return q->size;
}bool QEmpty(Queue* q)
{assert(q);//-------------------------1------------------------------------------------//1这里的报错，但是其实根本没错，是在下面的2处错的，所以在哪个地方报错可以重点看那个地方，但并不一定就是这个部分错了。return q->size == 0;
}QDataType QFront(Queue* q)
{assert(q);assert(q->head);return q->head->data;
}QDataType QBack(Queue* q)
{assert(q);assert(!QEmpty(q));return q->tail->data;
}

2、创建两个队列模拟的栈

创建一个结构体，放两个队列作为成员，然后创建并初始化队列。

//匿名结构体，创建一个结构体是我的栈，因为我们使用队列模拟栈，所以里面放两个队列。
typedef struct {Queue q1;Queue q2;
} MyStack;//创建我的栈，前面我们的模拟栈的结构体已经创建好了，现在就是要创建一个指针指向我们开辟出的该结构体的空间，并使其初始化。因为这是创建好后用的返回值传给别的函数，所以不能直接创建变量，要malloc，否则除该作用域就销毁了。
MyStack* myStackCreate() {MyStack* creat = (MyStack*)malloc(sizeof(MyStack));if(creat == NULL){perror("malloc error");assert(creat);}QInit(&creat->q1);QInit(&creat->q2);return creat;
}

3、入栈

直接入到不为空的队列就行，因为两个相互导顺序还是原来的顺序。

void myStackPush(MyStack* obj, int x) {Queue* EmptyQ = &obj->q1;Queue* nonEmptyQ = &obj->q2;//if (QEmpty(&EmptyQ) == 0)-------------------------2(错的)----------------------------------if (QEmpty(EmptyQ) == 0){EmptyQ = &obj->q2;nonEmptyQ = &obj->q1;}QPush(nonEmptyQ, x);
}

4、出栈

让不为空的n-1个元素导到空队列中，原队列只剩最后一个，然后pop就行了。

int myStackPop(MyStack* obj) {Queue* EmptyQ = &obj->q1;Queue* nonEmptyQ = &obj->q2;if (!QEmpty(EmptyQ)){EmptyQ = &obj->q2;nonEmptyQ = &obj->q1;}while (QSize(nonEmptyQ) != 1){QPush(EmptyQ, QFront(nonEmptyQ));QPop(nonEmptyQ);}int ret = QFront(nonEmptyQ);QPop(nonEmptyQ);return ret;
}

5、访问栈顶元素

可以直接访问非空队列的最上面的元素即可。

//方法1.访问栈顶元素
int myStackTop(MyStack* obj) {if(!QEmpty(&obj->q1)){return QBack(&obj->q1);}elsereturn QBack(&obj->q2);
}

也可以再导一次，就像出栈一样，只不过不删除最后的元素，而是也导入另一个队列。

//方法2.访问栈顶元素
// 力扣检查比较严格，就算最后的那个return没用，但有返回值的函数结尾还是要加上return 的。
int myStackTop(MyStack* obj) {int ret = 0;Queue* EmptyQ = &obj->q1;Queue* nonEmptyQ = &obj->q2;if(!QEmpty(EmptyQ)){EmptyQ = &obj->q2;nonEmptyQ = &obj->q1;}while(QSize(nonEmptyQ)>0){if(QSize(nonEmptyQ) == 1){ret = QFront(nonEmptyQ);QPush(EmptyQ,QFront(nonEmptyQ));QPop(nonEmptyQ);return ret;}QPush(EmptyQ,QFront(nonEmptyQ));QPop(nonEmptyQ);}return ret;
}

6、判断栈是否为空

两个队列同时为空即为空。

bool myStackEmpty(MyStack* obj) {return QEmpty(&obj->q1) && QEmpty(&obj->q2);
}

7、释放空间

malloc了几次就释放几次。

void myStackFree(MyStack* obj) {QDestroy(&obj->q1);QDestroy(&obj->q2);free(obj);
}

8、总代码

#include <stdlib.h>typedef int QDataType;typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QInit(Queue* q)
{assert(q);q->head = q->tail = NULL;q->size = 0;
}void QDestroy(Queue* q)
{assert(q);while (q->head){QNode* next = q->head->next;free(q->head);q->head = next;}q->tail = NULL;q->size = 0;
}QNode* BuyNewnode(QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc error");assert(newnode);}newnode->data = x;newnode->next = NULL;return newnode;
}void QPush(Queue* q, QDataType x)
{assert(q);QNode* newnode = BuyNewnode(x);if (q->head == NULL){assert(q->head == q->tail);q->head = q->tail = newnode;}else{q->tail->next = newnode;q->tail = newnode;}q->size++;
}void QPop(Queue* q)
{assert(q);assert(q->head && q->tail);if (q->head->next == NULL){assert(q->head == q->tail);free(q->head);q->head = q->tail = NULL;}else{QNode* newhead = q->head->next;free(q->head);q->head = newhead;}q->size--;
}int QSize(Queue* q)
{assert(q);return q->size;
}bool QEmpty(Queue* q)
{assert(q);//-------------------------1------------------------------------------------//1这里的报错，但是其实根本没错，是在下面的2处错的，所以在哪个地方报错可以重点看那个地方，但并不一定就是这个部分错了。return q->size == 0;
}QDataType QFront(Queue* q)
{assert(q);assert(q->head);return q->head->data;
}QDataType QBack(Queue* q)
{assert(q);assert(!QEmpty(q));return q->tail->data;
}//匿名结构体，创建一个结构体是我的栈，因为我们使用队列模拟栈，所以里面放两个队列。
typedef struct {Queue q1;Queue q2;
} MyStack;//创建我的栈，前面我们的模拟栈的结构体已经创建好了，现在就是要创建一个指针指向我们开辟出的该结构体的空间，并使其初始化。因为这是创建好后用的返回值传给别的函数，所以不能直接创建变量，要malloc，否则除该作用域就销毁了。
MyStack* myStackCreate() {MyStack* creat = (MyStack*)malloc(sizeof(MyStack));if(creat == NULL){perror("malloc error");assert(creat);}QInit(&creat->q1);QInit(&creat->q2);return creat;
}void myStackPush(MyStack* obj, int x) {Queue* EmptyQ = &obj->q1;Queue* nonEmptyQ = &obj->q2;//if (QEmpty(&EmptyQ) == 0)-------------------------2----------------------------------if (QEmpty(EmptyQ) == 0){EmptyQ = &obj->q2;nonEmptyQ = &obj->q1;}QPush(nonEmptyQ, x);
}int myStackPop(MyStack* obj) {Queue* EmptyQ = &obj->q1;Queue* nonEmptyQ = &obj->q2;if (!QEmpty(EmptyQ)){EmptyQ = &obj->q2;nonEmptyQ = &obj->q1;}while (QSize(nonEmptyQ) != 1){QPush(EmptyQ, QFront(nonEmptyQ));QPop(nonEmptyQ);}int ret = QFront(nonEmptyQ);QPop(nonEmptyQ);return ret;
}// //方法1.访问栈顶元素
// int myStackTop(MyStack* obj) {
//     if(!QEmpty(&obj->q1))
//     {
//         return QBack(&obj->q1);
//     }
//     else
//         return QBack(&obj->q2);
// }//方法2.访问栈顶元素
// 力扣检查比较严格，就算最后的那个return没用，但有返回值的函数结尾还是要加上return 的。
int myStackTop(MyStack* obj) {int ret = 0;Queue* EmptyQ = &obj->q1;Queue* nonEmptyQ = &obj->q2;if(!QEmpty(EmptyQ)){EmptyQ = &obj->q2;nonEmptyQ = &obj->q1;}while(QSize(nonEmptyQ)>0){if(QSize(nonEmptyQ) == 1){ret = QFront(nonEmptyQ);QPush(EmptyQ,QFront(nonEmptyQ));QPop(nonEmptyQ);return ret;}QPush(EmptyQ,QFront(nonEmptyQ));QPop(nonEmptyQ);}return ret;
}//方法3.访问栈顶元素
// int myStackTop(MyStack* obj) {
// 	Queue* EmptyQ = &obj->q1;
// 	Queue* nonEmptyQ = &obj->q2;
// 	if (!QEmpty(EmptyQ))
// 	{
// 		EmptyQ = &obj->q2;
// 		nonEmptyQ = &obj->q1;
// 	}
// 	while (QSize(nonEmptyQ) != 1)
// 	{
// 		QPush(EmptyQ, QFront(nonEmptyQ));
// 		QPop(nonEmptyQ);
// 	}
// 	int ret = QFront(nonEmptyQ);
// 	QPush(EmptyQ,QFront(nonEmptyQ));
// 	QPop(nonEmptyQ);
// 	return ret;
// }bool myStackEmpty(MyStack* obj) {return QEmpty(&obj->q1) && QEmpty(&obj->q2);
}void myStackFree(MyStack* obj) {QDestroy(&obj->q1);QDestroy(&obj->q2);free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

四、总结

• -----1-----和-----2-----这两个地方是一个错误，因为在2多写了个取地址，然后在1处报错，结果检查了大半天也检查不出来，因为1处报错很难想出来是2处的问题。所以：报错的地方重点检查，如果真的没错误，可能是其他地方的问题。
• 分别指向空队列和非空队列时别弄混了，有点绕。

---

• 博主长期更新，博主的目标是不断提升阅读体验和内容质量，如果你喜欢博主的文章，请点个赞或者关注博主支持一波，我会更加努力的为你呈现精彩的内容。

🌈专栏推荐
😈魔王的修炼之路–C语言
😈魔王的修炼之路–数据结构初阶
😈魔王的修炼之路–C++
😈魔王的修炼之路–Linux
更新不易，希望得到友友的三连支持一波。收藏这篇文章，意味着你将永久拥有它，无论何时何地，都可以立即找到重新阅读；关注博主，意味着无论何时何地，博主将永久和你一起学习进步，为你带来有价值的内容。