创建一个自定义的数据结构来计算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)中运行
【创建一个自定义的数据结构来计算O(1)中的函数】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。