一、问题描述

使用队列实现栈的下列操作：

       push(x) -- 元素 x 入栈
       pop() -- 移除栈顶元素
       top() -- 获取栈顶元素
       empty() -- 返回栈是否为空

注意:你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/implement-stack-using-queues

二、问题分析

1.栈的特点：栈只能在栈顶进行入栈和出栈操作，同时遵循“先入后出”原则。

2.队列的特点：队列的一端用于入队、另一端用于出队；遵循“先进先出”；

3.队列实现栈的思路分析

两个队列，一个队列保持空另一个队列保持非空，当入栈时向非空的队列中直接入队元素，当出栈时将非空队列中的元素出最后一个外其余全部出队并入控队中。

三、代码实现

typedef int QDataType;
//队列节点结构体
typedef struct QueueNode
{
    struct QueueNode* _next;//指针域
    int _data;//数据域
}QNode;
//队列结构体
typedef struct QueueList
{
    struct QueueNode* _front;//头节点
    struct QueueNode* _rear;//尾节点
}Queue;
//栈结构，用两个队列实现一个栈,一个队列保持空一个保持非空
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

//初始化队列
void QueueInit(Queue* q)
{
    q->_front = NULL;
    q->_rear = NULL;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	//创建节点
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	newNode->_data = data;
	newNode->_next = NULL;
	//判断队列是否为空
	if (q->_front == NULL)
	{
		q->_front = newNode;
		q->_rear = newNode;
	}
	else
	{
		q->_rear->_next = newNode;
		q->_rear = q->_rear->_next;
	}

}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* curr = q->_front;
	QNode* del = NULL;
	while (curr)
	{
		del = curr;
		curr = curr->_next;
		free(del);
	}
	del = NULL;
}
// 队头出队列 
void QueuePop(Queue* q)
{
	//判断队列是否为空
	if (q->_front == NULL)
	{
		return;
	}
	QNode* head = q->_front;
	q->_front = q->_front->_next;
	free(head);
	head = NULL;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	//判断队列是否为空,为空返回-1
	if (q->_front == NULL)
	{
		return -1;
	}
	return q->_front->_data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	QNode* curr = q->_front;
	int size = 0;
	while (curr)
	{
		size++;
		curr = curr->_next;
	}
	return size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	if (q->_front == NULL)
		return 1;
	return 0;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	if (q->_front == NULL)
		return -1;
	return q->_rear->_data;
}
/** Initialize your data structure here. */

MyStack* myStackCreate() {
    //申请空间
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    //初始化栈
    QueueInit(&st->q1);
    QueueInit(&st->q2);

    return st;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
    //将元素x入非空的队列，如果都为空就如obj->q2
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) {
    //定义两个队列指针，一个为空队列一个为非空队列
    Queue* empty = &obj->q1;
    Queue* notEmpty = &obj->q2;
    //判断哪一个队列非空，就从那个队列出队
    if(!QueueEmpty(&obj->q1))
    {
        empty = &obj->q2;
        notEmpty = &obj->q1;
    }
    //让非空队列元素出队，并放入空队列
    while(QueueSize(notEmpty)>1)
    {
        //取队头元素放入空队列中
        QueuePush(empty,QueueFront(notEmpty));
        //队头元素出队
        QueuePop(notEmpty);
    }
    //保存队尾元素
    int top = QueueBack(notEmpty);
    //队尾元素出队
    QueuePop(notEmpty);
    return top;
}

/** Get the top element. */
int myStackTop(MyStack* obj) {
    //返回队尾元素
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
    //如果有一个队列不为空，栈就不为空
    if(!QueueEmpty(&obj->q1) ||  !QueueEmpty(&obj->q2))
    {
        return false;
    }
    else
    {
        return true;
    }
}

void myStackFree(MyStack* obj) {
    //销毁队列
    QueueDestroy(&obj->q1);
    QueueDestroy(&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);
*/