备案控制台
开发者社区 云计算 文章 正文

【DS】两个队列实现栈&两个栈实现队列@Leetcode —— 栈和队列

2022-07-29 92
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 两个队列实现栈&两个栈实现队列

@TOC
这两道题目太经典了，就是栈的先进后出与队列的先进先出，来相互实现对方的性质，很有意思。

在这里插入图片描述

正文开始@边通书

1. 两个队列实现栈

1.1 题目

题目链接：用队列实现栈
在这里插入图片描述

1.2 思路

用两个栈实现队列，就是用队列来满足栈入数据&出数据的性质，即实现后进先出。

:blue_heart:1. 出数据，把前(n-1)个数据依次转移（东北话倒腾）到另一个队列里，最后一个pop掉。实现后进先出。
在这里插入图片描述
:blue_heart:2. 入数据，哪一个队列非空，就入哪一个队。保持数据顺序。
在这里插入图片描述

1.3 题解

前置文章：队列@栈和队列

有了思路就开动吧！本题复杂在于它的结构。你要把每个函数接口都做了什么谙熟于心，不然就可能犯错。

把队列基本操作的函数接口暂时省略掉的函数接口去掉 ——

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

MyStack* myStackCreate() {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);
    //往非空的队列中入
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        //可以处理q1,q2都为空的情况，就随便找一个入就okay
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    assert(obj);
    // 假设法
    Queue* nonemptyQ = &obj->q1;
    Queue* emptyQ = &obj->q2;
    if(QueueEmpty(&obj->q1))
    {
        nonemptyQ = &obj->q2;
        emptyQ = &obj->q1;
    }
    //1.把前(size-1)个元素倒腾到另一个队列中
    while(QueueSize(nonemptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }
    //2.把最后一个元素pop掉
    QDataType pop = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
    return pop;
}

int myStackTop(MyStack* obj) {
    assert(obj);
    //取队尾元素
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

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

void myStackFree(MyStack* obj) {
    assert(obj);
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);//注意释放顺序--防止内存泄漏
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

注意：
:black_heart: 1. 初始化时，写成Mystack st; return &st;就是经典的野指针问题。st是局部变量，是调用函数接口来创建结构体，这与在main函数中初始化不同。
:black_heart: 2.在入栈操作我们仍使用了经典的假设法。我们假设的emptyQ和nonemptyQ都是q1和q2的地址，因为都是要对这两个队列本身操作。
:black_heart: 3.两道题目都要注意销毁的处理，否则会发生内存泄漏。free是要分层的，注意释放顺序。
在这里插入图片描述

2. 两个栈实现队列

2.1 题目

题目链接：用栈实现队列
在这里插入图片描述

2.2 思路

第一次做这个的时候，我受到了上一道题目的影响，自己弄了一个天马行空的思路，总之就是倒来倒去，确实没有经典思路好。

总之，还是要满足队列出数据&入数据先进先出的性质。

:blue_heart:1. 一个栈是pushST，另一个是popST。
出数据时，把pushST中的数据弹栈倒腾到popST中，实现了先进先出。此后，若要出数据，直接在popST弹栈即可。若出空了，就再如上倒腾一下。
在这里插入图片描述

:blue_heart:2.入数据，就只管往pushST中入就行。保持了数据的顺序。
在这里插入图片描述

2.3 题解

前置文章： 栈@栈和队列
做过上一道题目，有了那么多小注意，这个应该很顺手嘞~它们验主义的都是一样的。

typedef struct {
    ST pushST;
    ST popST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&q->pushST);
    StackInit(&q->popST);
    return q;
}

void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    StackPush(&obj->pushST,x);
}

int myQueuePop(MyQueue* obj) {
    assert(obj);
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    int top = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return top;
}

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);
}

bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}

void myQueueFree(MyQueue* obj) {
    assert(obj);
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/

附

还是由于需要借助栈和队列的数据结构，逻辑中再写一遍基本的接口很麻烦，把之前写好的函数接口贴过来了。因为会造成文章冗长，前面都只写了主体逻辑，现在把完整的贴过来嗷，有需要自取。

//两个队列实现栈
typedef int QDataType;

//队列
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;

//多个变量，那就用结构体封起来
typedef struct Queue
{
    QueueNode* head;
    QueueNode* tail;
}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);
//求队列中有效元素个数
int QueueSize(Queue* pq);
//判断队列是否为空？
bool QueueEmpty(Queue* pq);

void QueueInit(Queue* pq)
{
    assert(pq);
    pq->head = pq->tail = NULL;
}

void QueueDestroy(Queue* pq)
{
    assert(pq);
    QueueNode* cur = pq->head;
    while (cur)
    {
        QueueNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    newnode->data = x;
    newnode->next = NULL;
    if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;//迭代
    }
}

void QueuePop(Queue* pq)
{
    assert(pq);
     assert(!QueueEmpty(pq));
    QueueNode* newhead = pq->head->next;
    free(pq->head);
    pq->head = newhead;
    if (pq->head == NULL)
    {
        pq->tail = NULL;
    }
}

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;
}

int QueueSize(Queue* pq)
{
    assert(pq);
    int size = 0;
    QueueNode* cur = pq->head;
    while (cur)
    {
        cur = cur->next;
        size++;
    }
    return size;
}

bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

