## Algorithm

Problem Name: Data Structures - Maximum Element

In this HackerRank in Data Structures - Maximum Element solutions

You have an empty sequence, and you will be given N queries. Each query is one of these three types:

``````1 x  -Push the element x into the stack.
2    -Delete the element present at the top of the stack.
3    -Print the maximum element in the stack.
``````

Function Description

Complete the getMax function in the editor below.

getMax has the following parameters:
- string operations[n]: operations as strings

Returns
- int[]: the answers to each type 3 query

Input Format

The first line of input contains an integer, n. The next n lines each contain an above mentioned query.

Constraints

1 <= n <= 10**5

1 <= x <= 10**9

1 <= type <= 3

All queries are valid.

Sample Input

```STDIN   Function
-----   --------
10      operations[] size n = 10
1 97    operations = ['1 97', '2', '1 20', ....]
2
1 20
2
1 26
1 20
2
3
1 91
3
```

Sample Output

``````26
91
``````

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef struct node *Node;
typedef struct stackRep *Stack;

typedef struct node {
int data;
int prevMax;
Node next;
} node;

typedef struct stackRep {
int maxElt;
} stack;

Stack newStack(void);
void destroyStack(Stack s);
Node newNode(Stack s, int i);
void push(Stack s, Node n);
Node pop(Stack s);

int main(int argc, char *argv[]) {

int i;
int lines;

i = 0;
fscanf(stdin, "%d", &lines);

Stack s;
s = newStack();

while (i  <  lines) {
int req;
fscanf(stdin, "%d", &req);

if (req == 1) {
// push

int data;
fscanf(stdin, "%d", &data);
// printf("pushing %d..\n", data);

Node n;
n = newNode(s, data);
push(s, n);

if (data > s->maxElt) {
s->maxElt = data;
}

} else if (req == 2) {
// pop
// printf("popping\n");
Node n;
n = pop(s);

if (n->data == s->maxElt) {
s->maxElt = n->prevMax;
}

free(n);

} else {
// return max
printf("%d\n", s->maxElt);
}

i += 1;
}

destroyStack(s);

return EXIT_SUCCESS;
}

void destroyStack(Stack s) {
if (s != NULL) {
Node curr;
Node prev;

while (curr->next != NULL) {
prev = curr;
curr = curr->next;
free(prev);
}

free(curr);
}

free(s);
}

Stack newStack(void) {
Stack s;
s = malloc(sizeof(struct stackRep) * 1);
s->maxElt = 0;
return s;
}

Node newNode(Stack s, int i) {
Node n;
n = malloc(sizeof(struct node) * 1);
n->data = i;
n->prevMax = s->maxElt;
n->next = NULL;
return n;
}

void push(Stack s, Node n) {
} else {
}
// printf("push \t%p\n", n);
}

Node pop(Stack s) {

Node curr;
curr = NULL;

}

return curr;
}
``````
Copy The Code &

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <iostream>

using namespace std;

struct stack {
struct s_node {
int value;
int max_value;
s_node *prev;
};

s_node *top = nullptr;

void push(int value) {
top = new s_node { value, top ? max(top->max_value, value) : value, top };
}

void pop() {
if (top)
top = top->prev;
}

int max_value() {
if (!top)
throw exception();
}
};

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
stack s;
int n; cin >> n;
while (n--) {
int o; cin >> o;
switch (o) {
case 1: {
int v; cin >> v;
s.push(v);
}
break;
case 2:
s.pop();
break;
case 3:
cout << s.max_value() << '\n';
break;
}
}
return 0;
}
``````
Copy The Code &

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
import java.io.*;
import java.util.*;

public class Solution {
private static void getMaxElementFromStack()
{
Stack < Integer> stack = new Stack();
Stack onlyMaxs = new Stack();

Scanner sc = new Scanner(System.in);

int N = Integer.parseInt(sc.nextLine());
int temp = 0;

while(sc.hasNext())
{
String type[] = sc.nextLine().split(" ");
switch(type[0])
{
case "1":
temp = Integer.parseInt(type[1]);
stack.push(temp);
if(onlyMaxs.isEmpty() || onlyMaxs.peek() <= temp)
onlyMaxs.push(temp);
break;
case "2":
temp = stack.pop();
if(temp == onlyMaxs.peek())
onlyMaxs.pop();
break;
case "3":
System.out.println(onlyMaxs.peek()>;
}
N--;
}

while(N-- > 0)
System.out.println(onlyMaxs.peek());

}
public static void main(String[] args) {
getMaxElementFromStack();
}
}
``````
Copy The Code &

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
function processData(input) {
var inputs = input.split('\n');

var stack = new MaxStack();
for (var i = 1; i  <  inputs.length; i++) {
var operation = inputs[i].charAt(0);
if (operation === '1') {
var data = inputs[i].split(' ');
stack.push(parseInt(data[1], 10));
} else if (operation === '2') {
stack.pop();
} else if (operation === '3') {
console.log(stack.max());
}
}
}

function MaxStack() {
var self = this,
data = [],
maxes = [];

this.push = function(item) {
data.push(item);
if (self.max() === null || self.max()  < = item) {
maxes.push(item);
}
};

this.pop = function() {
if (data.length === 0) {
return null;
}

var poppedItem = data.pop();
if (poppedItem === self.max()) {
maxes.pop();
}
return poppedItem;
};

this.max = function() {
if (maxes.length === 0) {
return null;
}
return maxes[maxes.length - 1];
};
};

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
_input += input;
});

process.stdin.on("end", function () {
processData(_input);
});
``````
Copy The Code &

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
n = int(input())
stack = []
most = []

for i in range(n):
data = input().split(' ')
x = int(data[0])
v = 0
if len(data) > 1: v = int(data[1])
if x == 1:
stack.append(v)
if not most or most[-1] <= v: most.append(v)
elif x == 2:
v = stack.pop()
if most[-1] == v: most.pop()
else:
print(most[-1])
``````
Copy The Code &