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    {}    请设计该容器,定义所需的数据结构,实现以上四个接口(用你熟悉的语言或者伪码),并给出各个方法的计算复杂度和整个容器的空间复杂度。-笔试面试资料

这是qklbishe.com第19689 篇笔试面试资料
提供答案分析,通过本文《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    {}    请设计该容器,定义所需的数据结构,实现以上四个接口(用你熟悉的语言或者伪码),并给出各个方法的计算复杂度和整个容器的空间复杂度。-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

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    {}

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

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    {}       请设计该容器,定义所需的数据结构,实现以上四个接口(用你熟悉的语言或者伪码),并给出各个方法的计算复杂度和整个容器的空间复杂度。 区块链毕设学生150591921号
与leetcode155类似,不过是把最小值改成了最大值。

class maxStack {     stack<int>s,max_stack; public:     maxStack()     {      }     int size()     {         return s.size();     }     void push(int val)     {         s.push(val);         if(max_stack.empty()||val>=max_stack.top())         {             max_stack.push(val);         }     }     int stack_pop()     {         int x=s.top();         s.pop();         if(!max_stack.empty()&&x==max_stack.top())         {             max_stack.pop();         }         return x;     }     int heap_pop()     {         int x=max_stack.top();          max_stack.pop();         stack<int>s1;         while(!s.empty())         {              if(s.top()!=x)             {                 s1.push(s.top());                 s.pop();             }             else             {                 s.pop();                break;             }         }         while(!s1.empty())         {             s.push(s1.top());             s1.pop();         }         return x;     } }; 

不过heap_pop()除了这种方法还没有想到更好的办法

2022-01-01 21:37:26 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 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    {}    请设计该容器,定义所需的数据结构,实现以上四个接口(用你熟悉的语言或者伪码),并给出各个方法的计算复杂度和整个容器的空间复杂度。-笔试面试资料

提供最优质的资源集合

立即查看 了解详情