[链表OJ题 8] 用栈实现队列,没想到你小子的基础这么好,这么快就做对了

这篇具有很好参考价值的文章主要介绍了[链表OJ题 8] 用栈实现队列,没想到你小子的基础这么好,这么快就做对了。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

题目来源:

代码实现:

思路分析:

实现过程:


题目来源:

力扣 - 232.用栈实现队列

题目描述:

[链表OJ题 8] 用栈实现队列,没想到你小子的基础这么好,这么快就做对了

代码实现:

我们这里的栈已经写好了,如果对栈还不是很懂的可以看看这篇文章:CSDN - [数据结构 -- C语言] 栈(stack)

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);

	ps->a = NULL;
	//ps->top = -1;//top 指栈顶数据
	ps->top = 0;//top 指栈顶数据的下一个位置
	ps->capacity = 0;
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);

	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail:");
			return;
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}

	ps->a[ps->top] = data;
	ps->top++;
}
// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top-1];
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);

	if (0 == ps->top)
		return 1;
	else
		return 0;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

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

MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->push);
    StackInit(&obj->pop);

    return obj;
}

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

int myQueuePop(MyQueue* obj) {
    int front = myQueuePeek(obj);
    StackPop(&obj->pop);
    return front;
}

int myQueuePeek(MyQueue* 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);
}

思路分析:

我们知道队列的特性:先入先出;栈的特性:先入后出。因此我们定义两个栈,一个是入元素的栈(push栈),另一个是出元素的栈(pop栈)。当我们要入队的时候就把元素直接入到 push栈中,出队的时候先把 push栈 中的元素全部放入 pop栈 中,将 pop栈 的栈顶元素出栈就能实现队列的特性。

此题的本质是以栈的特性来实现队列的特性。

[链表OJ题 8] 用栈实现队列,没想到你小子的基础这么好,这么快就做对了

实现过程:

1、我们先将栈的所有接口都写出来。然后我们创建两个栈,一个是实现入队功能的栈(push栈),另一个是实现出队功能的栈(pop栈);

2、我们要实现入队的时候,将元素入到 push栈 中,要出队的时候先将 push栈 中的元素转到 pop栈 中,然后出pop栈 这样就可以实现出队时出的是队头元素;

3、在出队的时候我们先看 pop栈 中还有没有元素,要是有元素我们直接出 pop栈 中的栈顶元素就可以,如果没有就先将 push栈 中的元素转到 pop栈 中;入队的时候直接入到 push栈 中就可以。

对栈还不太明白的朋友可以参考代码实现那部分的 的那篇文章。

[链表OJ题 8] 用栈实现队列,没想到你小子的基础这么好,这么快就做对了

*** 本篇结束 ***文章来源地址https://www.toymoban.com/news/detail-463136.html

到了这里,关于[链表OJ题 8] 用栈实现队列,没想到你小子的基础这么好,这么快就做对了的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 万万没想到,我用文心一言开发了一个儿童小玩具

    最近关注到一年一度的 百度世界大会 今年将于10月17日在北京首钢园举办,本期大会的主题是“ 生成未来(PROMPT THE WORLD) ”。会上,李彦宏会做主题为「 手把手教你做AI原生应用 」的演讲,比较期待 Robin 会怎么展示。据说,大会当天百度还会发布文心4.0版本,估计要炸一

    2024年02月08日
    浏览(43)
  • 真没想到啊!无需服务器,五分钟部署公众号机器人

    大家好,我是编程哥。一个寻求破圈,不断淬炼自己的人,关注我一起进步。 目前各大模型都比较火,作为一名程序员,对大模型的了解也是蠢蠢欲动,尤其是对于机器人自动问答这一项。所以在朋友的推荐下,了解了一个无需服务器,快速搭建公众号机器人的教程,现在分

    2024年02月03日
    浏览(39)
  • 作为所有类的顶层父类,没想到Object的魔力如此之大!

    在上一篇博文中我们提到了Java面向对象的四大特性,其中谈及“抽象”特性时做了一个引子,引出今天的主人公Object,作为所有类的顶级父类,Object被视为是James.Gosling的哲学思考,它高度概括了事务的自然与社会行为。 跟进Object类的源码中我们可以看到,类的注释中对它做

    2024年02月01日
    浏览(42)
  • 没想到,JDBC 驱动会偷偷修改 sql_mode 的会话值

    最近碰到一个 case,值得分享一下。 现象就是一个 update 操作,在 mysql 客户端中执行提示 warning,但在 java 程序中执行却又报错。 update 语句中使用 STR_TO_DATE 函数将字符串转换为日期时间格式。 但因为这个格式字符串 \\\'%Y-%m-%d %H:%i:%s\\\' 没有对日期字符串中的毫秒部分 .0 进行解析

    2024年03月09日
    浏览(44)
  • 5年测试经验怎么着我也能要个20K吧?没想到被阿里P8问傻了····

    都说金三银四是跳槽涨薪季,我也是着急忙慌的准备简历—— 5年软件测试经验,可独立测试大型产品项目,熟悉项目测试流程…薪资要求?5年测试经验起码能要个20K吧? 我加班肝了一页半简历,投出去一周,面试电话倒是不少,自信满满去面试,现场被问了这么几个问题—

    2024年02月08日
    浏览(44)
  • 云安全_什么是云,云计算的本质,没想到一个Handler还有中高级几种问法

    是将计算机终端系统进行虚拟化,以达到桌面使用的安全性和灵活性。可以通过任何设备,在任何地点,任何时间通过网络访问属于我们个人的桌面系统。 存储虚拟化 是对存储硬件资源进行抽象化表现。 网络虚拟化 网络虚拟化就是在一个物理网络上模拟出多个逻辑网络来。

    2024年04月13日
    浏览(44)
  • 5年测试经验怎么着我也能要个20K吧?没想到被阿里P8问傻了

    都说金三银四是跳槽涨薪季,我也是着急忙慌的准备简历—— 5年软件测试经验,可独立测试大型产品项目,熟悉项目测试流程…薪资要求?5年测试经验起码能要个20K吧? 我加班肝了一页半简历,投出去一周,面试电话倒是不少,自信满满去面试,现场被问了这么几个问题—

    2024年02月08日
    浏览(47)
  • 栈和队列OJ题:LeetCode--232.用栈实现队列

    朋友们、伙计们,我们又见面了,今天给大家带来的是LeetCode--232.用栈实现队列 数 据 结 构 专 栏:数据结构 个    人   主    页 :stackY、 LeetCode 专  栏 :LeetCode刷题训练营 LeetCode--232.用栈实现队列:https://leetcode.cn/problems/implement-queue-using-stacks/ 目录 1.题目介绍 2.实例演示

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

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

    2024年02月13日
    浏览(39)
  • 用队列实现栈和用栈实现队列

    前面我们实现了栈和队列,其实栈和队列之间是可以相互实现的 下面我们来看一下 用 队列实现栈 和 用栈实现队列 使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty) 实现 MyStack 类: void push(int x) 将元素 x 压入栈顶。 int pop

    2023年04月09日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包