Code Destine

Problem Statement

Design a Queue (FIFO) data structure using Linked List. The Queue data structure will supports the following operations:

1. enqueue(N) :- It insert element N to the back of the queue.
2. dequeue() :- It removes and returns the element from the front of the queue.
3. peek() :- It returns (not remove) the element from the front of the queue.
4. isEmpty() :- It checks whether the queue is empty.
5. size() :- It return the total number of elements.
6. iterator() :- It returns the java iterator object for iterating through the elements of the queue.

Example 

Queue queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);  
queue.peek();  // returns 10
queue.dequeue();   // returns 10
queue.isEmpty(); // returns false

Solution

Each node of linked list will contain two parts :

1. Data Part:- It contains the value to be pushed into the queue.
2. Next Part:- It contains pointer the next value in the queue.

Each operation of the queue will work in the following way:

1. enqueue(N) :- It creates and inserts a new node to the tail of the linked list. Node’s data part contains element N, next part contains the current head of the linked list.
2. dequeue() :- 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. isEmpty() :- If head of the linked list is null, then returns true otherwise returns false.
5. size() :- It traverses the linked list and count the total number of nodes and return the count.
6. iterator() :- It returns the object of QueueIterator class.

Queue Interface

public interface Queue<T> extends Iterable<T> {

	public void enqueue(T t);
	
	public T dequeue();
	
	public T peek();
	
	public boolean isEmpty();
	
	public int size();
	
}

Queue Implementation

import java.util.Iterator;

public class LinkedListQueue<T> implements Queue<T> {

	private Node head;
	private Node tail;
	
	@Override
	public void enqueue(T t) {
		Node temp = new Node();
		temp.element = t;
		temp.next = null;
		if(tail == null){
			tail = temp;
			head = temp;
		}else{
			tail.next = temp;
			tail = temp;
		}
	}

	@Override
	public T dequeue() {
		T t = head.element;
		head = head.next;
		return t;
	}
	
	@Override
	public T peek() {
		if(head != null) {
			return head.element;
		}
		return null;
	}

	@Override
	public boolean isEmpty() {
		return head == null;
	}

	@Override
	public int size() {
		Node temp = head;
		int count = 0;
		while(temp != null){
			temp = temp.next; 
			count++;
		}
		return count;
	}
	
	private class Node{
		T element;
		Node next;
	}

	@Override
	public Iterator<T> iterator() {
		return new QueueIterator<T>(head);
	}
	
	private class QueueIterator<T> implements Iterator<T>{

		private LinkedListQueue<T>.Node head;
		
		public QueueIterator(LinkedListQueue<T>.Node head) {
			super();
			this.head = head;
		}

		@Override
		public boolean hasNext() {
			return head !=null;
		}

		@Override
		public T next() {
			if(head != null){
				T t = head.element;
				head = head.next;
				return t;
			}else {
				throw new RuntimeException("Iterator Exhuested Exception");
			}
		}		
	}
}

Similar Post

1. Design Stack using Dynamic Array
2. Design Queue using Dynamic Array
3. Design PriorityQueue using Binary Heap

That’s all for Design Queue using Linked List in Java, If you liked it, please share your thoughts in a comments section and share it with others too.