力扣（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;
}