队列实现栈

发表于 分类于
本文详细讲解了基于C语言用队列实现栈

介绍

题目来源

题目来源于力扣网站:队列实现栈
 
题目

原理讲解

题目要求使用队列的标准操作，关于队列的讲解可以看这篇文章:队列

之前我们在讲解用栈实现队列的时候，关键点在于栈可以逆序。而这个问题中，队列是无法逆序的，那该采用什么样的结构呢？

栈每次弹出的都是最后入栈的那个元素，而最后一个元素在队列中就是队尾元素，所以可以让队列将除了队尾元素外其他元素全部头删，最后一次头删就相当于出栈。但是这样就会丢失前面的所有元素，所以需要需要另一个队列来保存前面的元素。

到此，基本的结构我们已经清楚了，但是出现了另外一个问题。
在栈实现队列中我们规定了两个栈，一个负责尾插，一个负责头删。但是这个问题中，应该如何规定两个队列的功能呢？

我们来看下面的过程：
此时q2为空，执行一次出栈，q1头删1，2；q2尾插1，2
过程1
此时q1头删3，相当于栈执行出栈
过程2
出栈完成之后，q1为空
过程3
按照刚才的逻辑，如果需要继续执行出栈，需要q2头删1…后面继续刚才的逻辑

不知道你有没有观察到，在每次执行出栈的时候，一个队列为空，另一个队列有数据，这就是刚才问题的答案。

不同于之前的栈实现队列，我们没有办法规定两个队列一个入栈一个出栈，因为在操作过程中队列为空的状态一直在交替。
通过上面的图示，不难看出，执行出栈的时候，为空的队列用来接收前面的元素，不为空的队列将元素全部头删，所以两个队列的功能由是否为空来决定

到此，基本原理已经解释完毕，我们上代码实现

代码实现

队列的基本操作如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
typedef int QDataType;
typedef struct QueueNode
{
	QueueNode* next;
	QDataType val;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//尾插
void QueuePush(Queue* pq, QDataType val);
//头删
void QueuePop(Queue* pq);
//队列元素数量
int QueueSize(Queue* pq);
//获取队列头
QDataType QueueFront(Queue* pq);
//获取队列尾
QDataType QueueBack(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);

栈结构

根据前面的原理解释，栈的结构内部由两个队列构成

1
2
3
4
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

初始化

 
对栈初始化，返回栈指针
内部分别对两个队列执行初始化

1
2
3
4
5
6
MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

销毁

 
销毁栈，传入栈的指针
内部直接调用队列的销毁函数
最后释放栈指针

1
2
3
4
5
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

入栈

 
传入栈指针和新数据值x
通过原理讲解我们知道，入栈需要往不为空的队列尾插
直接判断哪个队列不为空，对其执行尾插即可

1
2
3
4
5
6
7
8
9
10
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}

出栈

假设法

 
在下面函数中我们采用假设法来寻找空和非空队列
在不确定哪个队列为空时，顾名思义，我们先假设任意一个队列为空，例如下面代码中的q1
接着令另一个为非空
然后对刚刚假设为空的队列进行判空，如果假设为空，但是实际非空，那么交换empty和noempty的值即可

1
2
3
4
5
6
7
Queue* empty = &obj->q1;
Queue* noempty = &obj->q2;
if(!QueueEmpty(&obj->q1))
{
    empty = &obj->q2;
    noempty = &obj->q1;
}

假设法是一种非常巧妙的方法，可以减少重复书写代码
例如在这个题中，如果不用假设法，那么我们需要分两个情况分别写一套流程

出栈函数

 
传入栈指针，返回出栈元素
使用假设法找到非空和空队列，将noempty中队头元素尾插到empty中，然后noempty执行头删，直到noempty中只剩下最后一个元素
用ret保存noempty的队头元素
将noempty头删
最后返回ret

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int myStackPop(MyStack* obj) {
    //假设法
    Queue* empty = &obj->q1;
    Queue* noempty = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }
    while(QueueSize(noempty)>1)
    {
        QueuePush(empty,QueueFront(noempty));
        QueuePop(noempty);
    }
    int ret = QueueFront(noempty);
    QueuePop(noempty);
    return ret;
}

获取栈顶元素

在原理中我们讲到，在出栈前后，两个队列至少有一个为空
栈顶元素也就是不为空队列中的队尾元素，这个位置的元素可以直接用QueueBack函数拿到

1
2
3
4
5
6
7
8
9
10
int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

判空

判断栈是否为空，返回bool值
直接对两个队列判空即可

1
2
3
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

总结

用队列实现栈中，关键点在于，两个队列至少有一个为空，而队列为空的状态是交替进行的，因此用是否为空来决定队列的作用

在简化代码方面，在书写出栈代码时，我们使用了假设法，避免了重复书写同一套流程

最后，这是代码的通过截图
通过截图

如果文章内容有误，欢迎指出