自学内容网 自学内容网
自学内容网 > 正文

用队列实现栈

🕗 发布于 2024-04-19 17:55 算法  c++  c语言  leetcode  数据结构  

文章目录

我们一起来看这样一道题目

题目介绍

链接: 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;
};

原文地址：https://blog.csdn.net/m0_70980326/article/details/137794391

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024