用队列实现栈

使用队列实现栈的下列操作：
  push(x) – 元素 x 入栈
  pop() – 移除栈顶元素
  top() – 获取栈顶元素
  empty() – 返回栈是否为空
注意:

你只能使用队列的基本操作-- 也就是push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
https://leetcode-cn.com/problems/implement-stack-using-queues/description/
用双队列实现栈：两个队列倒换数据
入栈的时候

出栈的时候

删除之后

入栈

队列的实现

typedef int QUDataType;

typedef struct QueueNode
{
	QUDataType _data;
	struct QueueNode *_next;
}QueueNode;

typedef struct Queue
{
	QueueNode *_front;
	QueueNode *_rear;
}Queue;

void QueueInit(Queue *q)
{
	assert(q);

	q->_front = q->_rear = NULL;
}

void QueueDestory(Queue *q)
{
	assert(q);

	QueueNode * cur = q->_front;
	while (cur)
	{
		QueueNode * next = cur->_next;
		free(cur);
		cur = next;
	}
}

void QueuePush(Queue *q, QUDataType x)
{
	assert(q);
	
	//申请结点
	QueueNode *newNode = (QueueNode*)malloc(sizeof(QueueNode));
	newNode->_data = x;
	//连接到队尾1.空队列2.有数据
	if (q->_front == NULL)
	{
		q->_front = q->_rear = newNode;
		q->_rear->_next = NULL;
	}
	else
	{
		q->_rear->_next = newNode;
		q->_rear = q->_rear->_next;
		q->_rear->_next = NULL;
	}
}

void QueuePop(Queue *q)
{
	assert(q);

	//空队列不能删除
	if(q->_front)
	{
		QueueNode *next = q->_front->_next;
		free(q->_front);
		q->_front = next;
	}
}

int QueueSize(Queue *q)
{
	assert(q);

	QueueNode *cur = q->_front;
	int size = 0;
	while (cur)
	{
		size++;
		cur = cur->_next;
	}
	return size;
}

int QueueEmpty(Queue *q)
{
	assert(q);

	if (q->_front == NULL)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

QUDataType QueueFront(Queue *q)
{
	assert(q);

	return q->_front->_data;
}

QUDataType QueueRear(Queue *q)
{
	assert(q);

	return q->_rear->_data;
}

用双队列实现栈

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

/** Initialize your data structure here. */
MyStack* myStackCreate(int maxSize) {
    MyStack *obj = (MyStack *)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) {
    assert(obj);
    //入栈是入到不为空的队列
    //第一次都为空时对边入哪个队列都可以
    if(QueueEmpty(&obj->q1) != 0)
        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* pEmpty = &obj->q1, *pNonEmpty = &obj->q2;
    //使得pEmpty指向为空的队列
    //使得NonEmpty指向不为空的队列
    if(QueueEmpty(&obj->q1) != 0)
    {
        pEmpty = &obj->q2;
        pNonEmpty = &obj->q1;
    }
    //把非空队列里的数据转移到空队列这种，剩余最后一个元素
    while(QueueSize(pNonEmpty) > 1)
    {
        QueuePush(pEmpty, QueueFront(pNonEmpty));
        QueuePop(pNonEmpty);
    }
    //最后一个元素出栈，从刚才那个非空队列出来
    int top = QueueFront(pNonEmpty);
    QueuePop(pNonEmpty);
    return top;
}

/** Get the top element. */
int myStackTop(MyStack* obj) {
    assert(obj);
    //使得pEmpty指向为空的队列
    //使得NonEmpty指向不为空的队列
    Queue *pEmpty = &obj->q1;
    Queue *pNonEmpty = &obj->q2;
    if(QueueEmpty(pEmpty) != 0)
    {
        pEmpty = &obj->q2;
        pNonEmpty = &obj->q1;
    }
    //返回非空队列的最后一个元素
    return QueueRear(pNonEmpty);
}

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) {
    assert(obj);
    //两个队列都为空时，栈为空
    if(QueueEmpty(&obj->q1) == 0 && QueueEmpty(&obj->q2) == 0)
        return true;
    return false;
}

void myStackFree(MyStack* obj) {
    assert(obj);
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);
    free(obj);
    obj = NULL;
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * struct MyStack* obj = myStackCreate(maxSize);
 * myStackPush(obj, x);
 * int param_2 = myStackPop(obj);
 * int param_3 = myStackTop(obj);
 * bool param_4 = myStackEmpty(obj);
 * myStackFree(obj);
 */