Code Destine

Problem Statement

Design a stack data structure that supports the following operations in constant time O(1).

1. push(N) :- It insert element N onto the top of the stack.
2. pop() :- It removes and returns the element from the top of the stack.
3. peek() :- It returns (not remove) the element from the top of the stack.
4. getMax() :- It returns the maximum element in the stack.

Example 

MaxStack stack = new MaxStack();
stack.push(4);
stack.push(-5);
stack.push(2);
stack.getMax(); -- value: 4
stack.pop();
stack.peek(); -- value: -5
stack.getMax(); -- value: 4

Solution

The Linked List data structure can be used to design Max Stack data structure. Each node of linked list will contain three parts :

1. Data Part:- It contains the value to be pushed into the stack.
2. Max Part:- It contains the maximum value among all values, currently stored in the stack.
3. Next Part:- It contains pointer the next value in the stack.

Each operation of the max stack will work in the following way:

1. push(N) :- It creates and inserts a new node to the head of the linked list. Node’s data part contains element N, next part contains the current head of the linked list and max part contains a value, which is a maximum of element N and data part of the current head of the linked list.
2. pop() :- It removes and returns the head node and makes node next to the head node as a new head of the linked list.
3. peek() :- It returns data part of the head node.
4. getMax() :- It returns max part of the head node.

Program

public class MaxStack {
	
	public static void main(String[] args) {		
		MaxStack stack = new MaxStack();
		
		stack.push(4);
		stack.push(-5);
		stack.push(2);
		System.out.println("Max: " + stack.getMax());
		stack.pop();
		System.out.println("Peek: " + stack.peek());
		System.out.println("Max: " + stack.getMax()); 								
	} 

	private class Node {        
        int val;
        int max;
        Node next;
        Node(int val, int max){
            this.val = val;
            this.max = max;
        }        
    }
    
    private Node stack = null;
    
    public void push(int x) { 
    	Node node = new Node(x, x);
        if(this.stack == null){
        	this.stack = node;
        }else {
            if(this.stack.max > node.max){
                node.max = this.stack.max;
            }            
            node.next = this.stack;
            this.stack = node;
        }
    }
    
    public void pop() {
        if(this.stack != null){
        	this.stack = this.stack.next;  
        }
    }
    
    public int peek() {
        if(this.stack != null){
            return this.stack.val;
        }
        return -1;
    }
    
    public int getMax() {
        if(this.stack != null){
            return this.stack.max;
        }
        return -1;
    }
}

Result

Max: 4
Peek: -5
Max: 4

Similar Post

1. Design Maximum Frequency Stack Data Structure
2. Remove All Adjacent Duplicates In String
3. Backspace String Compare

That’s all for Design Max Stack Data Structure in Java, If you liked it, please share your thoughts in a comments section and share it with others too.