文档章节

设计包含min函数的栈

Zhang_H
 Zhang_H
发布于 2014/04/09 22:45
字数 740
阅读 18
收藏 0

定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。

分析:

在栈里添加一个成员变量存放最小元素(或最小元素的位置)。每次push一个新元素进栈的时候,如果该元素比当前的最小元素还要小,则更新最小元素。 
乍一看这样思路挺好的。但仔细一想,该思路存在一个重要的问题:如果当前最小元素被pop出去,如何才能得到下一个最小元素? 
因此仅仅只添加一个成员变量存放最小元素(或最小元素的位置)是不够的。我们需要一个辅助栈。每次push一个新元素的时候,同时将最小元素(或最小元素的位置。考虑到栈元素的类型可能是复杂的数据结构,用最小元素的位置将能减少空间消耗)push到辅助栈中;每次pop一个元素出栈的时候,同时pop辅助栈。 


简而概之——以空间换时间。


好久没认真写过C程序了,指针写的各种不熟练。

代码如下(GCC编译,运行通过);

#include "stdio.h"
#include "stdlib.h"
#define MAX_SIZE 10

typedef struct
{
	int top;//栈顶指针
	int maxsize;//栈的最大容量
	int *stack;//数组,存放栈内元素
	int *min_index;//存放当前最小值下标
}ElemST;


void InitStack(ElemST *s,int ms);
void Push(ElemST *s,int val);
int Pop(ElemST *s);
int GetMinVal(ElemST *s);

int main(void)
{

	ElemST s;	
	int i,tmp;
	
	InitStack(&s,10);

	srand((unsigned)time(NULL));//随机数种子

	for(i = 0;i<MAX_SIZE;++i)//产生随机数,压栈
	{
		tmp = rand()%101;
		Push(&s,tmp);
		if(rand()%2)//随机判断是否出栈
			Pop(&s);
	}

	printf("Min Val is %d\n",GetMinVal(&s));

	return 0;
}

void InitStack(ElemST *s,int ms)
{
	s->maxsize = ms;
	s->top = -1;
	s->stack = (int *)malloc(s->maxsize * sizeof(int));
	s->min_index = (int *)malloc(s->maxsize * sizeof(int));
}

void Push(ElemST *s,int val)
{
	if(s->top +1 == s->maxsize)
	{
		printf("stack full,close...");
		exit(0);
	} 

	s->stack[++s->top] = val;//压栈
	if(s->top-1  == -1)//修改当前最小值下标
	{
		s->min_index[s->top] = 0;
	}
	else	if(val > s->stack[s->min_index[s->top -1]])
	{
		s->min_index[s->top] = s->min_index[s->top -1];
	}
	    	else
		{
			s->min_index[s->top] = s->top;
		}

	printf("%d已入...\n",val);
}

int Pop(ElemST *s)
{
	s->top--;
	printf("%3d已出...\n",s->stack[s->top+1]);
	return s->stack[s->top+1];
}

int GetMinVal(ElemST *s)
{
	return  s->stack[s->min_index[s->top]];
}


举个例子演示上述代码的运行过程: 

   步骤               数据栈             辅助栈 (存小元素的位置)              最小值 
1.push 3              3                     0                                                   3 
2.push 4             3,4                  0,0                                                  3 
3.push 2            3,4,2               0,0,2                                                2 
4.push 1            3,4,2,1            0,0,2,3                                              1 
5.pop                3,4,2               0,0,2                                                 2 
6.pop               3,4                   0,0                                                    3 

7.push 0           3,4,0                0,0,2                                                 0 


参考资料:

《微软面试100题系列》

来自互联网其他资料


© 著作权归作者所有

Zhang_H
粉丝 6
博文 39
码字总数 21186
作品 0
西安
私信 提问
面试题_设计包含 min函数的栈

设计包含 min函数的栈() 定义栈的数据结构,要求添加一个 minminmin函数,能够得到栈的最小元素。 要求函数 min、push以及 pop 的时间复杂度都是 O(1)。 #include <iostream>using namespa...

梦想游戏人
2015/07/01
24
0
Java面试题:栈和队列的实现

面试的时候,栈和队列经常会成对出现来考察。本文包含栈和队列的如下考试内容: (1)栈的创建 (2)队列的创建 (3)两个栈实现一个队列 (4)两个队列实现一个栈 (5)设计含最小函数min()...

umgsai
2016/09/10
0
0
栈和队列的面试题Java实现【重要】

栈和队列: 面试的时候,栈和队列经常会成对出现来考察。本文包含栈和队列的如下考试内容:   (1)栈的创建   (2)队列的创建   (3)两个栈实现一个队列   (4)两个队列实现一个...

商者
2016/04/10
84
0
栈和队列的面试题Java实现

栈和队列: 面试的时候,栈和队列经常会成对出现来考察。本文包含栈和队列的如下考试内容: (1)栈的创建 (2)队列的创建 (3)两个栈实现一个队列 (4)两个队列实现一个栈 (5)设计含最...

天蚕宝衣
2016/03/31
27
0
算法3-设计包含min函数的栈

题目:定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。 要求函数min、push以及pop的时间复杂度都是O(1)。 思路:使用一个辅助栈来保存最小元素,这个解法简单不失优雅。设该...

kuanshang
2014/03/06
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
323
5
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
11
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
6
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部