数据结构-用栈实现队列

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

前言:

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

实现 MyQueue 类:

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false

说明:

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。

数据结构-用栈实现队列


目录

1.栈得实现

1.1结构体定义

1.2初始化栈

1.3压栈函数

1.4出栈函数

1.5返回栈顶函数

1.6判空函数 

 1.7销毁函数

 2.题目解析

3.软件程序 

 3.1结构体定义及初始化

3.2进队函数 

 3.3出队函数

 3.3返回队头元素

3.4判空函数 

 3.5销毁函数


 

1.栈得实现

这个题我是使用C语言解法进行解题得,因为要使用栈实现队列,所以首先我们要有栈得源函数,我在这里就把之前写过得栈得源函数按功能分类拷贝下来:代码如下:

1.1结构体定义

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;//数组栈 
	int top;//栈顶
	int capacity;//容量
}ST;

1.2初始化栈

 

void StackInit(ST* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = 0; // ps->top = -1;
	ps->capacity = 0;
}

1.3压栈函数

 

void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newCapacity);
		

		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}

		ps->a[ps->top] = x;
	ps->top++;
}

1.4出栈函数

 

void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
}

 

 

1.5返回栈顶函数

 

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top - 1];
}

1.6判空函数 

 

bool StackEmpty(ST* ps)
{
	assert(ps);

	/*if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return ps->top == 0;
}

 1.7销毁函数

bool StackEmpty(ST* ps)
{
	assert(ps);

	/*if (ps->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/
	return ps->top == 0;
}

 2.题目解析

 我们知道队列是先进先出得,数据得进出如下图所示:

数据结构-用栈实现队列 

而栈得数据是先进后出, 如果上面数据进入栈内,先出的肯定就是数据6,不符合队列要求的数字1先出,所以我们要使用两个栈,一个栈pushST用来将所有数据存储进去,另一个栈popST用来出数据,这样就会把栈底得数据,在出数据得得栈中第一个出去,就满足队列得先进先出得原则。图解图下:

数据结构-用栈实现队列

我们如果这时候想入数据,应该往pushST这个栈里面入,出数据就看popST栈中有无数据,没有数据就往里添pushST中得数据,如果有直接出,如下图所示:

数据结构-用栈实现队列

数据结构-用栈实现队列 

3.软件程序 

 3.1结构体定义及初始化

typedef struct {
ST  pushST;  //定义一个专门存数据得栈
ST  popST;//定义一个专门出数据得栈

} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue *q = (MyQueue*)malloc(sizeof(MyQueue)); //定义一个结构体指针变量 指向两个栈
    StackInit(&q->pushST);//初始化
    StackInit(&q->popST);

    return q;

}

3.2进队函数 

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST,x);  // 开始存数据

}

 3.3出队函数

要先判断栈里面是否为空,为空要先进数据。题目要求 要返回出队得元素,所以我们要定义个变量用来存储出队得数据,代码如下:

int myQueuePop(MyQueue* obj) {
    //如果出栈得数据为空得话,要将存数据得栈内数据放进出栈
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
   int front =  StackTop(&obj->popST);
   StackPop(&obj->popST);
   return front;
}

 3.3返回队头元素

返回的队头元素即为,出栈得栈定元素,代码如下:

int myQueuePeek(MyQueue* obj) {
        if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    //返回栈定数据
   return StackTop(&obj->popST);
}

3.4判空函数 

如果pushST栈 以及popST栈都为空得话 则队列为空,直接用表达式真假判断即可,代码如下:

bool myQueueEmpty(MyQueue* obj) {

    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);

}

 3.5销毁函数

 我们需要先销毁两个栈,再销毁 自定义结构体指针变量得指向,图解如下:

数据结构-用栈实现队列

代码如下: 

 

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    free(obj);

}

 文章来源地址https://www.toymoban.com/news/detail-405357.html

到了这里,关于数据结构-用栈实现队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

领支付宝红包 赞助服务器费用

相关文章

  • 《数据结构初阶》用队列实现栈&&用栈实现队列的细致解析

    目录 一、⏱️本章重点 二、⏱️队列实现栈 三、⏱️栈实现队列 四、⏱️解题思路总结 用两个队列实现栈 用两个栈实现队列 解题思路总结  我们有两个队列:  入栈数据1、 2、 3 可以将数据入队列至队列一或者队列二。 如何出栈?  但出栈要先出1,怎么办? 第一步 :

    2023年04月25日
    浏览(35)
  • 【算法与数据结构】232、LeetCode用栈实现队列

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :这道题要求我们用栈模拟队列(工作上一定没人这么搞)。程序当中,push函数很好解决,直接将元素push进输入栈当中。pop函数需要实现队列先进先出的操作,而栈是先进后出。只

    2024年02月12日
    浏览(42)
  • 【数据结构】队列篇| 超清晰图解和详解:循环队列模拟、用栈实现队列、用队列实现栈

    博主简介: 努力学习的22级计算机科学与技术本科生一枚🌸 博主主页: @是瑶瑶子啦 每日一言🌼: 每一个不曾起舞的日子,都是对生命的辜负。——尼采 🔗622. 设计循环队列 👧🏻 思路: 🍊数据结构: 使用数组为数据结构,且采用牺牲一个空间的方法来包装判空和判满的

    2024年02月11日
    浏览(38)
  • 数据结构刷题训练:用栈实现队列(力扣OJ)

    目录 前言 1. 题目:用栈实现队列 2. 思路 3. 分析  3.1 定义 “ 队列 ”  3.2 创建队列 3.3 入队  3.4 队头数据  3.5 出队  3.6 判空和销毁 4.题解 总结         栈和队列是数据结构中的两个重要概念,它们在算法和程序设计中都有着广泛的应用。本文将带你深入了解如何使用

    2024年02月13日
    浏览(37)
  • 速学数据结构 | 我不允许还有人不会用栈实现队列!

    🎬 鸽芷咕 :个人主页  🔥个人专栏 :《Linux深造日志》《C++干货基地》 ⛺️生活的理想,就是为了理想的生活!    🌈 hello! 各位铁铁们大家好啊,不知道大家对栈和队列的学习都学过了吧?那么用栈来实现队列你会做嘛?    ⛳️ 栈和队列我们前面说了都是一种特殊

    2024年02月02日
    浏览(40)
  • 【数据结构】用栈实现括号匹配

    1.创立一个判断括号是否匹配的函数BracketsCheck 2.传参(栈,输入的字符串) 3.对字符串中的(、[、{、这三种括号进行匹配 4.顺序从左往右进行,依次将符合条件的括号放入栈中,满足FILO原则 5.但拿到右括号时进行匹配,如果匹配成功,那么就出栈,如果失败就返回false 定义

    2024年02月06日
    浏览(40)
  • C语言数据结构篇——用栈实现四则运算

    作者名:Demo不是emo  主页面链接: 主页传送门 创作初心: 舞台再大,你不上台,永远是观众,没人会关心你努不努力,摔的痛不痛,他们只会看你最后站在什么位置,然后羡慕或鄙夷 座右铭: 不要让时代的悲哀成为你的悲哀 专研方向: 网络安全,数据结构 每日emo: 我爱

    2024年02月09日
    浏览(52)
  • 【数据结构-进制转换】用栈实现10进制数转任意进制数

    用栈实现10进制数转任意进制数代码实现 主要思想 :一个十进制数转成相应进制,是通过自身除于对应进制得余数,直到商为0.将所有余数逆序(即最先得到的余数放最后面)排列,得到的结果为所得相应进制数。这一特性与栈极其类似,栈也是 先进后出 原则,故用栈更为

    2023年04月08日
    浏览(41)
  • 用栈的思想实现将一个十进制数字转换为八进制--数据结构

    魔王的介绍:😶‍🌫️一名双非本科大一小白。 魔王的目标:🤯努力赶上周围卷王的脚步。 魔王的主页:🔥🔥🔥大魔王.🔥🔥🔥 ❤️‍🔥大魔王与你分享:“并不是你喝了一瓶雪花,就有人愿意陪你勇闯天涯。” 学完栈的思想后,我们知道了栈只能从栈顶进出,如果

    2023年04月24日
    浏览(42)
  • 【数据结构】前言概况 - 树

    🚩 纸上得来终觉浅, 绝知此事要躬行。 🌟主页:June-Frost 🚀专栏:数据结构 🔥该文章针对树形结构作出前言,以保证可以对树初步认知。  线性结构是一种相对简单的数据结构,元素之间按照一定的顺序排列,每个元素最多有两个接口:前驱和后继。这种结构相对直观

    2024年02月07日
    浏览(67)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包