[Leetcode] 使用队列实现堆栈

1.用队列实现栈

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

实现 MyStack 类：

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

目录

题解：

1.既是以队列（Queue）实现栈(Stack)，那首先要实现队列的基础功能：

2.基于队列(Queue)实现栈（Stack）：

出栈：

入栈：

获取栈顶元素：

判空：

3.注意：

4..完整代码：

---

题解：

1.既是以队列（Queue）实现栈(Stack)，那首先要实现队列的基础功能：

（初始化（QueueInit），出入队列（QueuePush）（QueuePop），判空（QueueEnpty））

typedef int QueueDataType;
typedef struct QueueData{
	QueueDataType Data;
	struct QueueData* Next;
}QD;
typedef struct{
	QD* head;
	QD* rear;
}Queue;
//初始化队列
void QueueInit(Queue*tmp) {
	tmp->head = tmp->rear = NULL;
}
//判空
bool QueueEmpty(Queue* tmp) {
	assert(tmp);
	return tmp->rear == NULL;
}
//入队列
void QueuePush(Queue*tmp,QueueDataType x) {
	assert(tmp);
	QD* p = (QD*)malloc(sizeof(QD));
	if (p == NULL) {
		perror("Push:malloc");
		return;
	}
	p->Data = x;
	p->Next = NULL;
	if (tmp->rear == NULL) {
		tmp->head = tmp->rear = p;
	}
	else {
		tmp->rear->Next = p;
		tmp->rear = p;
	}
}
//出队列
QueueDataType QueuePop(Queue*tmp) {
	assert(tmp);
	QueueDataType data;
	if (QueueEmpty(tmp)) {
		perror("QueuePop:NULL");
	}
	else if (tmp->head == tmp->rear) {
		data = tmp->head->Data;
		free(tmp->head);
		tmp->head = tmp->rear = NULL;
	}
	else {
		data = tmp->head->Data;
		QD* p = tmp->head;
		tmp->head = tmp->head->Next;
		free(p);
		p = NULL;
	}
	return data;
}

2.基于队列(Queue)实现栈（Stack）：

出栈：

结合队列先进先出的特性，要满足栈后入先出，只需要两个队列互相配合（一个（a）队列接收（n个）入栈元素，当要出栈时只需要将（n-1个）元素出队列到另一个（b）队列中，最后将（a）队列中最后一个元素出队列即可）

QueueDataType myStackPop(MyStack* obj) {
	if (QueueEmpty(&obj->queue1) && QueueEmpty(&obj->queue2)) {
		perror("StackPop:NULL");
	}
	if (QueueEmpty(&obj->queue2)) {
		while (obj->queue1.head != obj->queue1.rear) {
			QueuePush(&obj->queue2, QueuePop(&obj->queue1));
		}
		return QueuePop(&obj->queue1);
	}
	else {
		while (obj->queue2.head != obj->queue2.rear) {
			QueuePush(&obj->queue1, QueuePop(&obj->queue2));
		}
		return QueuePop(&obj->queue2);
	}
}

入栈：

同理，入栈也需要两个队列配合，用一个队列接收元素，并标记该队列，另一个为空

void myStackPush(MyStack* obj, QueueDataType x) {
	if (QueueEmpty(&obj->queue2)) {
		QueuePush(&obj->queue1, x);
	}
	else {
		QueuePush(&obj->queue2, x);
	}
}

获取栈顶元素：

只需找到不为空的队列，返回该队列的队尾元素即可

QueueDataType myStackTop(MyStack* obj) {
	if (QueueEmpty(&obj->queue1) && QueueEmpty(&obj->queue2)) {
		perror("StackTop:NULL");
		return 0;
	}
	if (QueueEmpty(&obj->queue2)) {
		return obj->queue1.rear->Data;
	}
	else {
		return obj->queue2.rear->Data;
	}
}

判空：

判断构成栈的两个队列都为空，即栈为空

bool myStackEmpty(MyStack* obj) {
	return (QueueEmpty(&obj->queue1) && QueueEmpty(&obj->queue2));

}

3.注意：

实现队列和栈的过程中，想内存申请的空间，最后要记得释放，防止内存泄漏

4..完整代码：

#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>
typedef int QueueDataType;
typedef struct QueueData{
	QueueDataType Data;
	struct QueueData* Next;
}QD;
typedef struct{
	QD* head;
	QD* rear;
}Queue;
typedef struct{
	Queue queue1;
	Queue queue2;
} MyStack;
void QueueInit(Queue*tmp) {
	tmp->head = tmp->rear = NULL;
}
bool QueueEmpty(Queue* tmp) {
	assert(tmp);
	return tmp->rear == NULL;
}
MyStack* myStackCreate() {
	MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
	QueueInit(&stack->queue1);
	QueueInit(&stack->queue2);
	return stack;
}
void QueuePush(Queue*tmp,QueueDataType x) {
	assert(tmp);
	QD* p = (QD*)malloc(sizeof(QD));
	if (p == NULL) {
		perror("Push:malloc");
		return;
	}
	p->Data = x;
	p->Next = NULL;
	if (tmp->rear == NULL) {
		tmp->head = tmp->rear = p;
	}
	else {
		tmp->rear->Next = p;
		tmp->rear = p;
	}
}
QueueDataType QueuePop(Queue*tmp) {
	assert(tmp);
	QueueDataType data;
	if (QueueEmpty(tmp)) {
		perror("QueuePop:NULL");
	}
	else if (tmp->head == tmp->rear) {
		data = tmp->head->Data;
		free(tmp->head);
		tmp->head = tmp->rear = NULL;
	}
	else {
		data = tmp->head->Data;
		QD* p = tmp->head;
		tmp->head = tmp->head->Next;
		free(p);
		p = NULL;
	}
	return data;
}
void myStackPush(MyStack* obj, QueueDataType x) {
	if (QueueEmpty(&obj->queue2)) {
		QueuePush(&obj->queue1, x);
	}
	else {
		QueuePush(&obj->queue2, x);
	}
}

QueueDataType myStackPop(MyStack* obj) {
	if (QueueEmpty(&obj->queue1) && QueueEmpty(&obj->queue2)) {
		perror("StackPop:NULL");
	}
	if (QueueEmpty(&obj->queue2)) {
		while (obj->queue1.head != obj->queue1.rear) {
			QueuePush(&obj->queue2, QueuePop(&obj->queue1));
		}
		return QueuePop(&obj->queue1);
	}
	else {
		while (obj->queue2.head != obj->queue2.rear) {
			QueuePush(&obj->queue1, QueuePop(&obj->queue2));
		}
		return QueuePop(&obj->queue2);
	}
}

QueueDataType myStackTop(MyStack* obj) {
	if (QueueEmpty(&obj->queue1) && QueueEmpty(&obj->queue2)) {
		perror("StackTop:NULL");
		return 0;
	}
	if (QueueEmpty(&obj->queue2)) {
		return obj->queue1.rear->Data;
	}
	else {
		return obj->queue2.rear->Data;
	}
}

bool myStackEmpty(MyStack* obj) {
	return (QueueEmpty(&obj->queue1) && QueueEmpty(&obj->queue2));

}

void myStackFree(MyStack* obj) {
	QD* cur = obj->queue1.head;
	while (cur) {
		QD* tmp = cur;
		cur = cur->Next;
		free(tmp);
		tmp = NULL;
	}
	cur = obj->queue2.head;
	while (cur) {
		QD* tmp = cur;
		cur = cur->Next;
		free(tmp);
		tmp = NULL;
	}
}