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

速学数据结构 | 用队列实现栈你都被难住了？那是你没掌握好技巧

10月前 作者：重开_ 分类：Toy博客 阅读(47) 违法举报

这篇具有很好参考价值的文章主要介绍了速学数据结构 | 用队列实现栈你都被难住了？那是你没掌握好技巧。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。


速学数据结构 | 用队列实现栈你都被难住了？那是你没掌握好技巧,《数据结构&算法》,数据结构,C++,算法,java

🎬 鸽芷咕：个人主页

 🔥个人专栏:《Linux深造日志》《C++干货基地》
⛺️生活的理想，就是为了理想的生活!

📋 前言

  🌈hello！ 各位铁铁们大家好啊，栈和队列我们都学过了那么试试用队列实现栈你会嘛？。
  ⛳️本篇文章就来给大家来篇如何用队列来实现栈的全部解析让你彻底拿捏队列。
  📚本期文章收录在《数据结构&算法》，大家有兴趣可以看看呐！
  ⛺️ 欢迎铁汁们 ✔️ 点赞 👍 收藏 ⭐留言 📝！

一、队列实现栈的具体功能

速学数据结构 | 用队列实现栈你都被难住了？那是你没掌握好技巧,《数据结构&算法》,数据结构,C++,算法,java

二、队列实现栈的具体思路

我们先来总结一下队列的特点 先进先出 ，队列的特点 是 后进先出 ：

  • 具体我们可以看一下下图来快速了解

速学数据结构 | 用队列实现栈你都被难住了？那是你没掌握好技巧,《数据结构&算法》,数据结构,C++,算法,java

  • 队列的特点是先进先出
  • 我们要实现栈的功能是后进先出

2.1 实现栈区的具体方法

我们是不是可以具体这样想，队列既然是先进先出，栈是后进先出，的意识就是我们需要每次获取的栈区数据是队列的最后一个：

  • ⁉️那可以不可以这样呢？
  • 开辟俩个队列空间，每次让其中一个为空
  • 另外一个不为空，这样就可以解决删除的问题了。

速学数据结构 | 用队列实现栈你都被难住了？那是你没掌握好技巧,《数据结构&算法》,数据结构,C++,算法,java

2.1 栈区的插入思路

这思路就很简单如果使用俩个指针来管理队列，那么插入就非常简单了，只需要考虑俩种情况：

  • 第一种当然是俩个栈区都为空的情况，还没开始插数据
  • 第二种就是已经插入数据了，那么插入的时候直接往不为空的栈区插入就好了。

2.1 栈区的删除思路

大家看如何我们使用俩个指针来管理队列，来实现栈的话那么来删除就非常简单了为什么这样说呢？

  • 既然一个队列永远为空，一个不为空
  • 那么删除的时候直接把不为空的队列插入到为空的队列
  • 留下最后一个元素用来删除就好了

速学数据结构 | 用队列实现栈你都被难住了？那是你没掌握好技巧,《数据结构&算法》,数据结构,C++,算法,java

三、队列实现栈（具体代码）

好了以上就是队列实现栈的核心思想了，只要核心思想掌握了，那么其他就是小菜了。下面我们就来快速实现一下吧：

3.1 队列的准备

这里是队列的实现代码，由于C语言库里面并没有队列这个数据结构我们就只能手动实现了：

  • 如果有想了解队列的可以看这篇文章：
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QueDataType;

typedef struct QueueType {
	QueDataType data;
	struct QueueType* next;
}QueueNode;

typedef struct Queue {
	struct QueueType* head;
	struct QueueType* tail;
	int size;
}Que;

//初始化队列
void QueueInit(Que* ps);
//销毁队列
void QueueDestroy(Que* ps);
//插入数据
void QueuePush(Que* ps, QueDataType x);
//删除数据
void QueuePop(Que* ps);
//获取头数据
QueDataType QueueFront(Que* ps);
//获取尾数据
QueDataType QueueBack(Que* ps);
//获取队列长度
int QueueSize(Que* ps);
//判断是否为空
bool QueueEmpty(Que* ps);


//初始化队列
void QueueInit(Que* ps)
{
	assert(ps);

	ps->head = NULL;
	ps->tail = NULL;
	ps->size = 0;
}

//销毁队列
void QueueDestroy(Que* ps)
{
	assert(ps);
	QueueNode* cur = ps->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}

	ps->head = ps->tail = NULL;
	ps->size = 0;
}

//插入数据
void QueuePush(Que* ps, QueDataType x)
{
	assert(ps);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;

	if (ps->head == NULL)
	{
		ps->head = ps->tail = newnode;
	}
	else
	{
		ps->tail->next = newnode;
		ps->tail = newnode;
	}

	ps->size++;
}


//删除数据
void QueuePop(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}

	pq->size--;
}

//获取头数据
QueDataType QueueFront(Que* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->head->data;
}

//获取尾数据
QueDataType QueueBack(Que* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));


	return ps->tail->data;
}

//获取队列长度
int QueueSize(Que* ps)
{
	assert(ps);
	
	return ps->size;
}

//判断是否为空
bool QueueEmpty(Que* ps)
{
	assert(ps);

	return ps->head == NULL;
}

3.2 栈区的初始化

好了思路我们理清楚了接下来就是看看具体队列实现栈的代码到底如何实现：

  • 前面我们说过了使用俩个指针来管理队列就好了
  • 然后进行 malloc 申请空间就好了

📚 代码演示：

typedef struct {
    Que q1;
    Que q2;

} MyStack;


MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);

    return obj;
}

3.3 栈区的插入

插入的话我们思想已经都知道，下面就是考验你的代码能力了：

  • 如果俩个队列为空随便插入一个就好了
  • 否则就插入另一个队列

📚 代码演示：

