1.题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty()
  如果栈是空的，返回 true ；
  否则，返回 false 。

2.原题链接

Leetcode225. 用队列实现栈

3.思路分析

1 . 这道题利用队列先进先出的特性来实现栈 ，使用用两个队列
2. 保证一个队列为空 ，另一个队列存放size个数据 ，
如何实现栈的Pop？
将有数据的队列中的size-1个数据放进另一个空队列 ,然后将剩下的数据Pop，那就有一个问题，如何判断哪个队列为空？
定义两个变量 ， emptyQ (空队列 ） ， nonemptyQ( 不是空队列） 。假设q1 为空队列， q2 不为空队列 （ q1 ,q2 为两个队列 ）。如果q1为空队列， q2 不为空队列，则假设成功 , 如果q1不为空队列， q2 为空队列，则假设失败 ，就将q2变为空队列 ， q1 变为非空队列
如何实现栈的Push ?
如果 有队列不为空 ，就往该队列插入数据 , 哪个队列不为空 ，就往哪个队列插入
如何实现栈的Empty ？
两个队列为空即栈为空

4.代码实现

这道题使用的结构体比较多 ，我们画图辅助理解相应的细节 : 图中的QNode* head 、QNodetail , 分别对应下面代码中的 Queue head 、Queue* tail

typedef int   QueueNodeTypeData;typedef struct  QueueNode
{struct  QueueNode* next;QueueNodeTypeData data;
}QueueNodeType;typedef struct Queue
{QueueNodeType * tail; // 队尾QueueNodeType * head; //队头int size; 
} Queue;  // 链式结构：表示队列void QueueInit(Queue* pq);  // 初始化  void QueueDestory(Queue* pq); //队列的销毁void QueuePush(Queue* pq , QueueNodeTypeData x );  // 队尾入队列void QueuePop(Queue* pq); //队头出队列int QueueSize(Queue* pq);//获取队列中有效元素个数bool QueueEmpty(Queue* pq); // 判断队列是否为空 QueueNodeTypeData QueueFront(Queue * pq); //获取队列头部元素QueueNodeTypeData QueueBack(Queue * pq); //获取队列尾部元素void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestory(Queue* pq) //队列的销毁
{assert(pq);QueueNodeType * cur = pq->head;//遍历 while (cur){QueueNodeType* next = cur->next;  //保存下一个节点的地址free(cur); //释放当前节点cur = next; }pq->tail = pq->head = NULL;pq->size = 0;
}
void QueuePush(Queue* pq, QueueNodeTypeData x) // 入队 
{assert(pq);QueueNodeType* newnode =(QueueNodeType*) malloc( sizeof(QueueNodeType) );if (newnode == NULL){printf(" malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;//扩容成功//第一次入队if ( pq->head == NULL){assert(pq->tail == NULL);   //pq->head ==NULL , pq->tail != NULL ,就是出问题了pq->tail = pq->head = newnode;}else //非第一次入队{pq->tail->next = newnode; // 类似尾插pq->tail = newnode; // 更新tail 指针}pq->size++;
}
void QueuePop(Queue* pq) //队头出队列
{assert(pq);assert(pq->head != NULL); //只有一个节点if (pq->head->next == NULL) {free(pq->tail);  //出队pq->tail = pq->head = NULL;}// 多个节点else{QueueNodeType* next = pq->head->next; // 保存下一个节点的地址 free(pq->head); // 出队pq->head = NULL;pq->head = next;  //更新pq->head ，往后走 }pq->size--;
}int QueueSize(Queue* pq)//获取队列中有效元素个数
{assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return  pq->head == NULL ;
}QueueNodeTypeData QueueFront(Queue* pq) //获取队列头部元素
{assert(pq);assert(!QueueEmpty(pq)); //防止队列为空return pq->head->data;}QueueNodeTypeData QueueBack(Queue* pq) //获取队列尾部元素
{assert(pq);assert(!QueueEmpty(pq)); //防止队列为空return pq->tail->data;
}typedef struct{Queue q1 ;Queue q2 ;} MyStack;MyStack* myStackCreate() 
{MyStack * pst = (MyStack *)malloc ( sizeof( MyStack));      if( pst == NULL){perror( "malloc fail");return NULL ;} //初始化两个队列 QueueInit(&pst->q1);QueueInit(&pst->q2);return pst ;
}void myStackPush(MyStack* obj, int x) 
{//q1 不为空 ，插入数据 if( !QueueEmpty(&obj->q1)){QueuePush( &obj->q1 ,x);}else //q2 不为空 ，插入数据 {QueuePush( &obj->q2 ,x);}
}int myStackPop(MyStack* obj) 
{//假设q1 不为空队列 ，q2 为空队列 MyStack* empty = &obj->q2;MyStack* nonempty = &obj->q1;if( !QueueEmpty(&obj->q2))  // q2 不为空队列 ，q1 为空队列 ，假设失败,重新假设即可 {empty = &obj->q1 ;nonempty = &obj->q2 ;}//将有数据的队列中的size-1个数据放进另一个空队列  while ( QueueSize(nonempty)>1){QueuePush( empty , QueueFront(nonempty));QueuePop(nonempty);}   //Pop将剩下的一个数据int top  = QueueBack(nonempty);QueuePop(nonempty);return top ;}int myStackTop(MyStack* obj)  //返回栈顶元素 {//q1 为空 返回 q2的队尾元素 if( !QueueEmpty(&obj->q2)){return QueueBack(&obj->q2) ;}else  //q2 为空 返回 q1的队尾元素 {return QueueBack(&obj->q1) ;}}bool myStackEmpty(MyStack* obj) 
{ return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2) ;  
}void myStackFree(MyStack* obj){QueueDestory( &obj->q1);QueueDestory( &obj->q2);free( obj);}

如果你觉得这篇文章对你有帮助，不妨动动手指给点赞收藏加转发，给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力！！