全文目录
- 引言
- 用队列实现栈
- 题目介绍
- 思路简述
- 实现
- 队列的部分
- 栈的部分
- 栈的创建
- 判断栈是否为空
- 压栈
- 出栈
- 访问栈顶元素
- 栈的释放
- 总结
引言
在了解了栈和队列的知识后，我们已经对它们的特点有了一定的了解：栈是先进后出，队列是先进先出：
戳我康栈详解哦
戳我康队列详解哦
接下来的两篇文章就来介绍用两个队列实现栈以及用两个栈实现队列的OJ练习：
用队列实现栈OJ链接
用队列实现栈
题目介绍
题目描述很简单：
通过两个队列实现栈存储数据的特点，即先进后出：
我们需要实现push、pop、top、empty、free：
void push(int x) 将元素 x 压入栈顶；
int pop() 移除并返回栈顶元素；
int top() 返回栈顶元素；
bool empty() 如果栈是空的，返回 true ；否则，返回 false 。
思路简述
这道题的难点主要在于如何pop队列中后存储的元素，因为队列的特点是先进先出，所以在队列尾的元素是无法直接移除的。
我们很容易的想到利用第二个队列，将队列中的元素转移到另一队列中，只留一个元素在原队列中，这个剩余的元素就是最后入的元素，将这个元素移除即可；
如果这时要再移除尾的元素，就将队列中的元素再移回原来的队列，删除剩下的一个元素即可；
如果此时要再插入元素，就直接在有元素的那个队列尾插入即可，再移除时再倒一遍即可：
因为，如果从一个队列中将元素从队列头依次移出，再依次插入到另一个队列中时，数据的顺序是不改变的。所以如果要再尾插入元素时直接在有元素的那个队列插入即可；尾删时，只需要重复的倒数据即可：
实现
队列的部分
在用两个队列实现栈之前，我们需要实现队列的接口，在用其实现栈时直接复用即可。关于队列的实现这里就不再赘述了，在前面的文章中已经详细的介绍过了。这里直接把前面实现过的队列的各种接口拷贝过来，包括用于定义队列的结构体：
typedef int QDataType;
typedef struct QListNode//队列的每个结点
{
struct QListNode* pNext;
QDataType data;
}QNode;
typedef struct Queue// 队列的结构
{
QNode* front;
QNode* rear;
int size;
}Queue;
// 队列的部分
// 初始化队列
void QueueInit(Queue* pq)
{
assert(pq);
pq->front = NULL;
pq->rear = NULL;
pq->size = 0;
}
// 检测队列是否为空，如果为空返回非0,非空返回0
int QueueEmpty(Queue* pq)
{
assert(pq);
return pq->front == NULL;
}
// 队尾入队列
void QueuePush(Queue* pq, QDataType data)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
newnode->data = data;
newnode->pNext = NULL;
if (QueueEmpty(pq))
{
pq->front = newnode;
pq->rear = newnode;
}
else
{
pq->rear->pNext = newnode;
pq->rear = newnode;
}
pq->size++;
}
// 队头出队列
void QueuePop(Queue* pq)
{
assert(pq && QueueEmpty(pq)==0);
QNode* cur = pq->front->pNext;
if (cur)
{
free(pq->front);
pq->front = cur;
}
else
{
free(pq->front);
pq->front = NULL;
pq->rear = NULL;
}
pq->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* pq)
{
assert(pq && QueueEmpty(pq)==0);
return pq->front->data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq && QueueEmpty(pq)==0);
return pq->rear->data;
}
// 销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->front;
QNode* next = pq->front;
while (cur)
{
next = cur->pNext;
free(cur);
cur = next;
}
pq->front = NULL;
pq->rear = NULL;
pq->size = 0;
}
栈的部分
有了队列的实现后，我们需要创建两个队列q1与q2，并将这两个队列存放在一个结构体变量中方便访问：
typedef struct //两个队列
{
Queue q1;
Queue q2;
} MyStack;
栈的创建
对于这个接口，题目并没有给出参数。我们就直接为结构体MyStack动态开辟一块空间，并且初始化即可。
初始化时，我们可以直接复用队列初始化函数QueueInit，初始化两个队列即可：
//创建栈
MyStack* myStackCreate()
{
MyStack* pmst = (MyStack*)malloc(sizeof(MyStack));
assert(pmst);
QueueInit(&pmst->q1);
QueueInit(&pmst->q2);
return pmst;
}
判断栈是否为空
栈为空，即两个队列均为空。
所以我们直接复用判断队列是否为空函数QueueEmpty，当两个队列均为空，即两个函数的返回值均为真时，返回真，否则返回假：
//判断栈是否为空为空返回1，非空返回0
bool myStackEmpty(MyStack* obj)
{
assert(obj);
if (QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2))//当两个队列全为空时才为空
{
return 1;
}
else
{
return 0;
}
}
压栈
压栈时，我们需要将元素插入到不为空的那个队列中，若均为空，就随便插入一个：
插入时，我们就直接复用插入队列函数QueuePush即可：
//从栈顶入栈
void myStackPush(MyStack* obj, int x)
{
assert(obj);
if (QueueEmpty(&obj->q1)==0)//在有数据的那个队列入栈
{
assert(QueueEmpty(&obj->q2));
QueuePush(&obj->q1, x);
}
else
{
assert(QueueEmpty(&obj->q1));
QueuePush(&obj->q2, x);
}
}
出栈
出栈时，我们需要将有元素的那个队列中的元素转移到空的队列中，直到剩一个元素。将这个元素移除即可：
在转移元素时，我们可以复用 QueueFront函数，取出队列头的元素，再用QueuePush插入到另一个队列的尾。然后再QueuePop，删除原队列中的首元素即可：
//从栈顶出栈
int myStackPop(MyStack* obj)
{
assert(obj && myStackEmpty(obj)==0);
QDataType ret = 0;
//将有数据的那个队列转移到空队列中，返回剩下的那个数据
if(QueueEmpty(&obj->q1)==0 && QueueEmpty(&obj->q2))
{
while (obj->q1.size > 1)
{
QueuePush(&obj->q2, QueueFront(&obj->q1));
QueuePop(&obj->q1);
}
ret = QueueFront(&obj->q1);
QueuePop(&obj->q1);
}
else if (QueueEmpty(&obj->q2)==0 && QueueEmpty(&obj->q1))
{
while (obj->q2.size > 1)
{
QueuePush(&obj->q1, QueueFront(&obj->q2));
QueuePop(&obj->q2);
}
ret = QueueFront(&obj->q2);
QueuePop(&obj->q2);
}
else
{
return EOF;
}
return ret;
}
访问栈顶元素
访问栈顶元素时，即访问有元素的那个队列的尾元素即可。
我们可以直接复用访问队列尾元素的 QueueBack函数：
//访问栈顶元素
int myStackTop(MyStack* obj)
{
assert(obj && myStackEmpty(obj) == 0);
QDataType ret = 0;
if (QueueEmpty(&obj->q1) == 0 && QueueEmpty(&obj->q2))//访问有数据的那个队列的尾数据
{
ret = QueueBack(&obj->q1);
}
else if (QueueEmpty(&obj->q2) == 0 && QueueEmpty(&obj->q1))
{
ret = QueueBack(&obj->q2);
}
else
{
return EOF;
}
return ret;
}
栈的释放
释放栈时，直接复用队列释放函数QueueDestroy，分别释放两个队列。最后再释放动态开辟的结构体变量即可：
//释放栈
void myStackFree(MyStack* obj)
{
QueueDestroy(&obj->q1);
QueueDestroy(&obj->q2);
free(obj);
}
总结
到此，关于用两个队列实现栈的题目就介绍完了，在下一篇文章中将介绍用两个栈实现队列，欢迎大家持续关注哦
如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题，欢迎大家在评论区提出
如果本文对你有帮助，希望一键三连哦
希望与大家共同进步哦
