目录

题目要求

代码思路

两个队列实现栈的准备工作

两个队列实现栈  

题目要求

请你仅使用两个队列实现一个后入先出（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 队列不为空时就尾插到 q1
    if(!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 个数据放入 pEmptyQ
    while(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);
}