Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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;
Node head;
} 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);
// printf("read: %d\n", 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;
curr = s->head;
prev = s->head;
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;
s->head = NULL;
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) {
if (s->head == NULL) {
s->head = n;
} else {
n->next = s->head;
s->head = n;
}
// printf("push \t%p\n", n);
}
Node pop(Stack s) {
Node curr;
curr = NULL;
if (s->head != NULL) {
curr = s->head;
s->head = curr->next;
}
return curr;
}
#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();
return top->max_value;
}
};
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;
}
#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();
}
}
#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);
});
#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])