Learn-dsa..in 30 days!



























CC-4 : Deque – double ended queue.

Description:

Create a double ended Queue.

Test cases and expected outputs:

Input Parameters Expected outputs
QueueDequequeue=new QueueDeque();
queue.addFirst(9);
queue.addFirst (14);
queue.addFirst (17);
queue.addFirst (34);
queue.addLast(21); 		Queue nodes: 34 <- 17 <- 14 <- 9 <- 21
queue.removeFirst();
queue.removeFirst();
queue.removeLast(); 		Queue nodes: 14 <- 9

Pseudocode:

The FIFO Queue will use a LinkedList for storing data elements.
Maintain pointers to index of first and last data elements in the storage array.
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.
o If deque has only one node, then return data of firstNode and set firstNode and lastNode to null.
oElse:
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 QueueDeque {
	
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