Java Programs example Priority Queue
// Priority Queue
import java.util.Scanner;
class Node {
public int requestID, priority;
public Node next;
public Node(int id, int p) {
requestID=id; priority=p;
}
}
//////////////////////////////////////////////
class mySLL_Queue {
protected Node head, tail;
public mySLL_Queue() { head = tail = null; }
public void enqueue(int el, int p) { // addToTail
Node newNode = new Node(el, p);
newNode.next = null;
if (head == null) // empty
head = tail = newNode;
else {
tail.next = newNode;
tail = newNode;
}
}
public int dequeue() { // deleteFromHead
if(head == null) // empty
return -1;
int el = head.requestID;
if (head == tail) // if only one node on the list;
head = tail = null;
else {
int p =10; // remove a node with highest priority
while( (el=delete(p)) == -1)
p--;
}
return el;
}
public void printAll() {
for (Node tmp = head; tmp != null; tmp = tmp.next)
System.out.println(tmp.requestID + "(" + tmp.priority + ")" );
}
public int delete(int p) { // delete target node with el;
Node prev = head, tmp = head.next;
while ( tmp != null && tmp.priority != p) {
prev = prev.next;
tmp = tmp.next;
}
if (tmp != null) { // if el was found;
prev.next = tmp.next;
if (tmp == tail) // if el is in last node;
tail = prev;
}
else
return -1;
return tmp.requestID;
} ////////////////////////////////////
}
///////////////////////////////////////////////
public class Queue_Using_SinglyLinkedList {
public static void main(String[] args) {
mySLL_Queue sllQueue = new mySLL_Queue();
int cust=1, opt, pri;
Scanner sc = new Scanner(System.in);
while (true){
System.out.println("Priority Queue\n 1. Add a customer\n 2. Remove a customer\n3. Show the queue\n4. Exit \n Your choice? ");
opt = sc.nextInt();
if(opt==1){
System.out.println("Enter priority? ");
pri = sc.nextInt();
System.out.print("Added Customer # ");
sllQueue.enqueue(cust++, pri);
}
else if(opt==2){
System.out.println("Removed customer # " + sllQueue.dequeue());
}
else if(opt==3){
System.out.print("Queue = " );
sllQueue.printAll();
}
else if(opt==4){
return;
}
else
System.out.println("Wrong option selected...");
}
}
}
===
// Evaluating Postfix Expression
import java.util.*;
import java.util.Scanner;
public class Postfix {
public static void main(String[] args) {
System.out.println("Evaluating Postfix Expression\n");
Scanner sc = new Scanner(System.in);
System.out.println("Input an expression:");
String exp = sc.nextLine();
System.out.println(postfixEvaluate(exp));
}
public static Double postfixEvaluate(String exp) {
Stack<Double> s = new Stack<Double> ();
Scanner tokens = new Scanner(exp);
while (tokens.hasNext()) {
if (tokens.hasNextDouble()) {
s.push(tokens.nextDouble());
}
else {
Double num2 = s.pop();
Double num1 = s.pop();
String op = tokens.next();
if (op.equals("+")) {
s.push(num1 + num2);
}
else if (op.equals("-")) {
s.push(num1 - num2);
}
else if (op.equals("*")) {
s.push(num1 * num2);
}
else if (op.equals("/")) {
s.push(num1 / num2);
}
else
System.out.println("Error in input...");
}
}
return s.pop();
}
}
=============
//bst Modify BST_Recursive.java of Lab-10:Exercise#2 to write a complete program to
//implement a spare-parts database with itemNo, price and description.
import java.util.Scanner;
class BSTNode {
int itemNum;
double Price;
String Discription;
BSTNode left, right;
public BSTNode(int itemNum, double Price, String Discription) {
this.itemNum = itemNum;
this.Price = Price;
this.Discription = Discription;
left = right = null;
}
}
class BinaryTree {
BSTNode root;
BinaryTree() { root = null; }
boolean searchByItemNum(int itemNum){ return searchRecursion(root, itemNum) != null; }
public BSTNode searchRecursion(BSTNode root, int num) {
if (root==null || root.itemNum ==num)
return root;
if (root.itemNum > num)
return searchRecursion(root.left, num);
return searchRecursion (root.right, num);
}
void deleteKey(int num) {
root = deleteRec(root, num);
}
BSTNode deleteRec(BSTNode root, int num) {
if (root == null) return root;
if (num < root.itemNum)
root.left = deleteRec(root.left, num);
else if (num > root.itemNum)
root.right = deleteRec(root.right, num);
else {
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
root.itemNum = minValue(root.right);
root.right = deleteRec(root.right, root.itemNum);
}
return root;
}
int minValue(BSTNode root) {
int minv = root.itemNum;
while (root.left != null) {
minv = root.left.itemNum;
root = root.left;
}
return minv;
}
void insert(int num,double price,String dis) {
root = insertRec(root, num,price,dis);
}
BSTNode insertRec(BSTNode root, int Num,double price,String disc) {
if (root == null) {
root = new BSTNode(Num,price,disc);
return root;
}
if (Num < root.itemNum)
root.left = insertRec(root.left,Num,price,disc);
else if (Num > root.itemNum)
root.right = insertRec(root.right,Num,price,disc);
return root;
}
void inorder() {
if(root == null)
System.out.println("== DATABASE IS EMPTY ! ==");
else
inorderRec(root);
}
void inorderRec(BSTNode root) {
if (root != null) {
inorderRec(root.left);
System.out.print("\n================================\nItem Num.: "+root.itemNum + "\nPrice :
"+root.Price+"\nDescription : "+root.Discription+"\n================================\n");
inorderRec(root.right);
}
}
void Run() {
Scanner sc = new Scanner(System.in);
int n;
System.out.print("\n1.insert. \n2.Search. \n3.Delete. \n4.Show all. \n5.Exit.");
System.out.print("\n\nYour option : ");
n = sc.nextInt();
switch (n) {
case 1:
System.out.print("\nEnter Item Number: ");
int item;
item = sc.nextInt();
System.out.print("Enter Price: ");
double price;
price = sc.nextDouble();
System.out.print("Enter Discription: ");
String Discription;
Discription = sc.next();
insert(item, price, Discription);
System.out.println("\n<< Item " + item + " added >>\n");
Run();
break;
case 2:
System.out.print("\nEnter item Num. : ");
int nu;
nu = sc.nextInt();
if (searchByItemNum(nu)) {
System.out.println("\n << Found >> ");
System.out.print("\n================================\nItem No.: " + root.itemNum + "\nPrice : " + root.Price +
"\nDescription : " + root.Discription + "\n================================\n");
} else {
System.out.println(" ** Not Found ** ");
}
Run();
break;
case 3:
System.out.println("\nEnter item Num. : ");
int num;
num = sc.nextInt();
deleteKey(num);
Run();
break;
case 4:
inorder();
Run();
break;
case 5:
return;
default:
System.out.println("ENTER NUMBER FROM '1 TO 5'");
Run();
break;
}
}
}
public class hw5a {
public static void main(String[] args) {
System.out.println("<< Spare-parts Database >>");
BinaryTree bst = new BinaryTree();
bst.Run();
}
}
================
//Dijkstra’s algorithm for shortest path u
import java.util.*;
// Data structure to store graph edges
class Edge {
int source, dest, weight;
public Edge(int source, int dest, int weight) {
this.source = source;
this.dest = dest;
this.weight = weight;
}
}
// Data structure to store heap nodes
class Node {
int vertex, weight;
public Node(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
}
// class to represent a graph object
class Graph {
// A List of Lists to represent an adjacency list
List<List<Edge>> adjList = null;
// Constructor
Graph(List<Edge> edges, int N) {
adjList = new ArrayList<>(N);
for (int i = 0; i < N; i++) {
adjList.add(i, new ArrayList<>());
}
// add edges to the undirected graph
for (Edge edge: edges) {
adjList.get(edge.source).add(edge);
}
}
}
public class Dijkstra_aryLists {
private static void getRoute(int prev[], int i, List<Integer> route) {
if (i >= 0) {
getRoute(prev, prev[i], route);
route.add(i);
}
}
// Run Dijkstra's algorithm on given graph
public static void shortestPath(Graph graph, int source, int N) {
// create min heap and push source node having distance 0
PriorityQueue<Node> minHeap;
minHeap = new PriorityQueue<>(Comparator.comparingInt(node -> node.weight));
minHeap.add(new Node(source, 0));
// set infinite distance from source to v initially
List<Integer> dist = new ArrayList<>(Collections.nCopies(N, Integer.MAX_VALUE));
// distance from source to itself is zero
dist.set(source, 0);
// boolean array to track vertices for which minimum
// cost is already found
boolean[] done = new boolean[N];
done[source] = true;
// stores predecessor of a vertex (to print path)
int prev[] = new int[N];
prev[source] = -1;
List<Integer> route = new ArrayList<>();
// run till minHeap is not empty
while (!minHeap.isEmpty()) {
// Remove and return best vertex
Node node = minHeap.poll();
// get vertex number
int u = node.vertex;
// do for each neighbor v of u
for (Edge edge: graph.adjList.get(u))
{
int v = edge.dest;
int weight = edge.weight;
// Relaxation step
if (!done[v] && (dist.get(u) + weight) < dist.get(v))
{
dist.set(v, dist.get(u) + weight);
prev[v] = u;
minHeap.add(new Node(v, dist.get(v)));
}
}
// marked vertex u as done so it will not get picked up again
done[u] = true;
}
for (int i = 1; i < N; ++i) {
if (i != source && dist.get(i) != Integer.MAX_VALUE) {
getRoute(prev, i, route);
System.out.printf("Path (%d -> %d): Minimum Cost = %d and Route is %s\n",
source, i, dist.get(i), route);
route.clear();
}
}
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
// initialize edges as per above diagram
// (u, v, w) triplet represent undirected edge from
// vertex u to vertex v having weight w
// Set number of vertices in the graph
System.out.println("Enter The number of edges");
int N=sc.nextInt();
List<Edge> edges = new ArrayList<Edge>();
for(int i=0;i<N;i++) {
System.out.println("Enter the values for edge " + i);
System.out.println("Enter The values of U");
int u=sc.nextInt();
System.out.println("Enter The values of V");
int v=sc.nextInt();
System.out.println("Enter The values of W");
int w=sc.nextInt();
edges.add(new Edge(u, v, w));
}
// construct graph
Graph graph = new Graph(edges, N);
int source = 0;
shortestPath(graph, source, N);
}
}
================
//Hashing.
// Provide an option menu: 1) Insert, 2) Find, 3) Delete, 4) Show table, 5) Exit.
//Input user option and data to perform the required operation.
import java.util.Scanner;
public class Hashtable_Using_Java_Class {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//1. Create Hashtable
Hashtable<Integer, String> ht = new Hashtable<>();
char ch;
while(true){
System.out.println("\nHash Table Operations\n");
System.out.println("1. Insert ");
System.out.println("2. Find");
System.out.println("3. Delete");
System.out.println("4. Show");
System.out.println("5. Exit");
int choice = scan.nextInt();
switch (choice) {
case 1 :
System.out.println("Enter key and value");
ht.put(scan.nextInt(), scan.next() );
break;
case 2 :
System.out.println("Enter key");
System.out.println("Value = "+ ht.get( scan.nextInt() ));
break;
case 3 :
System.out.println("Enter key");
ht.remove( scan.nextInt() );
break;
case 4 :
System.out.println("Hash Table = \n" + ht);
break;
case 5 :
System.out.println("Bye... " );
break;
default :
System.out.println("Wrong option... \n ");
break;
}
}
}
}
