【栈与队列】栈与队列的相互转换OJ题-阿里云开发者社区

【栈与队列】栈与队列的相互转换OJ题

2024-05-08 11

版权

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

简介： 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

1 栈与队列

1.1 栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.2 队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 的原则

入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

1.3 差别与关系

通过上述的介绍，栈与队列仿佛毫不相干，一个先入先出，一个后入后出。

栈像一个容器来装物品，队列像排队买饭。这两个事情看起来毫不相干，那么如何实现栈与队列的相互转换呢。下面我们来看两道OJ题，来进行具体解决。

2 栈与队列的相互转换

2.1 队列模拟实现栈

我们来看题目描述

这道题给了我们六个接口，接下来我们来逐一完成。

首先先把队列的代码拷贝到代码区，方便我们使用队列中的对应接口。、

2.1.1 栈的结构体设置

首先，我们来分析一下怎样通过队列来模拟栈

我们看，我们模拟一下发现，删除操作只需要将一个队列的前n个数据迁移到另一个队列就可以，那我们不妨就假设看看两个队列能否实现栈。

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

2.1.2 初始化接口

非常简单的我们初始化一下

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

2.1.3 压栈操作

void myStackPush(MyStack* obj, int x) {
    Queue* emptyQueue = &obj->q1;
    Queue* unemptyQueue = &obj->q2;
    if (!QueueEmpty(emptyQueue)) {
        emptyQueue = &obj->q2;
        unemptyQueue = &obj->q1;
    }
    QueuePush(unemptyQueue, x);
}

使用假设法来判断两个队列的空与非空，选择非空进行插入。

2.1.4 出栈

int myStackPop(MyStack* obj) {

    Queue* emptyQueue = &obj->q1;
    Queue* unemptyQueue = &obj->q2;
    if (!QueueEmpty(emptyQueue)) {
        emptyQueue = &obj->q2;
        unemptyQueue = &obj->q1;
    }

    while (QueueSize(unemptyQueue) > 1) {
        QueuePush(emptyQueue, unemptyQueue->front->data);
        QueuePop(unemptyQueue);
    }
    int ret = QueueFront(unemptyQueue);
    QueuePop(unemptyQueue);
    return ret;
}

依然是通过假设法来判断是否非空，然后依次将非空队列的前n-1个元素移动到空队列，这里的移动不是将节点的移动，而是将值赋给空队列。最后取栈顶返回值，再出栈一下非空队列，完成操作。

2.1.5 取栈顶

int myStackTop(MyStack* obj) {

    if (!QueueEmpty(&obj->q1)) {
        return QueueBack(&obj->q1);
    }
    else {
        return QueueBack(&obj->q2);
    }

}

选择判断是否为非空进行取队列顶操作即可。

2.1.6 判断是否为空

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

都为空才为空

2.1.7 销毁栈

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

一步一步free掉即可。

2.2 栈模拟实现队列

我将源码放在下面，原理与上述相似，请自行观看。

2.2.1 版本一

typedef struct {
    Stack st1;
    Stack st2; 
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&pq->st1);
    StackInit(&pq->st2);

    return pq;
}

void myQueuePush(MyQueue* obj, int x) {
    if(!StackEmpty(&obj->st1)){
        StackPush(&obj->st1,x);
    }
    else{
        StackPush(&obj->st2,x);
    }

}

int myQueuePop(MyQueue* obj) {
    //判断 空与非空
    Stack* empty_st = &obj->st1;
    Stack* nonempty_st = &obj->st2;
    if(!StackEmpty(&obj->st1)){
        empty_st = &obj->st2;
        nonempty_st = &obj->st1;
    }
    //转移元素
    while(StackSize(nonempty_st)>1){
        StackPush(empty_st,StackTop(nonempty_st));
        StackPop(nonempty_st);
    }
    
    int del = StackTop(nonempty_st);
    StackPop(nonempty_st);
    while(!StackEmpty(empty_st)){
        StackPush(nonempty_st,StackTop(empty_st));
        StackPop(empty_st);
    }
    return del;
    
}

int myQueuePeek(MyQueue* obj) {
     //判断 空与非空
    Stack* empty_st = &obj->st1;
    Stack* nonempty_st = &obj->st2;
    if(!StackEmpty(&obj->st1)){
        empty_st = &obj->st2;
        nonempty_st = &obj->st1;
    }
    while(StackSize(nonempty_st)>1){
        StackPush(empty_st,StackTop(nonempty_st));
        StackPop(nonempty_st);
    }
    int ret = StackTop(nonempty_st);
    while(!StackEmpty(empty_st)){
        StackPush(nonempty_st,StackTop(empty_st));
        StackPop(empty_st);
    }
    return ret;
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->st1) && StackEmpty(&obj->st2);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->st1);
    StackDestroy(&obj->st2);
    free(obj);
}