void myStackPush(MyStack* obj, int x) {
    assert(obj);

    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }

}

3.4 栈区的删除

删除的思想很简单，每次搬运一下队列就好了：

  • 这里使用了一个非常实用的判定方法大家可以去看看
  • 先假设一个为空一个不为空
  • 然后如果错了就换过来

📚 代码演示：

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

    Que* empty = &obj->q1;
    Que* noempty = &obj->q2;
    if(!QueueEmpty(empty))
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }

    while(QueueSize(noempty) > 1)
    {
        QueuePush(empty, QueueFront(noempty));
        QueuePop(noempty);
    }

    int top = QueueFront(noempty);
    QueuePop(noempty);
    
    return top;
}

3.5 栈区的判空

这个就简单了只要栈中管理俩个队列的的都为空那当然都没有数据了：

  • QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2)

📚 代码演示：

bool myStackEmpty(MyStack* obj) {

    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

3.6 获取栈区的头元素

既然我们使用了俩个队列来实现栈，并且只有一个队列存放数据。

  • 那么只需要看哪个队列不为取出队尾数据就好了。

📚 代码演示：

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

3.7 栈区的销毁

老样子了，先把栈区里面的 malloc 里面的空间释放了，然后再释放栈就好了。

📚 代码演示：

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

    free(obj);

}

三、全部实现代码

📚 代码演示：

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QueDataType;

typedef struct QueueType {
	QueDataType data;
	struct QueueType* next;
}QueueNode;

typedef struct Queue {
	struct QueueType* head;
	struct QueueType* tail;
	int size;
}Que;

//初始化队列
void QueueInit(Que* ps);
//销毁队列
void QueueDestroy(Que* ps);
//插入数据
void QueuePush(Que* ps, QueDataType x);
//删除数据
void QueuePop(Que* ps);
//获取头数据
QueDataType QueueFront(Que* ps);
//获取尾数据
QueDataType QueueBack(Que* ps);
//获取队列长度
int QueueSize(Que* ps);
//判断是否为空
bool QueueEmpty(Que* ps);


//初始化队列
void QueueInit(Que* ps)
{
	assert(ps);

	ps->head = NULL;
	ps->tail = NULL;
	ps->size = 0;
}

//销毁队列
void QueueDestroy(Que* ps)
{
	assert(ps);
	QueueNode* cur = ps->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}

	ps->head = ps->tail = NULL;
	ps->size = 0;
}

//插入数据
void QueuePush(Que* ps, QueDataType x)
{
	assert(ps);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;

	if (ps->head == NULL)
	{
		ps->head = ps->tail = newnode;
	}
	else
	{
		ps->tail->next = newnode;
		ps->tail = newnode;
	}

	ps->size++;
}


//删除数据
void QueuePop(Que* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}

	pq->size--;
}

//获取头数据
QueDataType QueueFront(Que* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));

	return ps->head->data;
}

//获取尾数据
QueDataType QueueBack(Que* ps)
{
	assert(ps);
	assert(!QueueEmpty(ps));


	return ps->tail->data;
}

//获取队列长度
int QueueSize(Que* ps)
{
	assert(ps);
	
	return ps->size;
}

//判断是否为空
bool QueueEmpty(Que* ps)
{
	assert(ps);

	return ps->head == NULL;
}

typedef struct {
    Que q1;
    Que q2;

} MyStack;


MyStack* myStackCreate() {
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);

    return obj;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);

    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);
    }

}

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

    Que* empty = &obj->q1;
    Que* noempty = &obj->q2;
    if(!QueueEmpty(empty))
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }

    while(QueueSize(noempty) > 1)
    {
        QueuePush(empty, QueueFront(noempty));
        QueuePop(noempty);
    }

    int top = QueueFront(noempty);
    QueuePop(noempty);

    return top;
}

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

bool myStackEmpty(MyStack* obj) {

    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

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

    free(obj);

}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

📝全篇总结

☁️ 好了以上就是队列实现栈的全部细节与过程来，大家不要忘记练习哦！
看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！
💛 💙 💜 ❤️ 💚💓 💗 💕 💞 💘 💖
拜托拜托这个真的很重要！
你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。
速学数据结构 | 用队列实现栈你都被难住了？那是你没掌握好技巧,《数据结构&amp;算法》,数据结构,C++,算法,java文章来源地址https://www.toymoban.com/news/detail-744946.html

到了这里，关于速学数据结构 | 用队列实现栈你都被难住了？那是你没掌握好技巧的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

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

相关文章

  • 数据结构 | 队列的实现

    数据结构 | 队列的实现

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

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

    数据结构—队列的实现

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

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

    数据结构——队列的实现

    队列 ，又称为伫列（queue），计算机科学中的一种抽象资料类型，是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。 这段代码使用 typedef 定义了一个

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

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

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

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

    【数据结构】队列的实现

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

    2024年02月02日
    浏览(39)
  • 数据结构/队列实现栈

    数据结构/队列实现栈

    在学习数据结构的过程当中，我们会学到栈和队列，在本篇文章中，重点讲解的是队列实现栈，在上篇文章中已经简单介绍过栈和队列的使用说明，以及栈实现队列。(2条消息) 数据结构/栈实现队列_Y君的进化史的博客-CSDN博客 关于一个队列的简单使用方式：    关于一个栈的

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

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

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

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

    数据结构队列的实现

    本章介绍数据结构队列的内容，我们会从队列的定义以及使用和OJ题来了解队列，话不多说，我们来实现吧 队列 1。队列的概念及结构 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入

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

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

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

    2024年02月04日
    浏览(40)
  • 【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列

    【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列

    🌠 作者：@ 阿亮joy. 🎆 专栏：《数据结构与算法要啸着学》 🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根 请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、

    2024年01月20日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包