大前端

前端学习之家-大前端

算法开启队列转栈武魂

文章目录

  • ==**队列接口见 [算法开启小码农队列血脉](https://blog.csdn.net/diandengren/article/details/121072953?spm=1001.2014.3001.5501)**==
  • 用队列实现栈
    • 题目
      • 栈结构体
      • 栈初始化
      • 入“栈”
      • 出“栈”并取栈顶元素
      • 取栈顶元素
      • 判断栈空
      • 栈销毁
      • 栈代码(接口代码去我上面文章取) [算法开启小码农队列血脉](https://blog.csdn.net/diandengren/article/details/121072953?spm=1001.2014.3001.5501)

队列接口见 算法开启小码农队列血脉

用队列实现栈

题目

image-20211101211340400

栈结构体

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) {
    if(!QueueErase(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else//两个都为空时push给q2
    {
        QueuePush(&obj->q2,x);
    }
}

出“栈”并取栈顶元素

int myStackPop(MyStack* obj) {
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;//假设q2空,q1非空
    //不是我们就互换位置
    if(!QueueErase(emptyQ))
    {
        nonemptyQ = &obj->q1;
        emptyQ = &obj->q2;
    }
    //非空队长大于一时朝空队里面挪动数据
    while(QueueSize(nonemptyQ)>1)
    {
        //把非队空的对头数拿出push给对空的
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        //然后把非队空的对头数pop掉
        QueuePop(nonemptyQ);
    }
    //因为要返回栈顶数据所以存完再pop
    int tmp = QueueFront(nonemptyQ);
    //此时非空队就只还有一个数据,pop掉就行
    QueuePop(nonemptyQ);
    return tmp;
}

取栈顶元素

int myStackTop(MyStack* obj) {
    //谁不为空就去谁队尾数据
    if(!QueueErase(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

判断栈空

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

栈销毁

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

image-20211102002834360

栈代码(接口代码去我上面文章取) 算法开启小码农队列血脉


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) {
    if(!QueueErase(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else//两个都为空时push给q2
    {
        QueuePush(&obj->q2,x);
    }
}

int myStackPop(MyStack* obj) {
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;//假设q2空,q1非空
    //不是我们就互换位置
    if(!QueueErase(emptyQ))
    {
        nonemptyQ = &obj->q1;
        emptyQ = &obj->q2;
    }
    //非空队长大于一时朝空队里面挪动数据
    while(QueueSize(nonemptyQ)>1)
    {
        //把非队空的对头数拿出push给对空的
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        //然后把非队空的对头数pop掉
        QueuePop(nonemptyQ);
    }
    //因为要返回栈顶数据所以存完再pop
    int tmp = QueueFront(nonemptyQ);
    //此时非空队就只还有一个数据,pop掉就行
    QueuePop(nonemptyQ);
    return tmp;
}

int myStackTop(MyStack* obj) {
    //谁不为空就去谁队尾数据
    if(!QueueErase(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

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

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

发表评论:

Copyright Your WebSite.Some Rights Reserved.