栈与队列：用队列实现栈

题目：

栈和队列的数据模型对比：

思路分析：

代码分析：

一、定义栈

二、初始化栈

三、入栈

四、出栈⭐

代码解析：

五、获取栈顶元素

六、判断栈是否为空

七、销毁栈

完整代码：

需要手撕的队列代码：

题目：

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

实现 MyStack 类：

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

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

题源：225. 用队列实现栈 - 力扣（LeetCode）

题目内容：

栈和队列的数据模型对比：

思路分析：

本题的核心部分和原理是如何将队列的特点演变成栈的特点，即如何将队列的先进先出演化为栈的后进先出。

按照题目的要求，我们需要使用两个队列进行栈的实现，以此我们可以根据队列的特点，进行数据的传输交换。

如图所示，可以将一个队列中的数据（除去最后一个），转移到另一个空的队列中，并将最后一个数据进行删除，完成表面意义上的栈的出栈！

且当我们需要再次出栈的时候，便又可把含有数据的队列中的数据进行转移，并保留最后一个进行删除，以此来表示出栈！

而入栈，只需要将数据插入在原本就有数据的队列中，如果两个队列都没有数据，则随便插入一个即可。

代码分析：

一、定义栈

因为本题是需要使用两个队列来实现栈，于是需要对队列的调用，因此栈内部的定义只需要使用两个指向不同队列的指针即可。

二、初始化栈

使用之前定义的栈（MyStack）创造一个空间，表示栈的创建，随后在这个空间的内部调用队列的初始化函数，对栈中的两个队列进行初始化。

~~这种方法定义的形式，令人感觉像是栈的内部其实是两个队列。~~

注意：->的优先级是比&更高级的，所以&pst-> q1和 &pst-> q2的本意是取栈内部的q1、q2的地址，而pst只是一个指向栈（MyStack）的指针。

三、入栈

在思路分析中，讲诉过，那个队列是空的数据便尾插到那个队列，如果都为空那就随便插入都行

四、出栈⭐

代码解析：

根据之前的思路分析得知，我们需要两段逻辑，队列q1空q2不空，q2空q1不空，而这两段逻辑可以变为一句话，那便是，将不为空的元素（除了最后一个）全部按照顺序转移到另一个为空的队列中。

而因为需要将元素进行转移，所以我们调用了队列中的QueueSize，这个是统计队列长度的，当队列长度=1时，相当于留下的队尾的元素，而>1时进行转移。
转移需要使用插入函数，QueuePush函数，且函数中的参数是之前创立的空队列指针emptyq，另一个是非空队列队头的元素，非空队列的队头元素使用了QueueFront进行获取
获取之后使用了QueuePop在非空队列中进行删除，以此来减去非空队列的长度

while(QueueSize(nonemptye) > 1)在上图代码和下图的例图中，都表示while是把非空队列变成只剩下队尾元素的操作。

而最后一步的操作，则是在其他元素都转移后，只留下了队尾元素在非空队列中，然后使用获取队头元素的操作，将元素交给临时变量，而后进行删除非空队列的最后一个元素，并返回临时变量，以此表示出栈。

五、获取栈顶元素

获取栈顶元素在之前的数据模型对比中可以得知，队尾其实就相当于栈底，所以我们便可以调用队列的获取队尾元素来获取栈底元素，当然这个队列是不为空的队列！

六、判断栈是否为空

需要两个队列同时为空才行！因为我们进行了互换操作！

七、销毁栈

要分别把两个队列进行销毁后在销毁封存两个队列指针的结构体

完整代码：

需要手撕的队列代码：

//队列的单链表节点结构
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);
//销毁
void QueueDestroy(Queue* pq);
//插入——入队
void QueuePush(Queue* pq, QDataType x);
//删除——出队
void QueuePop(Queue* pq);
//获取队头元素
QDataType QueueFront(Queue* pq);
//获取队尾元素
QDataType QueueBack(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//查看队列长度
int QueueSize(Queue* pq);
//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = 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->val = x;
	newnode->next = NULL;
	//判断尾节点指针是否指向为空，如果为空头节点指针和尾节点指针都是指向新节点
	if (pq->ptail == NULL)
	{
		pq->ptail = pq->phead = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	//别忘了长度需要在插入后+1，为了方便之后的统计队列长度
	pq->size++;
}

// 出队
void QueuePop(Queue* pq)
{
	assert(pq);
	// 
	assert(pq->phead);

	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = NULL;
	//头删的第二种情况
	//如果只有一个节点，那么第二个节点就是空的了
	//而现在phead就处在第二个节点
	if (pq->phead == NULL)
		pq->ptail = NULL;

	pq->size--;
}
//获取队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	// 如果队头是空的表示队列不存在
	assert(pq->phead);

	return pq->phead->val;
}
//获取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//如果队尾是空的表示队列不存在 
	assert(pq->ptail);

	return pq->ptail->val;
}
//判断队列是否存在
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->phead == NULL;
}
//获取队列长度
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}