首页 > 试题广场 >

stack和heap都是常见的数据结构。现在我希望你设计一个

[问答题]

stack和heap都是常见的数据结构。现在我希望你设计一个容器,同时拥有stack和heap的特性,即该容器至少包含这四个接口:

(1) size:容器中元素的个数。

(2) push:向该容器中加入一个元素。

(3) stack_pop:从该容器中取出一个元素,且取出顺序与push顺序相反。

(4) heap_pop:从该容器中取出一个元素,且该元素是容器中值最大的。

一旦某个元素从容器中pop出去(无论是stack_pop还是heap_pop),该元素就不在容器中了,即一个元素只能被pop一次。

下面为样例,第一列是操作,第二列是操作完成后容器中的元素集合:

push(1)           {1}

push(3)           {1,3}

push(2)           {1,3,2}

heap_pop()->3     {1,2}

stack_pop()->2    {1}

stack_pop()->1    {}

请设计该容器,定义所需的数据结构,实现以上四个接口(用你熟悉的语言或者伪码),并给出各个方法的计算复杂度和整个容器的空间复杂度。


这道题你会答吗?花几分钟告诉大家答案吧!