ISourceCode

Make the frequent cases fast and the rare case correct

Category Archives: Queue

Priority Queue based on Sorted Linked Lists

Sorted list implementation: Like a checkout line at the supermarket, but where important people get to “cut” in front of less important people. (if using a basic array/list, this takes O(n) insertion time, O(1) pullNext time (from the front), and on average O(n*log(n)) to initialize (if using quicksort) or O(N2) for insertion sort – Wikipedia

class Node
{
	public int item;
	public Node next;
	public Node(int val)
	{
		item = val;
	}
}
class PQSort
{
	private Node first;
	public PQSort()
	{ first = null; }
	public void insert(Node k)
	{
		Node previous = null;
		Node current = first;
		while(current != null && k.item > current.item)
		{
			previous = current;
			current = current.next;
		}
		if(previous==null)
			first = k;
		else
			previous.next = k;
			k.next = current;
	}
	public Node pop()
	{
		Node temp = first;
		first = first.next;
		return temp;
	}
}
class PriorityQueue
{
	public static void main(String[] args)
	{
		int size = 10;
		PQSort thePQSort = new PQSort();
		for(int j=0; j<size; j++)
		{
			int n = (int)(java.lang.Math.random()*99);
			Node newLink = new Node(n);
			thePQSort.insert(newLink);			
		}
		System.out.println("Inserted elements at random into the queue such that Priority queue contains highest element at the end");
		System.out.println("sorted List based on Priority Queue . removing minimum element from the front of the list and displaying: ");
	
		for(int j=0; j<size; j++)
			System.out.print(thePQSort.pop().item + " ");
			System.out.println("");
	}
}

OUTPUT:

~/PriorityQSort$ java PriorityQueue
Inserted elements at random into the queue such that Priority queue contains highest element at the end
sorted List based on Priority Queue . removing minimum element from the front of the list and displaying:
10 32 35 37 45 47 56 63 67 84

Efficient way of implementing a Priority queue is by using a heap O(nlog(n))

Queue implementation using a Linked List

A queue is First in First out data structure. We define two methods of a linked list i.e to insert a node at the end of the list and then deleting the node from the beginning of the list.

When an element is inserted into the list it is further away from the start node. a new node becomes the start node if the list is empty.An element is deleted from the front of the list.

import java.io.*;
class Node{
	public int item;
	public Node next;
	public Node(int val){ 
		item = val; 
	}
	public void displayNode(){ 
		System.out.print("[" + item + "]"); 
	}
}
class LinkedList{
	private Node start;
	private Node end;
	public LinkedList(){
		start = null;
		end = null;
	}
	public boolean isEmpty(){ 
		return start==null; 
	}
	public void insertEnd(int val){//Insert node at the end of list
		Node newNode = new Node(val);
		if( isEmpty() )
			start = newNode;
		else
			end.next = newNode;
		end = newNode;
	}
	public int deleteStart(){//delete the node from the beginning of the list
		int temp = start.item;
		if(start.next == null)
			end = null;
		start = start.next;
		return temp;
	}
	public void displayList(){
		Node current = start;
		while(current != null)
		{
			current.displayNode();
			current = current.next;
		}
		System.out.println("");
	}
}
class Queue{
	private LinkedList listObj;
	public Queue(){
		listObj = new LinkedList(); 
	}
	public boolean isEmpty(){ 
		return listObj.isEmpty(); 
	}
	public void insert(int k){ 
		listObj.insertEnd(k); 
	}
	public int delete(){ 
		return listObj.deleteStart(); 
	}
	public void display(){
		System.out.print("Queue [start to end]: ");
		listObj.displayList();
	}
}
class ListQueueBlog{
	public static void main(String[] args){	
		Queue demo = new Queue();
		System.out.println("Inserting two elements into the queue");
		demo.insert(10);
		demo.insert(20);
		demo.display();
		System.out.println("Inserting one more element into the queue at the end");
 		demo.insert(30);
		demo.display();
		System.out.println("Deleting one element from the front");
		demo.delete();
		demo.display(); 
	} 
}

OUTPUT:

~/ListQueue$ java ListQueueBlog
Inserting two elements into the queue
Queue [start to end]: [10][20]
Inserting one more element into the queue at the end
Queue [start to end]: [10][20][30]
Deleting one element from the front
Queue [start to end]: [20][30]

Follow

Get every new post delivered to your Inbox.