Constant Time Stack
/*** How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time. ***/ #include <iostream> #include <climits> using namespace std; struct node { int val; node *next; }; class myStack { public: myStack(); ~myStack(); void push(int); int pop(); int getmin(); private: int min; node *stack; node *minStack; node *top; node *mintop; void update_top(node*); void delete_node(node*); }; myStack::myStack() { top = nullptr; mintop = nullptr; min = INT_MAX; } myStack::~myStack() { while (stack != nullptr) { delete_node(stack); } } void myStack::push(int val) { if (val <= min) { min = val; // push in stack stack = new node(); stack->next = top; stack->val = val; top = stack; minStack = new node(); minStack->next = mintop; minStack->val = val; mintop = minStack; } else { // only push val in stack stack = ...