CC-4 : Implement Priority Stack using LinkedList.

Description:

: A Priority Stack stores and return elements in terms of priority, rather than FIFO. Create and test a Priority Stack with integer data using LinkedList. Priority should be based on numerical value of integer data.

Test cases and expected outputs:

Input Parameters	Expected outputs
StackPriority stack=new StackPriority(); stack.add(9); stack.add(14); stack.add(17); stack.add(34); stack.add(21); stack.add(28);	Stack nodes: 34 <- 28 <- 21 <- 17 <- 14 <- 9
stack.remove(); stack.remove(); stack.remove();	Stack nodes: 17 <- 14 <- 9

Pseudocode:

The Priority Stack will use a LinkedList for storing data elements.

Refer to code for Stack implementation from code challenge 1.

For Priority Stack we just to need to replace add() method in Stack code by addByPriority() method. Rest of the code remains the same.

addByPriority() method:

If Priority Stack is currently empty, set new node as firstNode of Priority Stack.

Else If new node’s data is greater than data of firstNode, set new node as firstNode of priority Stack.

Else Navigate the Priority Stack nodes from firstNode onwards. Keep going to next node till we find a node that’s data is lesser than data of new node. Insert new node between the current node and its previousNode.

Else if while navigating if we reach end of the Priority Stack (that is all nodes data is less than data of new node) then add new node as last node of the Priority Stack.

Code:

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

public boolean addByPriority(int data){
	StackNode node=new StackNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(null);
		return true;		
	}
	if (firstNode.getNodeData()<=data) {
		node.setNextNode(firstNode);
		firstNode=node;
		return true;				
	}
	StackNode currNode=firstNode;
	StackNode prevNode=null;
	while (( currNode != null) && (currNode.getNodeData() > data))	{
		prevNode=currNode;
		currNode=currNode.getNextNode();				
	}
	if (currNode != null) {
		prevNode.setNextNode(node);
		node.setNextNode(currNode);
		return true;
	} 
	if (currNode == null){
		prevNode.setNextNode(node);
		node.setNextNode(null);
	}	
	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;
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

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

public boolean addByPriority(int data){
	StackNode node=new StackNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(null);
		return true;		
	}
	if (firstNode.getNodeData()<=data) {
		node.setNextNode(firstNode);
		firstNode=node;
		return true;				
	}
	StackNode currNode=firstNode;
	StackNode prevNode=null;
	while (( currNode != null) && (currNode.getNodeData() > data))	{
		prevNode=currNode;
		currNode=currNode.getNextNode();				
	}
	if (currNode != null) {
		prevNode.setNextNode(node);
		node.setNextNode(currNode);
		return true;
	} 
	if (currNode == null){
		prevNode.setNextNode(node);
		node.setNextNode(null);
	}	
	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() {
	StackNode currentNode=firstNode;
  	int idx=0;
  	while (currentNode !=null) {
  		currentNode=currentNode.getNextNode();
  		idx++;
  	}
  	return idx;
}

public void traverse() {
	StackNode currentNode=firstNode;
	while (currentNode !=null) {
  		System.out.println(currentNode.getNodeData());
  		currentNode=currentNode.getNextNode();
  	}
}			

public void printStack() throws Exception    {
    if (firstNode == null) { System.out.println("Stack empty"); return; }
    StackNode currentNode=firstNode;
	System.out.println();
	System.out.println("***************************************************************");
	System.out.print("Stack nodes: ");
	do  {
	    System.out.print(currentNode.getNodeData());
	    if (currentNode.getNextNode() != null)  System.out.print(" <- ");
		currentNode=currentNode.getNextNode();
	} while( currentNode != null);
		System.out.println();
		System.out.println("***************************************************************");
		System.out.println();
		Thread.sleep(2000);
		return;
}  
  	
public static void main(String[] args) {
	
	try {
	StackPriority stack=new StackPriority();
	System.out.print("Add to Stack");
	stack.addByPriority(99);
	stack.printStack();
	System.out.print("Add to Stack");
	stack.addByPriority(14);
	stack.printStack();
	System.out.print("Add to Stack");
	stack.addByPriority(77);
	stack.printStack();
	System.out.print("Add to Stack");
	stack.addByPriority(34);
	stack.printStack();
	System.out.print("Add to Stack");
	stack.addByPriority(21);
	stack.printStack();
	System.out.print("Add to Stack");
	stack.addByPriority(82);
	stack.printStack();
	
	System.out.println("QUEUE SIZE "+stack.getSize());
	
	System.out.print("\nRemove from Queue");
	stack.remove();
	stack.printStack();
	System.out.print("Remove from Queue");
	stack.remove();
	stack.printStack();
	System.out.print("Remove from Queue");
	
	System.out.println("GET FIRST NODE "+stack.get());
	
	stack.remove();
	stack.printStack();
	System.out.print("\nRemove from Queue");
	stack.remove();
	stack.printStack();
	System.out.print("Remove from Queue");
	stack.remove();
	stack.printStack();
	System.out.print("Remove from Queue");
	stack.remove();
	stack.printStack();
	
	System.out.println("QUEUE SIZE "+stack.getSize());
	System.out.println("\nGET FIRST NODE "+stack.get());
	
	System.out.print("Add to Queue");
	stack.addByPriority(99);
	stack.printStack();
	System.out.print("Add to Queue");
	stack.addByPriority(9);
	stack.printStack();
	System.out.print("Add to Queue");
	stack.addByPriority(31);
	stack.printStack();
	System.out.print("Remove from Queue");
	stack.remove();
	stack.printStack();
	System.out.print("Remove from Queue");
	stack.remove();
	stack.printStack();	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
	}	
}

public class StackNode {
	private StackNode nextNode=null;
	private int nodeData=0;
	
	public StackNode getNextNode() {
		return nextNode;
	}
	public void setNextNode(StackNode nextNode) {
		this.nextNode = nextNode;
	}	
	public int getNodeData() {
		return nodeData;
	}
	public void setNodeData(int nodeData) {
		this.nodeData = nodeData;
	}
}
	
}