创建一个自定义的数据结构来计算O(1)中的函数

创建一个自定义的数据结构, 使其具有以下功能：

GetLastElement();

RemoveLastElement();

AddElement()

GetMin()

所有函数应为O(1)

问题来源：亚马逊面试问题

方法：

1)创建一个具有两个元素的自定义类型结构堆栈, (元素, min_till_now)

2)在此自定义数据类型上实现功能

//program to demonstrate customized data structure
//which supports functions in O(1)
#include <iostream>
#include <vector>
using namespace std;
const int MAXX = 1000;
  
//class stack
class stack {
     int minn;
     int size;
  
public :
     stack()
     {
         minn = 99999;
         size = -1;
     }
     vector<pair<int , int>> arr;
     int GetLastElement();
     int RemoveLastElement();
     int AddElement( int element);
     int GetMin();
};
  
//utility function for adding a new element
int stack::AddElement( int element)
{
     if (size> MAXX) {
         cout <<"stack overflow, max size reached!\n" ;
         return 0;
     }
     if (element <minn)
         minn = element;
     arr.push_back(make_pair(element, minn));
     size++;
     return 1;
}
  
//utility function for returning last element of stack
int stack::GetLastElement()
{
     if (size == -1) {
         cout <<"No elements in stack\n" ;
         return 0;
     }
     return arr[size].first;
}
  
//utility function for removing last element successfully;
int stack::RemoveLastElement()
{
     if (size == -1) {
         cout <<"stack empty!!!\n" ;
         return 0;
     }
  
     //updating minimum element
     if (size> 0 && arr[size - 1].second> arr[size].second) {
         minn = arr[size - 1].second;
     }
     arr.pop_back();
     size -= 1;
     return 1;
}
  
//utility function for returning min element till now;
int stack::GetMin()
{
     if (size == -1) {
         cout <<"stack empty!!\n" ;
         return 0;
     }
     return arr[size].second;
}
  
//Driver code
int main()
{
     stack s;
     int success = s.AddElement(5);
     if (success == 1)
         cout <<"5 inserted successfully\n" ;
  
     success = s.AddElement(7);
     if (success == 1)
         cout <<"7 inserted successfully\n" ;
  
     success = s.AddElement(3);
     if (success == 1)
         cout <<"3 inserted successfully\n" ;
     int min1 = s.GetMin();
     cout <<"min element  :: " <<min1 <<endl;
  
     success = s.RemoveLastElement();
     if (success == 1)
         cout <<"removed successfully\n" ;
  
     success = s.AddElement(2);
     if (success == 1)
         cout <<"2 inserted successfully\n" ;
  
     success = s.AddElement(9);
     if (success == 1)
         cout <<"9 inserted successfully\n" ;
     int last = s.GetLastElement();
     cout <<"Last element :: " <<last <<endl;
  
     success = s.AddElement(0);
     if (success == 1)
         cout <<"0 inserted successfully\n" ;
     min1 = s.GetMin();
     cout <<"min element  :: " <<min1 <<endl;
  
     success = s.RemoveLastElement();
     if (success == 1)
         cout <<"removed successfully\n" ;
  
     success = s.AddElement(11);
     if (success == 1)
         cout <<"11 inserted successfully\n" ;
     min1 = s.GetMin();
     cout <<"min element  :: " <<min1 <<endl;
  
     return 0;
}

输出如下：

5 inserted successfully
7 inserted successfully
3 inserted successfully
min element  :: 3
removed successfully
2 inserted successfully
9 inserted successfully
Last element :: 9
0 inserted successfully
min element  :: 0
removed successfully
11 inserted successfully
min element  :: 2

时间复杂度：每个函数都在O(1)中运行

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。