#### Stacks & Queues

Problem
Design and implement an extended stack using linked list which permits push, pop & maxElement (gets maximum element in the stack) in O(1) time complexity.

Solution
We need to maintain an additional element ( max_so_far ) in each node which stores the maximum value pushed into the stack till now. The value of max_so_far on the top node of the stack gives the maximum element in the stack. See the implementation below.

```#include<iostream>
#define MAX 100
#define MIN -999999 // infinitesimal small value
using namespace std;

int max(int a,int b) {
return ((a > b) ? a : b);
}

// structure of a stack node
typedef struct stack_node {
int data;
int max_so_far;// max element so far in the stack
struct stack_node *next;
}node;

// declare a stack data structure which also gives the max
// element apart from push and pop operations in O(1) time
class stack {
private :
node *top;
public :
stack() {
// stack is empty
top = NULL;
}
void push(int element); // push element
void pop(); // pop
int getTopElement(); // returns the top element
int getMaxElement(); // returns max element
void displayStack(); // displays the stack
};

// displays all the elements of a stack
void stack :: displayStack() {
node *ptr = top;
cout<<"\nStack elements (top to bottom)\n";
while (ptr != NULL) {
cout<<ptr->data<<" ";
ptr = ptr->next;
}
}

// pushes an element onto stack
void stack :: push(int element) {
node *new_element = new node;
new_element->data = element;
new_element->next = NULL;
if (top == NULL) {
// first node being pushed into stack
new_element->max_so_far = new_element->data;
top = new_element;
}
else {
new_element->max_so_far = max(top->max_so_far, new_element->data);
new_element->next = top;
top = new_element; // update top
}
}

// removes the top element from stack
void stack :: pop() {
if (top == NULL) {
cout<<"\nStack Empty";
}
else {
node *ptr = top;
top = top->next;
delete ptr;
}
}

// get the top element
int stack :: getTopElement() {
}

// get the max element is stack
int stack :: getMaxElement() {
}

// main
int main() {
stack s;
s.push(11);
s.push(33);
s.push(77);
s.push(49);
s.push(55);
s.push(99);
s.pop();
s.displayStack();
cout<<"\nTop Element :: "<<s.getTopElement();
cout<<"\nMax Element :: "<<s.getMaxElement();
cout<<endl;
return 0;
}```