现在的位置: 首页 > 综合 > 正文

【数据结构】关于堆栈等数据结构的问题

2018年04月12日 ⁄ 综合 ⁄ 共 1426字 ⁄ 字号 评论关闭

1 在栈基础上完成取中位数,最大最小数的操作

 想到了流中位数和这个类似。


来考虑求取堆栈中中间值的方法。受求最大值、最小值方法的启发,设计出求中间值的方法。求中间值得方法需要两个栈,即最大值栈leftMax和最小值栈rightMin,还需要一个存中间值的数据结构,结构如下:

 

Median:存放中间值;leftCount:小于中间值元素的个数;rightCount:大于中间值的元素的个数。可以很容易知道rightCount<=leftCount<=(rightCount+1)。

小于中间值的元素的最大值可用最大值栈来获得,大于中间值的元素的最小值可用最小值栈来获得。假如进栈元素为data。

进栈操作:

1,  如果rightCount等于leftCount,leftCount+=1:(1),data等于median时,简单将data压入leftMax;(2),data大于median时,将median压入leftMax,同时比较data和rightMin中元素的最小值(由于rightMin是最小值栈,这一点可以很容易做到),将该最小值赋予median,同时将剩下的元素选择性的压入rightMin;(3),data小于median时,median值不变,选择性地将data压入leftMax,方法如最大值栈进栈操作的那样。

2,  如果(rightCount+1)等于leftCount,rightCount+=1:(1),data等于median时,简单将data压入rightMax;(2),data小于median时,将median压入rightMin,同时比较data和leftMax中元素的最大值(由于leftMax是最大值栈,这一点可以很容易做到),将该最大值赋予median,同时将剩下的元素选择性的压入leftMax;(3),data大于median时,median值不变,选择性地将data压入rightMin。

出栈操作:

1,  如果rightCount等于leftCount,rightCount-=1:(1),data等于median时,简单将rightMin中最小值弹出赋予median;(2),data大于median时,类似于最小值出栈操作,弹出data;(3),data小于median时,leftMax中弹出data,同时将median压入leftMax,弹出rightMin最小值赋予median。

2,  如果(rightCount+1)等于leftCount,leftCount-=1:(1),data等于median时,简单将leftMax中最大值弹出赋予median;(2),data小于median时,类似于最大值出栈操作,弹出data;(3),data大于median时,rightMin中弹出data,同时将median压入rightMin,弹出leftMax最大值赋予median。

举例如下:

假如要进栈的数据分别是1,3,3,5,1,7,2,4,3,所有数据进栈后总栈和求取中间值附加的最大值栈、最小值栈和中间值中数据排列情况如下:

之后堆栈执行pop操作过后各个数据结构的分布情况如下:

 

综述,采用上述对堆栈的扩展,堆栈的那一组处理函数void push(data);void pop();int getMiddle();int getMax();int getMin();int size();均可在O(1)的时间内完成。

抱歉!评论已关闭.