2.设计包含min函数的栈。
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
分析:既然要求“求最小”时间复杂度为O(1),所以一定要在top指针结构内记录最小量。就是在push 时将最小值
#include "stdio.h"
#include"malloc.h"
#define STACK_LEN 50
/*
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。
要求函数min、push以及pop的时间复杂度都是O(1)。
*/
typedef struct
{
int val; // 存储值
int min;
} stack_item;
typedef struct
{
stack_item data[STACK_LEN]; //使用另一个数据结构
int top;
} stack;
void push(stack *stk, int val)//放入
{
//printf("%d",stk->top);
stk->data[++stk->top].val = val;
//printf("sssssss");
if (stk->top > 0)
{
if (val < stk->data[stk->top - 1].min)//如果当前push进的元素小于栈中最小元素
stk->data[stk->top].min = val; //把当前元素置为栈中最小元素
else //否则,不更新
stk->data[stk->top].min = stk->data[stk->top - 1].min; //新插入值后的 最小值与 插入之前最小值相同
}
else //栈 初始化 为空的情况
stk->data[stk->top].min = val;
}
int pop(stack *stk)
{
return stk->data[stk->top--].val;
}
int min(stack *stk)
{
return stk->data[stk->top].min;
}
int main()
{
int i;
int a[9]={10,7,3,3,8,5,2,6};
stack *stk;
stk=(stack*)malloc(sizeof(stack));//这里一定要
stk->top=-1;//这里需要添加
for(i=0;i<8;++i)
push(stk, a[i]);
printf("%d",min(stk));
return 0;
}
分享到:
相关推荐
网络工程师考前冲刺100题
01第-章第二章p1-p29.rar 网盘文件永久链接 02第三章第四章D30-p59.ram 03第五章第五章P60-P85.rar 04第六章第章第八章P85-P8113.ram 05第九章第十章p114-P137.rar 06第十章第章P138-P165.rar 07第十■章第十■章...
5.[第二部分]精选微软等公司结构+算法面试100题[前41-60题]: http://download.csdn.net/source/2811703 6.[第一部分]精选微软等公司数据结构+算法经典面试100题[1-40题] http://download.csdn.net/source/2778852 ...
《网络工程师考前冲刺100题》内容简介:一直以来,计算机技术与软件专业技术资格(水平)考试(以下简称“软考”)是国内难度最高的计算机专业资格考试之一,其平均通过率在10%左右。自网络工程师开考以来,其通过率...
01 第一章 第二章P1-P29 02 第三章 第四章P30-P59 03 第五章 第五章P60-P85 04 第六章 第七章第八章P85-P8113 05 第九章 第十章P114-P137 06 第十一章 第十二章P138-P165 07 第十二章 第十二章P165-P185 08 第十三章...
[第二部分]精选微软等公司结构+算法面试100题[前41-60题]: http://download.csdn.net/source/28117034 [第1题-60题汇总]微软等数据结构+算法面试100题 http://download.csdn.net/source/2826690答案系列: 5.[最新...
2019互联网面试题第2季
第2题【答案】 第1处:static void 第2处:(year%4==0&&year%100!=0)||year%400==0 第3处:else 第3题【答案】 第1处:String[]args(或 String args[])(注:args为变量名,可为其他名称) 第2处:switch 第3处:r...
Python基础题库100题及答案 Python基础题库100题及答案全文共16页,当前为第1页。Python基础题库100题及答案全文共16页,当前为第1页。 Python基础题库100题及答案全文共16页,当前为第1页。 Python基础题库100题及...
本微软面试100题系列,共计11篇文章,300多道面试题,截取本blog索引性文章:程序员面试、算法研究、编程艺术、红黑树、数据挖掘5大系列集锦:http://blog.csdn.net/v_july_v/article/details/6543438,中的第一部分...
猿人学第二届第一题解题小记
2020 CSP-S 第1轮 初赛 第 17 题 二、阅读程序题 第2题.pdf
2.[答案V0.2 版]精选微软数据结构+算法面试100 题[前20 题]--修正 http://download.csdn.net/source/2813890 //此份答案是针对最初的V0.1 版本,进行的校正与修正。 3.[答案V0.1 版]精选微软数据结构+算法面试100 题...
微软等数据结构+算法面试100题最后20题第81-100题新鲜出炉 ---100题系列V0.1版完整公布 作者:July 时间:2010年12月5日 ============= 首先,非常感谢各位,对本微软面试100题系列前期工作的大力支持。 很多很多...
2019,尚硅谷,周阳,互联网面试题脑图,第2季,.mmap版
北航 数值分析大作业 第二题 C++ 北航 数值分析大作业 第二题 C++ 北航 数值分析大作业 第二题 C++ 北航 数值分析大作业 第二题 C++
在此之前,由于本人笨拙,这微软面试100题的答案只整理到了前60题(第1-60题答案可到本人资源下 载处下载:http://v_july_v.download.csdn.net/),故此,常有朋友留言或来信询问后面40题的答案。只是 因个人认为:...
尚硅谷2019年互联网大厂高频重点面试题第二季, 内容包括JUC多线程并发、JVM和GC等目前大厂笔试中会考、面试中会问、工作中会用的高频难点知识。从多线程并发入手,分层递进讲解,逐步让大家掌握volatile、原子类和...
看书就是看谭浩强的《C程序设计(第二版)》,最重要的是5、6、7章,要求掌握;其次是2、3、4、8、9章,要求理解;第1章简单看一下就可以了;另外,虽说指针、文件输入输出等不考,但还是建议看一下,至少要知道...
这是模式分类(第二版)第二章课后编程题的答案,其中的代码跟书中题目的要求不完全相同,但是思路都是相同的,这部分代码完全是我自己独立完成的,如果有什么不对的地方请大家提出来,我好及时修改。