力扣（LeetCode) ——225 用队列实现栈(C语言）

题目：用队列实现栈

示例1：

输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]

输出： [null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

解题思路：

栈的特性是只能在一端插入和删除元素，但是队列是队头删除元素队尾插入元素。

最终代码：

typedef int QDataType;
//节点结构
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next; 
}QNode;
//队列结构
typedef struct Queue
{
	QNode* phead;//队头
	QNode* ptail;//队尾
	int size;//队列大小
}Queue;

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* pcur = pq->phead;
	while (pcur)
	{
		QNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}



//队尾插入
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->next = NULL;
	newnode->val = x;

	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}

//队头删除
void QueuePop(Queue* pq)
{
	assert(pq && pq->size > 0);
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	pq->size--;
}

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(pq && pq->size > 0);
	return pq->phead->val;
}

//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(pq && pq->ptail);
	return pq->ptail->val;
}

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

//队列个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
 
//————————————————————————————
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

//创建一个栈
MyStack* myStackCreate() 
{
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&(pst->q1));
    QueueInit(&(pst->q2));

    return pst;
}
//入栈
void myStackPush(MyStack* obj, int x)
{
    //往不为空的队列插入数据
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}
//出栈
int myStackPop(MyStack* obj) 
{
    Queue* empty = &(obj->q1);
    Queue* nonEmpty = &(obj->q2);
    if(!QueueEmpty(&(obj->q1)))
    {
        empty = &(obj->q2);
        nonEmpty = &(obj->q1);
    }

    while(QueueSize(nonEmpty)>1)
    {
        QueuePush(empty, QueueFront(nonEmpty));
        QueuePop(nonEmpty);
    }
    int top = QueueFront(nonEmpty);
    QueuePop(nonEmpty);
    return top;
    
}
//返回栈顶元素
int myStackTop(MyStack* obj) 
{
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }   
    else
    {
        return QueueBack(&obj->q2);
    }
}
//判断栈是否为空
bool myStackEmpty(MyStack* obj) 
{
    return (QueueEmpty(&obj->q1) && (QueueEmpty(&obj->q2)));
    
}
//销毁 
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj = NULL;
}