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

简介: 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出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);
}

2.2.2 优化版本二

Thanks♪(・ω・)ノ


相关文章
|
4天前
|
存储 索引
【数据结构OJ题】设计循环队列
力扣题目——设计循环队列
14 1
【数据结构OJ题】设计循环队列
|
4天前
【数据结构OJ题】有效的括号
力扣题目——有效的括号
10 1
【数据结构OJ题】有效的括号
|
4天前
|
存储 前端开发 DataX
【数据结构】栈和队列
数据结构中的栈和队列
10 1
【数据结构】栈和队列
|
5天前
【数据结构OJ题】复制带随机指针的链表
力扣题目——复制带随机指针的链表
12 1
【数据结构OJ题】复制带随机指针的链表
|
4天前
【数据结构OJ题】用栈实现队列
力扣题目——用栈实现队列
11 0
【数据结构OJ题】用栈实现队列
|
4天前
【数据结构OJ题】用队列实现栈
力扣题目——用队列实现栈
15 0
【数据结构OJ题】用队列实现栈
|
28天前
|
算法 C语言
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
【数据结构与算法 经典例题】使用栈实现队列(图文详解)
|
22天前
|
存储 缓存 算法
堆和栈的区别及应用场景
堆和栈的区别及应用场景
|
28天前
|
存储 测试技术
【数据结构】操作受限的线性表,栈的具体实现
【数据结构】操作受限的线性表,栈的具体实现
30 5
|
28天前
|
算法 C语言
【数据结构与算法 经典例题】使用队列实现栈(图文详解)
【数据结构与算法 经典例题】使用队列实现栈(图文详解)