AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

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

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

在这里插入图片描述

正文开始@边通书

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
@浮光掠影
目录
相关文章
Codelinghu
|
1月前
【LeetCode 24】225.用队列实现栈
【LeetCode 24】225.用队列实现栈
Codelinghu
12 0
Codelinghu
|
1月前
|
算法
【LeetCode 23】232.用栈实现队列
【LeetCode 23】232.用栈实现队列
Codelinghu
19 0
BetterBench
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码，确保min、push和pop操作的时间复杂度为O(1)。
BetterBench
28 4
BetterBench
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 09. 用两个栈实现队列
使用两个栈实现队列的Python解决方案，包括初始化两个栈、实现在队列尾部添加整数的appendTail方法和在队列头部删除整数的deleteHead方法，以及相应的示例操作。
BetterBench
39 2
BetterBench
|
3月前
|
Python
【Leetcode刷题Python】641.循环双端队列
文章介绍了如何实现一个循环双端队列，包括其操作如插入、删除、获取队首和队尾元素，以及检查队列是否为空或已满，并提供了Python语言的实现代码。
BetterBench
25 0
BetterBench
|
3月前
|
Python
【Leetcode刷题Python】232. 用栈实现队列
如何使用Python语言通过两个栈来实现队列的所有基本操作，包括入队(push)、出队(pop)、查看队首元素(peek)和判断队列是否为空(empty)，并提供了相应的代码实现。
BetterBench
21 0
yantuguiguziPGJ
|
2月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案，包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行，每个问题都给出了至少一种实现方法。
yantuguiguziPGJ
56 6
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
BetterBench
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法，用于按照之字形顺序打印二叉树的层次遍历结果，实现了在奇数层正序、偶数层反序打印节点的功能。
BetterBench
57 6
BetterBench
|
3月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法，提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法，并给出了Python实现代码。
BetterBench
114 2
楠竹11
|
23天前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF，全方位评估OpenAI o1，Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来，OpenAI的o1模型在大型语言模型（LLMs）中脱颖而出，展现出卓越的推理能力和知识整合能力。基于Transformer架构，o1模型采用了链式思维和强化学习等先进技术，显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
楠竹11
19 1