1. Toy模板网首页
  2. > Toy博客

【数据结构经典题目】—两个队列实现栈与两个栈实现队列

8月前 作者：B1ue慕斯 分类：Toy博客 阅读(39) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构经典题目】—两个队列实现栈与两个栈实现队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【数据结构经典题目】—两个队列实现栈与两个栈实现队列,数据结构与算法炼体 淬体中,数据结构,c语言

​

                                         食用指南：本文在有C基础的情况下食用更佳  

                                        🔥这就不得不推荐此专栏了：C语言

                                        🍀本文前置知识： C语言实现栈与队列

                                        ♈️今日夜电波：怪獣の花唄—Vaundy

                                         3:12 ━━━━━━️💟──────── 4:13                                                                                                                                     🔄   ◀️   ⏸   ▶️    ☰

                                       💗关注👍点赞🙌收藏您的每一次鼓励都是对我莫大的支持😍 

目录

🍂两个队列实现栈

问题的描述以及要求

思路整理

具体的思路：

 每个操作的实现

 初始化

判空

入栈

 出栈

 取栈顶元素

 销毁栈

🍁整体代码

🍃两个栈实现队列

问题的描述以及要求

思路整理

具体的思路：              

每个操作的实现 

 初始化

判空

入队

出队

 取队头元素

 销毁队列

🌿整体代码

🍂两个队列实现栈

问题的描述以及要求

        使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

思路整理

        首先理清一点，队列实现是先进先出，而栈是后进先出，我们需要使用两个队列来实现栈。对此，我的思路是一个队列用于入栈用，而另外一个队列用于出栈。对此，在这个基础上设立了如下的结构体：

typedef struct QNode//队列节点
{
    int data;
    struct QNode* next;
}QNode;

typedef struct Queue//队列
{
    QNode* front;
    QNode* tail;
}Queue;

typedef struct {
    QNode q1;
    QNode q2;
} MyStack;
具体的思路：

        保持一个队列在出栈前为空的状态，而另外一个队列则是出栈前一直用于入队。然后，当程序需要出栈了，我们将不为空的那个队列，也就是用于入队的队列的前N-1个数据出队，将原本为空的那个队列入队这N-1个数据。在此之后，我们发现原本作为入队的队列仅仅剩下了最后一个数据，而原本为空的队列拥有了N-1个数据，此时那剩下的一个数据不就是栈顶的数据吗？我们只需要将这个数据进行出队操作便可。而在这个数据出队操作完成后，这个两个队列的性质进行了交换，原本为空的队列，现在拥有N-1个数据，原本不为空的队列，现在为空了，因此，在接下来的操作需要转换两个队列的入队性质。

        一图带你了解~ 

【数据结构经典题目】—两个队列实现栈与两个栈实现队列,数据结构与算法炼体 淬体中,数据结构,c语言

 每个操作的实现

 初始化
MyStack* myStackCreate() {
    MyStack* new=(MyStack*)malloc(sizeof(MyStack));
    if(new==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    QueueInit(&new->q1);
    QueueInit(&new->q2);
    return new;
}

        这里对于为什么对new->q1,new->q2取地址做出解释：由于前面结构体的定义为 QNode q1;QNode q2;而QueueInit内传参为指针所以取地址&。

判空
bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
入栈
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }else
    {
        QueuePush(&obj->q2,x);
    }
}

        入栈操作主要在于对于两个队列进行判断，判断出入上文思路所述，其中一个为空，以此，将空的队列作为入栈操作。

 出栈
int myStackPop(MyStack* obj) {
    assert(obj);

    MyStack* empty=&obj->q1;
    MyStack* nonempty=&obj->q2;

    if(!QueueEmpty(empty))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueTop(nonempty));
        QueuePop(nonempty);
    }
    int re=QueueTop(nonempty);
    QueuePop(nonempty);
    return re;
}

        出栈操作是用两个队列实现栈的最关键的一步。首先创建两个结构体指针，一个用于存放空的队列，另外一个存不为空的队列。这时候有人就要问了，你怎么知道哪个是空的哪个不是空的。别急，这不有个if的判断语句来判断吗？(*^▽^*)。接着，按照思路，将不为空的队列N-1个数据入队到原来为空的的队列，最后再对剩下的一个数据进行出栈。

 取栈顶元素
