用队列实现栈
文章目录
- 题目介绍
- 思路分析
- 代码实现
- C语言版本
- C++版本
我们一起来看这样一道题目
题目介绍
链接: link
栈和队列呢我们之前的文章都有讲解过，当时栈我们是用顺序表（数组）来实现的，队列采用单链表来实现的。 而现在这道题呢要让我们用两个队列去实现一个栈，那该怎么做呢？
思路分析
其实也挺好搞的，我们来一起分析一下：
栈是先进后出，队列是先进先出
现在呢，有两个队列，但是我们要把它当作栈来看，那就要实现先进后出/后进先出 那现在我来入栈几个数据，比如1 2 3 4，先随便找一个队列放进去
然后我要出栈pop，那应该出谁呢？ 🆗，栈上后进先出，所以现在出栈的话应该是出4。 可是，现在数据放在队列里面，队列只允许在队尾入数据，队头出数据
所以现在想要出数据的话只能是1 2 3 4的顺序，那如何做到让4先出呢？ 🆗，那还有另一个队列我们还没用，我们可以借助另外一个队列来完成。 怎么做呢？ 我们把非空队列的前size-1个元素导入到空队列
然后此时原来的非空队列只剩下一个元素，把它出队列，不就相当于pop了栈顶的元素嘛。
那我要继续出栈，就该3了，怎么办呢？ 是不是同样的操作啊，把非空队列的前size-1个元素导入到空队列，非空队列剩下的唯一一个元素就是栈顶元素，把该元素出队列就相当于删除栈顶元素。
所以，我们要想实现栈的先进后出，如果栈不为空的情况下是不是要始终保持一个队列为空，数据全放在另一个队列啊，然后pop出栈的时候把非空队列的前size-1个元素导入到空队列，非空队列剩下的唯一一个元素就是栈顶元素，把该元素出队列就相当于删除栈顶元素。 如果两个队列都为空那就是栈为空。
🆗，那分析到这里就差不多了。
我们再来看下题目要求：
我们要实现这四个接口，经过上面的分析其实很简单了 push： 数据压栈的时候哪个队列不为空就插到那个里面，要始终保持一个队列为空（都为空随便选一个） pop： 找出空队列和非空队列，把非空队列的前size-1个元素导入到空队列，非空队列剩下的唯一一个元素就是栈顶元素，把该元素出队列就相当于删除栈顶元素 top： 获取栈顶元素，需要像pop那样导数据吗？ 不需要，队列有一个接口是获取队尾元素，队尾元素就是栈顶元素，直接调用即可。
empty： 判空，如果两个队列都为空，就是栈为空
代码实现
我们来写一下代码：
C语言版本
这道题如果用C语言写的话，会麻烦一点，因为需要我们自己造轮子，写一个队列的数据结构，不过我们之前实现过，可以直接用：
我就直接拷贝过来
然后我们来写这道题的代码：
题目给的代码模板是这样的，我们来写一下
首先这个就是栈的结构定义嘛，当然他这里给的是一个匿名结构体，那正常匿名结构体类型只能在定义的时候创建结构体变量，后面再想利用这个结构体类型创建变量就做不到了。 不过他这里进行了一个typedef，这样后面就可以使用MyStack这个类型了。 那这个很简单，它的成员变量就是两个队列嘛
继续：
有个myStackCreate，顾名思义就是让我们创建Mystack结构体变量，当然同时也要进行一个初始化（创建+初始化） 最终返回结构体变量的地址
然后剩下的接口就是我们上面分析过的了
就不再多解释了 最后呢，由于我们用的是C语言，所以还有一个free
这里要注意不能直接free obj就完事了，因为它内部还包含两个队列也是在堆上
ps：除了obj指针在栈上，其余都在堆上
那就写完了：
就过啦
typedef int QDataType;
//结点结构
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
//队列结构
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(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->head = NULL;
pq->tail = NULL;
pq->size = 0;
}
//销毁队列
void QueueDestory(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* nextnode = cur->next;
free(cur);
cur = nextnode;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
//队尾入数据
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
//队头出数据
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next == NULL)
{
free(pq->head);
pq->head = pq->tail = NULL;
}
else
{
QNode* nextnode = pq->head->next;
free(pq->head);
pq->head = nextnode;
}
pq->size--;
}
//取队头元素
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
//取队尾元素
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
//队列判空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
//return pq->head == NULL && pq->tail == NULL;
}
//求队列有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
//---------------------------------------（上面自己造轮子）
//匿名结构体类型（进行了一个typedef）
typedef struct {
Queue q1;
Queue q2;
} MyStack;
//创建Mystack结构体变量（要在堆上，否则出作用域就销毁了）并初始化
MyStack* myStackCreate() {
MyStack* obj=(MyStack*)malloc(sizeof(MyStack));//OJmalloc可以不检查（不会失败）
QueueInit(&obj->q1);
QueueInit(&obj->q2);
return obj;
}
//哪个队列不为空就插到那个里面（都为空随便选一个）
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1,x);
}
else
{
QueuePush(&obj->q2,x);
}
}
int myStackPop(MyStack* obj) {
//找出空队列和非空队列
Queue* emptyq=&obj->q1;
Queue* nonemptyq=&obj->q2;
if(QueueEmpty(&obj->q2))
{
emptyq=&obj->q2;
nonemptyq=&obj->q1;
}
//把非空队列的前size-1个元素导入到空队列
while(QueueSize(nonemptyq)>1)
{
QueuePush(emptyq,QueueFront(nonemptyq));
QueuePop(nonemptyq);
}
//非空队列剩下的唯一一个元素就是栈顶元素
int top=QueueFront(nonemptyq);
//删除栈顶元素
QueuePop(nonemptyq);
return top;
}
//oj加不加断言都可以
//非空队列队尾的元素就是栈顶元素
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&obj->q1))
return QueueBack(&obj->q1);
else
return QueueBack(&obj->q2);
}
//两个队列都为空才是栈为空
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
//不能直接free obj，因为它内部还包含两个队列在堆上
void myStackFree(MyStack* obj) {
QueueDestory(&obj->q1);
QueueDestory(&obj->q2);
free(obj);
obj=NULL;
}C++版本
那当然如果大家学过C++的话，这道题用C++来搞就会方便很多，因为STL里面就有stack这个模板类。我们可以直接用
各个接口实现的思路还是一样的，就不在多说了
class MyStack {
public:
MyStack() {
}
void push(int x) {
if(!q1.empty())
q1.push(x);
else
q2.push(x);
}
int pop() {
queue<int>& noemptyq = q1.empty() ? q2 : q1;
queue<int>& emptyq = q1.empty() ? q1 : q2;
while(noemptyq.size()>1)
{
emptyq.push(noemptyq.front());
noemptyq.pop();
}
int top=noemptyq.front();
noemptyq.pop();
return top;
}
int top() {
if(!q1.empty())
return q1.back();
else
return q2.back();
}
bool empty() {
return q1.empty()&&q2.empty();
}
private:
queue<int> q1;
queue<int> q2;
};