Learn-dsa..in 30 days!



























CC-3 : Implement Stack using self-coded Deque LinkedList.

Description:

Create and test a Stack using a self-coded Deque LinkedList.

Test cases and expected outputs:

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

Pseudocode:

The Deque Stack will use a LinkedList for storing data elements.
We need to maintain pointers to index of first and last data elements in the LinkedList.
The addFirst() method:
Check if Deque is empty, in that case add the new node as firstnode and set firstNode and lastNode pointers to point to the new node.
Else:
Set current firstNode as nextNode of new node.
Set new node as previousNode of firstNode .
Set firstNode pointer to point to new node.
The addLast() method:
Check if Deque is empty, in that case add the new node as firstnode and set firstNode and lastNode pointers to point to the new node.
Else:
Set current lastNode as previousNode of new node.
Set new node as nextNode of lastNodeNode.
Set nextNode of lastNode to null.
Set lastNode pointer to point to new node.
The removeFirst() method:
Check if Deque is empty, then return Integer.MIN_VALUE to indicate deque is empty.
If deque has only one node, return data of firstNode and set firstNode and lastNode to null.
Else:
Set removedData to data of firstNode.
Set firstNode to nextNode of firstNode.
Set firstNode’s previousNode to null.
Return removedData.
The removeLast() method:
Check if Deque is empty, then return Integer.MIN_VALUE to indicate deque is empty.
If deque has only one node, then return data of firstNode and set firstNode and lastNode to null.
Else:
Set removedData to data of lastNode.
Set prevNode to previous node of lastNode.
Set prevNode’s nextNode to null.
Set lastNode to prevNode.
Return removedData.

Code:

public class StackDeque {	
	
private DequeNode firstNode=null;
private DequeNode lastNode=null;	

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

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

public boolean addFirst(int data){
	DequeNode node=new DequeNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		lastNode=node;
		node.setNextNode(null);
		node.setPreviousNode(null);
		return true;
	}else {
		node.setNextNode(firstNode);
		firstNode.setPreviousNode(node);
		firstNode=node; 
		node.setPreviousNode(null);
		return true;			
	}
}

public boolean addLast(int data){
	DequeNode node=new DequeNode();
	node.setNodeData(data);
	if (lastNode==null) { 
		firstNode=node; 
		lastNode=node;
		node.setNextNode(null);
		return true;
	}
	else {
		lastNode.setNextNode(node);
		node.setNextNode(null);
		node.setPreviousNode(lastNode);
		lastNode=node;
		return true;			
	}
}

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

public int removeLast() {
	if (lastNode == null) { return Integer.MIN_VALUE; }
	int removedData=lastNode.getNodeData();
	if (lastNode.getPreviousNode()==null) {
		firstNode=null; 
		lastNode=null;
		return removedData;
	}
	DequeNode prevNode=lastNode.getPreviousNode();
	prevNode.setNextNode(null);
	lastNode=prevNode;
	return removedData;
	
}
}

Click here to download and run code and test cases !


Next Page >


About UsPrivacy PolicyContact us