int myStackTop(MyStack* obj) {
    assert(obj);
    assert(!myStackEmpty(obj));
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

        这个简单，只需要将不为空的队列的最后一个元素给出去就好了！

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

🍁整体代码 

typedef struct QNode//队列节点
{
    int data;
    struct QNode* next;
}QNode;
typedef struct Queue//队列
{
    QNode* front;
    QNode* tail;
}Queue;
//初始化
void QueueInit(Queue* queue);
//队列是否为空
bool QueueEmpty(Queue* queue);
//进队
void QueuePush(Queue* queue, int x);
//出队
void QueuePop(Queue* queue);
//队列头部元素
int QueueTop(Queue* queue);
//队列尾部元素
int QueueBack(Queue* queue);
//队列有效元素个数
int QueueSize(Queue* queue);
//销毁队列
void QueueDestroy(Queue* queue);

void QueueInit(Queue* queue)//初始化
{
    assert(queue);
    queue->front = NULL;
    queue->tail = NULL;
}
//队列是否为空
bool QueueEmpty(Queue* queue)
{
    assert(queue);
    return queue->tail == NULL;
}
//进队
void QueuePush(Queue* queue, int x)
{
    assert(queue);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    assert(newnode);
    newnode->data = x;
    newnode->next = NULL;
    if(queue->tail == NULL)
    {
        queue->front = queue->tail = newnode;
    }
    else
    {
        queue->tail->next = newnode;
        queue->tail = newnode;
    }
}
//出队
void QueuePop(Queue* queue)
{
    assert(queue);
    QNode* next = queue->front->next;
    free(queue->front);
    queue->front = next;
    if(queue->front == NULL)
    {
        queue->tail = NULL;
    }
}
//队列头部元素
int QueueTop(Queue* queue)
{
    assert(queue);
    assert(queue->front);
    return queue->front->data;
}
//队列尾部元素
int QueueBack(Queue* queue)
{
    assert(queue);
    assert(queue->tail);
    return queue->tail->data;
}
//队列有效元素个数
int QueueSize(Queue* queue)
{
    assert(queue);
    int size = 0;
    QNode* cur = queue->front;
    while(cur != NULL)
    {
        ++size;
        cur = cur->next;
    }
    return size;
}
//销毁队列
void QueueDestroy(Queue* queue)
{
    assert(queue);
    QNode* next = queue->front;
    while(next != NULL)
    {
        next = queue->front->next;
        free(queue->front);
        queue->front = next;
    }
    queue->tail = NULL;
}


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


MyStack* myStackCreate() {
    MyStack* new=(MyStack*)malloc(sizeof(MyStack));
    if(new==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    QueueInit(&new->q1);
    QueueInit(&new->q2);
    return new;
}

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

int myStackPop(MyStack* obj) {
    assert(obj);
    MyStack* empty=&obj->q1;
    MyStack* nonempty=&obj->q2;
    if(!QueueEmpty(empty))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    while(QueueSize(nonempty)>1)
    {
        QueuePush(empty,QueueTop(nonempty));
        QueuePop(nonempty);
    }
    int re=QueueTop(nonempty);
    QueuePop(nonempty);
    return re;
}  

bool myStackEmpty(MyStack* obj);

int myStackTop(MyStack* obj) {
    assert(obj);
    assert(!myStackEmpty(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);
    obj=NULL;
}

🍃两个栈实现队列

问题的描述以及要求

        仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）。

思路整理

        首先理清一点，栈实现是后进先出，而队列是先进先出，我们需要使用两个栈来实现队列。对此，我的思路是一个栈用于入队用，而另外一个栈用于出队。对此，在这个基础上设立了如下的结构体：

typedef int STDataType;
typedef struct Stack//变长的数组栈
{
	STDataType* a;
	int top;
	int capacity;
}SLtack;

typedef struct {
    SLtack push;
    SLtack pop;
} MyQueue;
具体的思路：              

         将一个栈当作输入栈，用于压入push 传入的数据；另一个栈当作输出栈，用于 pop操作。每次 pop 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。若不为空，则只有将所有输出栈的数据都pop完后，才将输入栈的数据弹入输出栈。再对输出栈进行pop操作。

        一图让你了然~

 【数据结构经典题目】—两个队列实现栈与两个栈实现队列,数据结构与算法炼体 淬体中,数据结构,c语言

每个操作的实现 

 初始化
MyQueue* myQueueCreate() {
    MyQueue* new=(MyQueue*)malloc(sizeof(MyQueue));
    if(new==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    StackInit(&new->push);
    StackInit(&new->pop);
    return new;
}

        这里对于为什么对new->push,new->pop取地址做出解释：由于前面结构体的定义为SLtack push;SLtack pop;而StackInit内传参为指针所以取地址&。

判空
bool myQueueEmpty(MyQueue* obj) {

    return StackEmpty(&obj->push)&&StackEmpty(&obj->pop);
}
入队
void myQueuePush(MyQueue* obj, int x) {
    
    StackPush(&obj->push,x);
}

        入队操作只需要对push栈进行入栈操作即可

出队
int myQueuePop(MyQueue* obj) {

    assert(obj);
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    int re=StackTop(&obj->pop);
    StackPop(&obj->pop);
    return re;
}

        出队操作是实现两个栈实现队列的关键。需要将push栈中的数据全都压栈道pop栈，注意只有pop为空时才进行以上操作。然后就是对于pop栈进行正常的出栈操作即可。

 取队头元素
int myQueuePeek(MyQueue* obj) {
    assert(obj);
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    return StackTop(&obj->pop);
}

        这里主要还是同出队操作差不多，取队头的元素需要在pop栈上的top取！

 销毁队列
void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->push);
    StackDestroy(&obj->pop);
    free(obj);
    obj==NULL;
}

🌿整体代码 

typedef int STDataType;
typedef struct Stack//变长的数组栈
{
	STDataType* a;
	int top;
	int capacity;
}SLtack;

// 初始化栈 
void StackInit(SLtack* ps);
// 入栈 
void StackPush(SLtack* ps, STDataType data);
// 出栈 
void StackPop(SLtack* ps);
// 获取栈顶元素 
STDataType StackTop(SLtack* ps);
// 获取栈中有效元素个数 
int StackSize(SLtack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(SLtack* ps);
// 销毁栈 
void StackDestroy(SLtack* ps);

void StackInit(SLtack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;//top初始化为0，则top指向栈顶的下一个元素
}

void StackPush(SLtack* ps, STDataType data)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		ps->capacity =ps->capacity== 0 ? 4 : ps->capacity * 2;
		ps->a = (STDataType*)realloc(ps->a, sizeof(int) * ps->capacity);
	}
	ps->a[ps->top] = data;
	ps->top++;
}

void StackPop(SLtack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

STDataType StackTop(SLtack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

int StackSize(SLtack* ps)
{
	assert(ps);
	return ps->top;
}

int StackEmpty(SLtack* ps)
{
	assert(ps);
	return ps->top == 0;
}

void StackDestroy(SLtack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

typedef struct {
    SLtack push;
    SLtack pop;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* new=(MyQueue*)malloc(sizeof(MyQueue));
    if(new==NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    StackInit(&new->push);
    StackInit(&new->pop);
    return new;
}

void myQueuePush(MyQueue* obj, int x) {
    
    StackPush(&obj->push,x);
}

bool myQueueEmpty(MyQueue* obj);

int myQueuePop(MyQueue* obj) {

    assert(obj);
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    int re=StackTop(&obj->pop);
    StackPop(&obj->pop);
    return re;
}

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->pop))
    {
        while(!StackEmpty(&obj->push))
        {
            StackPush(&obj->pop,StackTop(&obj->push));
            StackPop(&obj->push);
        }
    }
    return StackTop(&obj->pop);
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->push)&&StackEmpty(&obj->pop);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->push);
    StackDestroy(&obj->pop);
    free(obj);
    obj==NULL;
}

                 感谢你耐心的看到这里ღ( ´･ᴗ･` )比心，如有哪里有错误请踢一脚作者o(╥﹏╥)o！ 

                                ​​​​​​​        【数据结构经典题目】—两个队列实现栈与两个栈实现队列,数据结构与算法炼体 淬体中,数据结构,c语言

                                                                                给个三连再走嘛~   文章来源地址https://www.toymoban.com/news/detail-636911.html

到了这里，关于【数据结构经典题目】—两个队列实现栈与两个栈实现队列的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】栈与队列经典oj题

    【数据结构】栈与队列经典oj题

    🚀write in front🚀 📜所属专栏：初阶数据结构 🛰️博客主页：睿睿的博客主页 🛰️代码仓库：🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！！ 关注我，关注我，关注我 ， 你们将会看到更多的优质内容！！   栈两种线性表示都能实现

    2024年02月03日
    浏览(36)
  • 【数据结构】回溯算法公式化解题 leetcode经典题目带刷：全排列、组合、子集

    【数据结构】回溯算法公式化解题 leetcode经典题目带刷：全排列、组合、子集

    一、什么是回溯算法 回溯算法（Backtracking Algorithm）是一种解决 组合问题 、 排列问题 、 选择问题 等一类问题的常用算法。它通过尝试所有可能的选择来找到问题的解，当发现当前选择不符合要求时，就回溯到之前的状态，然后尝试其他的选择。 1、基本思想： 从问题的起

    2024年02月11日
    浏览(39)
  • 经典TopK问题、优先级队列 与 堆的纠葛一文为你解惑——数据结构

    经典TopK问题、优先级队列 与 堆的纠葛一文为你解惑——数据结构

    前言： 本篇文章以 TopK 问题为引，具体阐述了 PriorityQueue 实现的基本逻辑——堆 数据结构，以及PriorityQueue 的常用方法。如有问题欢迎看官朋友指正，如果觉得文章还不错的话，求点赞、收藏、评论 三连。 重点： 堆的基本实现逻辑 PriorityQueue 运用和源码分析 TopK 问题的解法

    2023年04月22日
    浏览(39)
  • 【数据结构】队列的实现

    【数据结构】队列的实现

    队列是一种常用的数据结构，也是一种操作受限制的线性表，特点是只允许在表的头部进行删除操作，在表的尾部进行插入操作，队列具有先进先出FIFO(First In First Out)。 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头 我们实现可以用数组和链表

    2024年02月02日
    浏览(32)
  • 【数据结构—队列的实现】

    【数据结构—队列的实现】

    提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 文章目录 前言 一、队列 1.1队列的概念及结构 二、队列的实现 2.1头文件的实现—Queue.h 2.2源文件的实现—Queue.c 2.3源文件的测试—test.c 三、测试队列实际数据的展示 3.1正常队列的出入 3.2入队列的同时存

    2024年02月04日
    浏览(36)
  • 数据结构—队列的实现

    数据结构—队列的实现

    前言：上次我们已经学习了数据结构中一个重要的线性表—栈，那么我们这一次就来学习另外一个重要的线性表—队列。 一、 队列的概念 二、 队列的实现： 1.队列的创建 三、 队列的操作 1.初始化队列 2.队尾入队列 3.队头出队列 4.获取队列头部元素 5.获取队列队尾元素 6.获

    2024年02月04日
    浏览(33)
  • 【数据结构】：队列的实现

    【数据结构】：队列的实现

    队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头 队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如

    2024年02月07日
    浏览(32)
  • 【数据结构】队列及其实现

    【数据结构】队列及其实现

    目录 😎前言 认识队列 队列的初始化 队列判空 数据队尾入队 数据队头出队 取队头数据 取队尾数据 队列数据的个数 队列销毁 总结 上次我们学习了栈及其实现，当然也少不它的好兄弟队列啦，今天我们开始队列的学习 队列的性质是 先进先出 ，就比如车辆进出隧道一般，它

    2024年02月09日
    浏览(41)
  • 数据结构---队列的实现

    数据结构---队列的实现

    前言 一、什么是队列？ 二、 队列接口的实现 1. 队列结构的定义 2. 接口实现 总结 队列是一种特殊的线性表。 特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。 进行插入操作的端称为

    2024年02月02日
    浏览(30)
  • 数据结构 | 队列的实现

    数据结构 | 队列的实现

    队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头 队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如

    2024年02月05日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包