Learn-dsa..in 30 days!



























CC-20 : Implement Stack that returns minimum element in O(1) time.

Description:

Implement and test a stack that returns the minimum element in O(1) time.

Test cases and expected outputs:

Input Parameters Expected outputs
Stack nodes:
28 <- 3 <- 34 <- 17 <- 33 <- 9 		Stack Min: 3
Stack nodes:
34 <- 17 <- 33 <- 9 		Stack Min: 9

Pseudocode:

Define a class named StackElement to hold the stack elements. StackElement will have following member variables:
nodeData : to hold the data of the StackElement.
nextNode: to hold a reference to the next node of the Stack.
stackMin: this will hold the minimum data within all nodeData of the current stack elements.
add() method:
Create an instance of StackElement class. Store the inputData in StackElement’s nodeData.
To handle addition of a new StackElement to start of a Stack, we need to handle 2 cases:
If Stack is empty add new StackElement as first StackElement of Stack. Set StackElement’s stackMin to input Data.
Else :
add new StackElement as first StackElement of Stack and point new StackElement’s nextNode link to original first StackElement of the stack.
If new StackElement‘s nodeData is greater than original first StackElement’s nodeData, then assign original first StackElement’s nodeData to new StackElement’s nodeData member variable.
remove() method:
If the Stack has only one StackElement, the set first node variable of Stack to null.
If the Stack already has more than one StackElement, then remove the first StackElement and return data of first StackElement and set second StackElement as the first node of the Stack.


Code:

public class StackWithMinInO1 {
private class StackElement{
	private StackElement nextNode=null;
	private int nodeData=0;
	private int stackMin=Integer.MIN_VALUE;
	
	public StackElement getNextNode() {
		return nextNode;
	}
	public void setNextNode(StackElement nextNode) {
		this.nextNode = nextNode;
	}

	public int getNodeData() {
		return nodeData;
	}
	public void setNodeData(int nodeData) {
		this.nodeData = nodeData;
	}
	
	public int getStackMin() {
		return stackMin;
	}
	public void setStackMin(int stackMin) {
		this.stackMin = stackMin;
	}
}

private StackElement firstNode=null;

public int get() {
	if (firstNode !=null) {
		return firstNode.getNodeData();
	}
	return Integer.MIN_VALUE;
}

public int getMin() {
	if (firstNode !=null) {
		return firstNode.getStackMin();
	}
	return Integer.MIN_VALUE;
}

public boolean add(int data){
	StackElement node=new StackElement();
	int min;
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setStackMin(data);
		node.setNextNode(null);
		return true;
	}
	else {
		if (firstNode.getStackMin()< data) {
			min=firstNode.getStackMin();
		}else {
			min=data;
		}
		node.setNextNode(firstNode);
		firstNode=node;
		node.setStackMin(min);
		return true;
	}
}

public int remove() {
	if (firstNode == null) { return Integer.MIN_VALUE; }
	int removedData=firstNode.getNodeData();
	if (firstNode.getNextNode()==null) {
		firstNode=null; 
		return removedData;
	}
	firstNode=firstNode.getNextNode();
	return removedData;
}

public int getSize() {
	StackElement currentNode=firstNode;
  	int idx=0;
  	while (currentNode !=null) {
  		currentNode=currentNode.getNextNode();
  		idx++;
  	}
  	return idx;
}
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us