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. getMin() :- It returns the minimum element in the stack.

Example 

MinStack stack = new MinStack();
stack.push(-2);
stack.push(2);
stack.push(-3);
stack.getMin(); -- value: -3
stack.pop();
stack.peek(); -- value: 2
stack.getMin(); -- value: -2

Solution

The Linked List data structure can be used to design Min 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. Min Part:- It contains the minimum 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 min 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 min part contains a value, which is a minimum 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. getMin() :- It returns min part of the head node.

Program

public class MinStack {
	
	public static void main(String[] args) {		
		MinStack stack = new MinStack();
		
		stack.push(-2);
		stack.push(2);
		stack.push(-3);
		System.out.println("Min: " + stack.getMin());
		stack.pop();
		System.out.println("Peek: " + stack.peek());
		System.out.println("Min: " + stack.getMin()); 								
	} 

	private class Node {        
        int val;
        int min;
        Node next;
        Node(int val, int min){
            this.val = val;
            this.min = min;
        }        
    }
    
    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.min < node.min){
                node.min = this.stack.min;
            }            
            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 getMin() {
        if(this.stack != null){
            return this.stack.min;
        }
        return -1;
    }
}

Result

Min: -3
Peek: 2
Min: -2

Similar Post

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

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