大前端

前端学习之家-大前端

算法开启栈转队列武魂

文章目录

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

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

用栈实现队列

题目

image-20211102223625269

队结构体

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) {
    StackPush(&obj->PushST,x);
}

出“队”并取出队元素

int myQueuePop(MyQueue* obj) {
    //如果出队栈为空就从入队栈里面全导过来
    if(StackEmpty(&obj->PopST))
    {
        //导数据
        while(!StackEmpty(&obj->PushST))
        {
            //入队栈栈顶元素拿出来给出队栈
            StackPush(&obj->PopST,StackTop(&obj->PushST));
            //栈把入队栈的栈顶元素pop掉
            StackPop(&obj->PushST);
        }
    }
    //这时就说明都倒完了,所以开始pop掉出队栈元素
    int tmp = StackTop(&obj->PopST);
    StackPop(&obj->PopST);
    return tmp;
}

返回队头

int myQueuePeek(MyQueue* obj) {
    //如果出队栈为空就从入队栈里面全导过来
    if(StackEmpty(&obj->PopST))
    {
        //导数据
        while(!StackEmpty(&obj->PushST))
        {
            //入队栈栈顶元素拿出来给出队栈
            StackPush(&obj->PopST,StackTop(&obj->PushST));
            //栈把入队栈的栈顶元素pop掉
            StackPop(&obj->PushST);
        }
    }
    //就是出队函数那样只取队头而已
    return StackTop(&obj->PopST);
}

判断队空

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->PushST) && StackEmpty(&obj->PopST);
}

队列销毁

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->PushST);
    StackDestroy(&obj->PopST);
    free(obj);
}

image-20211103001539223

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


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) {
    StackPush(&obj->PushST,x);
}

int myQueuePop(MyQueue* obj) {
    //如果出队栈为空就从入队栈里面全导过来
    if(StackEmpty(&obj->PopST))
    {
        //导数据
        while(!StackEmpty(&obj->PushST))
        {
            //入队栈栈顶元素拿出来给出队栈
            StackPush(&obj->PopST,StackTop(&obj->PushST));
            //栈把入队栈的栈顶元素pop掉
            StackPop(&obj->PushST);
        }
    }
    //这时就说明都倒完了,所以开始pop掉出队栈元素
    int tmp = StackTop(&obj->PopST);
    StackPop(&obj->PopST);
    return tmp;
}

int myQueuePeek(MyQueue* obj) {
    //如果出队栈为空就从入队栈里面全导过来
    if(StackEmpty(&obj->PopST))
    {
        //导数据
        while(!StackEmpty(&obj->PushST))
        {
            //入队栈栈顶元素拿出来给出队栈
            StackPush(&obj->PopST,StackTop(&obj->PushST));
            //栈把入队栈的栈顶元素pop掉
            StackPop(&obj->PushST);
        }
    }
    //就是出队函数那样只取队头而已
    return StackTop(&obj->PopST);
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->PushST) && StackEmpty(&obj->PopST);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->PushST);
    StackDestroy(&obj->PopST);
    free(obj);
}

发表评论:

Copyright Your WebSite.Some Rights Reserved.