牛客网刷题-两个队列实现栈

题目原型：

输入输出示例：

1.题目分析：题目意思很明确，就是要你用两个队列去实现一个栈，本质就是用两个队列的接口函数去实现栈的接口函数如图下所示，只要满足后进先出的特性就好，那些输入输出示例就是在测试我们实现的栈的接口函数是否正确。

2.解题思路：
我们都知道队列的特性是先进先出，而栈的特性是后进先出，我们要想办法用两个队列去实现后进先出，要想实现后进先出，是不是先要找到后进的元素(最后一个元素)，先就是说我们只要每次出队列的最后一个元素不就实现了嘛，而且正好有两个栈：
1.出栈：可以将一个不为空的队列，把数据都除了最后一个元素全部出队列，然后把这些出掉的数据入队进为空的队列中，然后就将哪个不为空的队列上的最后一个元素出队，如果还要出栈就继续上述操作其实就是两个队列反复倒腾数据然后去最后一个元素出栈(这样就实现的了栈的后进先出的特性)
看图就明白啦：

模拟出栈函数代码实现：

int pop() {Queue *EmptyQueue=&q1;Queue *NonEmptyQueue=&q2;if(!QueueEmpty(&q1)){NonEmptyQueue=&q1;EmptyQueue=&q2;}while(QueueSize(NonEmptyQueue)>1){QueuePush(EmptyQueue,QueueFront(NonEmptyQueue));QueuePop(NonEmptyQueue);}int top= QueueFront(NonEmptyQueue);QueuePop(NonEmptyQueue);return top;
}

2.入栈：就是往不为空的队列入数据就好

模拟入栈函数实现：

void push(int element) {if(!QueueEmpty(&q1)){QueuePush(&q1,element);}else{QueuePush(&q2,element);}
}

3.取栈顶元素：因为栈的特性后进先出取栈顶元素其实就是去队列的最后一个入队的元素，直接可以利用队列取队尾数据的接口函数

模拟取栈顶元素代码实现：

int top() {if(!QueueEmpty(&q1)){return QueueBack(&q1);}else{return QueueBack(&q2);}
}

4.判断栈是否为空：两个队列都为空则栈的就为空
代码实现：

bool empty() {return QueueEmpty(&q1) && QueueEmpty(&q2);
}

完整代码附带注释：

typedef  int      QDataType;typedef struct QueueNode {struct QueueNode* next;QDataType data;
} QNode;typedef struct Queue {QNode* head;QNode* tail;
} Queue;/*队列的接口函数*/
void QueueInit(Queue* pq) {if (pq == NULL) {return;}pq->head = pq->tail = NULL;
}void QueueDestory(Queue* pq) {if (pq == NULL) {return;}QNode* cur = pq->head;while (cur) {QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;
}void QueuePush(Queue* pq, QDataType x) {if (pq == NULL) {return;}QNode* NewNode = (QNode*)malloc(sizeof(QNode));if (NewNode == NULL) {printf("malloc fail\n");exit(-1);}NewNode->data = x;NewNode->next = NULL;//空队列if (pq->tail == NULL) {pq->head = pq->tail = NewNode;}//队列不为空else {pq->tail->next = NewNode;pq->tail = NewNode;}}
void QueuePop(Queue* pq) {if (pq == NULL) {return;}//只有一个结点if (pq->head->next == NULL) {free(pq->head);pq->head = pq->tail = NULL;} else {QNode* next = pq->head->next;free(pq->head);pq->head = next;}
}
QDataType QueueFront(Queue* pq) {if (pq == NULL) {exit(-1);}return pq->head->data;
}
QDataType QueueBack(Queue* pq) {if (pq == NULL) {exit(-1);}return pq->tail->data;
}int QueueSize(Queue* pq) {if (pq == NULL) {exit(-1);}int count = 0;QNode* cur = pq->head;while (cur) {cur = cur->next;count++;}return count;
}bool QueueEmpty(Queue* pq) {return  pq->head == NULL;
}//创建两个队列q1,q2
Queue  q1;
Queue  q2;void push(int element) {//往非空队列"入栈"if(!QueueEmpty(&q1)){QueuePush(&q1,element);}else{QueuePush(&q2,element);}
}int pop() {/*判断出非空队列与空队列*/Queue *EmptyQueue=&q1;Queue *NonEmptyQueue=&q2;if(!QueueEmpty(&q1)){NonEmptyQueue=&q1;EmptyQueue=&q2;}//倒腾数据:非空队列往空队列里面倒腾数据(最后一个元素不动)while(QueueSize(NonEmptyQueue)>1){QueuePush(EmptyQueue,QueueFront(NonEmptyQueue));QueuePop(NonEmptyQueue);}//出栈最后一个元素int top= QueueFront(NonEmptyQueue);QueuePop(NonEmptyQueue);return top;
}int top() {//取非空队列的队尾数据(就是模拟栈的栈顶元素)if(!QueueEmpty(&q1)){return QueueBack(&q1);}else{return QueueBack(&q2);}
}bool empty() {//两个队列都为空模拟栈才为空return QueueEmpty(&q1) && QueueEmpty(&q2);
}