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

2021年5月14日15:46:07 发表评论 934 次浏览

GetLastElement();

RemoveLastElement();

GetMin()

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 GetMin();
};

//utility function for adding a new 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;
if (success == 1)
cout <<"5 inserted successfully\n" ;

if (success == 1)
cout <<"7 inserted successfully\n" ;

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" ;

if (success == 1)
cout <<"2 inserted successfully\n" ;

if (success == 1)
cout <<"9 inserted successfully\n" ;
int last = s.GetLastElement();
cout <<"Last element :: " <<last <<endl;

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" ;

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``````