每日一题——用两个队列实现栈

/*********************队列基本功能实现*************************/
typedef int QDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QueueNode;
typedef struct Queue  //定义存放指向队头，队尾指针的结构体
{
  QueueNode* head;  //指向队头
  QueueNode* tail;  //指向队尾
}Queue;
//初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
}
//销毁
void QueueDestroy(Queue* pq)
{
  QueueNode* cur = pq->head;  //定义临时变量
  while (cur)
  {
    pq->head = pq->head->next;  //链表下滑
    free(cur);    //释放空间
    cur = pq->head; //更新临时变量
  }
  pq->tail = NULL;  //空间释放完毕后head已经为空，但tail成为了野指针，所以要置空
}
//判空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}
//入队
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));   //创建新节点
  newnode->data = x;
  newnode->next = NULL;
  if (pq->tail == NULL && pq->head == NULL) //如果队列为空
  {
    pq->head = newnode; //使队头、队尾指针同时指向新节点
    pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode; //使队尾指针的指向下一个节点的指针指向新节点
    pq->tail = newnode; //更新队尾指针
  }
}
//出队
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));  //队列不能为空
  QueueNode* cur = pq->head;  //定义临时变量保存队头指针
  pq->head = pq->head->next;  //使队头指针指向下一个节点
  free(cur);    //释放原来的队头
  if (pq->head == NULL)
    pq->tail = NULL;  //如果节点已经全部出队，则要将队尾指针置空，防止形成野指针
}
//返回队头元素
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
//返回队尾元素 
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
//返回队列大小
int QueueSize(Queue* pq)
{
  QueueNode* cur = pq->head;
  int size = 0;
  while (cur)
  {
    size++;
    cur = cur->next;
  }
  return size;
}
/***********************用两个队列实现栈**************************/
typedef struct {
  Queue* q1, * q2;
} MyStack;
MyStack* myStackCreate() {
  MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
  obj->q1 = (Queue*)malloc(sizeof(Queue));
  obj->q2 = (Queue*)malloc(sizeof(Queue));
  QueueInit(obj->q1);
  QueueInit(obj->q2);
  return obj;
}
void myStackPush(MyStack* obj, int x) {
  QueuePush(obj->q1, x);
}
int myStackPop(MyStack* obj) {
  int size = QueueSize(obj->q1);
    //将除最后一个队列元素的其他所有元素放入辅助队列中
  while (--size)
  {
    QueuePush(obj->q2, QueueFront(obj->q1));
    QueuePop(obj->q1);
  }
    //保存要弹出的值
  int result = QueueFront(obj->q1);
    //出队
  QueuePop(obj->q1);
  size = QueueSize(obj->q2);
    //将辅助队列的元素重新移回主队列中
  while (size--)
  {
    QueuePush(obj->q1, QueueFront(obj->q2));
    QueuePop(obj->q2);
  }
  return result;
}
int myStackTop(MyStack* obj) {
  return QueueBack(obj->q1);
}
bool myStackEmpty(MyStack* obj) {
  return QueueEmpty(obj->q1);
}
void myStackFree(MyStack* obj) {
  QueueDestroy(obj->q1);
}
/**
 * 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);
*/