MyStack* myStackCreate() {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);
    //往非空的队列中入
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        //可以处理q1,q2都为空的情况，就随便找一个入就okay
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    assert(obj);
    // 假设法
    Queue* nonemptyQ = &obj->q1;
    Queue* emptyQ = &obj->q2;
    if(QueueEmpty(&obj->q1))
    {
        nonemptyQ = &obj->q2;
        emptyQ = &obj->q1;
    }
    //1.把前(size-1)个元素倒腾到另一个队列中
    while(QueueSize(nonemptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        QueuePop(nonemptyQ);
    }
    //2.把最后一个元素pop掉
    QDataType pop = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
    return pop;
}

int myStackTop(MyStack* obj) {
    assert(obj);
    //取队尾元素
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

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

void myStackFree(MyStack* obj) {
    assert(obj);
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);//注意释放顺序--防止内存泄漏
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/
//两个栈实现队列
typedef int STDataType;
typedef struct Stack
{
    STDataType* a;
    int top;//栈顶位置
    int capacity;
}ST;

void StackInit(ST* ps);
void StackDestroy(ST* ps);

//压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//取栈顶数据
STDataType StackTop(ST* ps);
//栈中数据多少？
int StackSize(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);

void StackInit(ST* ps)
{
    assert(ps);
    ps->a = NULL;
    ps->top = 0;
    //初始化时,top给-1,意味着top指向栈顶数据：先+1,再放数据
    //初始化时，top给0，意味着top指向栈顶数据的下一个：先放数据，再++
    ps->capacity = 0;
}

void StackDestroy(ST* ps)
{
    assert(ps);
    free(ps->a);
    ps->a = NULL;//有必要，不然就是野指针了
    ps->top = 0;
    ps->capacity = 0;
}

void StackPush(ST* ps, STDataType x)
{
    assert(ps);
    if (ps->top == ps->capacity)
    {
        int newcapacity = (ps->capacity == 0) ? 4 : 2 * ps->capacity;
        STDataType* ptr = (STDataType*)realloc(ps->a, newcapacity *sizeof(STDataType));
        if (ptr == NULL)
        {
            printf("realloc failed\n");
            exit(-1);
        }
        ps->a = ptr;
        ps->capacity = newcapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

void StackPop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));//断言，栈不为空--这样调用函数不会受到你实现方式的影响
    ps->top--;
}

int StackSize(ST* ps)
{
    assert(ps);
    return ps->top;
}

bool StackEmpty(ST* ps)
{
    assert(ps);
    return ps->top == 0;
}

STDataType StackTop(ST* ps)
{
    assert(ps);
    assert(!StackEmpty(ps));
    return ps->a[ps->top - 1]; //注意是top - 1
}


typedef struct {
    ST pushST;
    ST popST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&q->pushST);
    StackInit(&q->popST);
    return q;
}

void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    StackPush(&obj->pushST,x);
}

int myQueuePop(MyQueue* obj) {
    assert(obj);
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    int top = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return top;
}

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);
}

bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}

void myQueueFree(MyQueue* obj) {
    assert(obj);
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/
关键词：
LeetCode栈
LeetCode队列
LeetCode栈和队列
队列LeetCode
栈LeetCode
@浮光掠影
目录
相关文章
誓则盟约
|
2天前
|
存储 算法 索引
力扣每日一题 6/24 模拟 数组 单调栈
力扣每日一题 6/24 模拟 数组 单调栈
誓则盟约
6 0
一只大鸽子
|
16天前
|
存储 算法 Python
二刷力扣--栈和队列
二刷力扣--栈和队列
一只大鸽子
9 1
数据分析螺丝钉
|
21天前
|
存储 算法 数据可视化
力扣155题最全解法：如何实现支持常数时间获取最小值的最小栈（附详细图解和复杂度分析）
力扣155题最全解法：如何实现支持常数时间获取最小值的最小栈（附详细图解和复杂度分析）
数据分析螺丝钉
14 1
知更鸟呆呆
|
17天前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~
知更鸟呆呆
33 0
数据分析螺丝钉
|
21天前
|
存储 SQL 算法
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
数据分析螺丝钉
12 0
数据分析螺丝钉
|
21天前
|
存储 SQL 算法
LeetCode 题目 94：五种算法递归｜迭代｜莫里斯｜线索二叉树｜栈的迭代二叉树 实现中序遍历
LeetCode 题目 94：五种算法递归｜迭代｜莫里斯｜线索二叉树｜栈的迭代二叉树 实现中序遍历
数据分析螺丝钉
13 0
数据分析螺丝钉
|
21天前
|
SQL 算法 数据挖掘
探索有效括号 力扣第20题：从栈到递归的多角度解法 【含图解 python】
探索有效括号 力扣第20题：从栈到递归的多角度解法 【含图解 python】
数据分析螺丝钉
15 0
叶落闲庭
|
2月前
|
索引
【力扣刷题】数组实现栈、后缀表达式（逆波兰表达式）求值、中缀表达式转换为后缀表达式（无括号&&有括号）
【力扣刷题】数组实现栈、后缀表达式（逆波兰表达式）求值、中缀表达式转换为后缀表达式（无括号&&有括号）
叶落闲庭
23 0
爱喝兽奶的熊孩子
|
16天前
|
算法 C++
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-2
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
爱喝兽奶的熊孩子
21 2
爱喝兽奶的熊孩子
|
16天前
|
算法 C++
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-1
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
爱喝兽奶的熊孩子
27 2