目录
题目要求
代码思路
两个队列实现栈的准备工作
两个队列实现栈
题目要求
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
代码思路
要利用两个队列 Queue1 和 Queue2 实现后进先出的栈
实现栈的 先出 概念：
前提：要保证两个队列中，Queue1 有数据，Queue2 没有数据
假设：Queue1 中有 n 个数据
将 Queue1 中的前 n-1 个数据以先进先出的逻辑移动到 Queue2
再将 Queue1 中的第 n 个数据给移除
这样就实现了栈的 先出 概念
实现栈的 后进 概念：
当 Queue1 和 Queue2 都没有数据时，要存放的数据放在任意一个队列都可以
当 Queue1 或者 Queue2 其中一个没有数据时（要保证其中一个队列没有数据），那么就将要存放的数据放在已经有数据的那个队列里
这样就实现了栈的 后进 概念
两个队列实现栈的准备工作
先将队列的结构以及基本操作实现
// 数据类型
typedef int QDataType;// 链式队列每个节点的结构
typedef struct QueueNode
{struct QueueNode* next; //指向下一个节点的指针QDataType data; //当前节点的数据
}QNode;// 链式队列的结构
typedef struct Queue
{QNode* phead; //指向队头节点的指针QNode* ptail; //指向队尾节点的指针int size; //队列的总数据个数
}Queue;// 初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}// 打印
void QueuePrint(Queue* pq)
{assert(pq);QNode* cur = pq->phead;printf("head<-");while (cur != NULL){printf("%d<-", cur->data);cur = cur->next;}printf("tail\n\n");
}// 数据入队列（尾插）
void QueuePush(Queue* pq, QDataType x)
{assert(pq);// 开辟节点QNode* newnode = (QNode*)malloc(sizeof(QNode));// 判断是否开辟成功if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){// 双重判断，更保险assert(pq->ptail == NULL);pq->phead = newnode;pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}// 数据出队列（头删）
void QueuePop(Queue* pq)
{assert(pq);// 队列没有数据时if (pq->phead == NULL){printf("无数据可出队列\n");return;}if (pq->phead->next == NULL){free(pq->phead);pq->phead = NULL;pq->ptail = NULL;}else{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}// 访问队头的数据
QDataType QueueFront(Queue* pq)
{assert(pq);// 队列没有数据时if (pq->phead == NULL){printf("无数据可访问\n");return -1;}return pq->phead->data;
}// 访问队尾的数据
QDataType QueueBack(Queue* pq)
{assert(pq);// 队列没有数据时if (pq->ptail == NULL){printf("无数据可访问\n");return -1;}return pq->ptail->data;
}// 队列数据总个数
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}// 是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return (pq->phead == NULL) && (pq->ptail == NULL);
}// 释放列表
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur != NULL){QNode* next = cur->next;free(cur);cur = next;}pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}接下来用两个队列实现栈都需要以上的函数
两个队列实现栈
// 定义两个队列，存入匿名结构体，用来实现栈
typedef struct
{Queue q1;Queue q2;
} MyStack;// 初始化/创建
MyStack* myStackCreate()
{MyStack* obj = (MyStack*)malloc(sizeof(MyStack));// 判断是否开辟成功if(obj == NULL){perror("malloc fail");return NULL;}// 初始化两个队列QueueInit(&obj->q1);QueueInit(&obj->q2);return obj;
}// 插入数据（后进）
void myStackPush(MyStack* obj, int x)
{// 当 q1 队列不为空时就尾插到 q1if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1, x);}else //否则尾插到 q2{QueuePush(&obj->q2, x);}
}// 拿出数据（先出）
int myStackPop(MyStack* obj)
{Queue* pEmptyQ = &obj->q1;Queue* pNoEmptyQ = &obj->q2;// pNoEmptyQ 指向有数据的队列，pEmptyQ 指向无数据的队列if(!QueueEmpty(&obj->q1)){pNoEmptyQ = &obj->q1;pEmptyQ = &obj->q2;} // 将 pNoEmptyQ 的前 n-1 个数据放入 pEmptyQwhile(QueueSize(pNoEmptyQ) > 1){QueuePush(pEmptyQ, QueueFront(pNoEmptyQ));QueuePop(pNoEmptyQ);}int top = QueueFront(pNoEmptyQ);QueuePop(pNoEmptyQ);return top;
}// 访问栈顶元素
int myStackTop(MyStack* obj)
{// q1 队列不为空时，那么 q1 的尾节点就是栈顶元素if(!QueueEmpty(&obj->q1)){return QueueBack(&obj->q1);} else //q2 同理{return QueueBack(&obj->q2);}
}// 判空
bool myStackEmpty(MyStack* obj)
{// 也就是要判断两个队列是否都为空return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}// 释放
void myStackFree(MyStack* obj)
{// 释放 obj 前，要先释放两个队列中的节点QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);
}