1. Suppose you want to implement an ADT in which you can insert values and retri

Question

1. Suppose you want to implement an ADT in which you can insert values and retrieve or remove the item with smallest value. (This ADT is called a priority queue). If forced to choose between an array implementation and a linked list implementation, which would you choose and why?


2. Write a recursive function that reads a list of integers from the console and prints them in reverse order. The function should read until a negative number is encountered. You may only use one local variable of type int. (So arrays or other aggregate data types are allowed.)
Example: 4 5 6 7 8 9 10 -1
10 9 8 7 6 5 4

3. Repeat question 2 using a local stack rather than recursion.

Explanation / Answer

import java.util.Scanner;

class Value
{
String name;
int priority;

/** Constructor **/
public Value(String name, int priority)
{
this.name = name;
this.priority = priority;   
}
/** toString() **/
public String toString()
{
return "Value Name : "+ name +" Priority : "+ priority;
}
}

/** Class PQ **/
class PQ
{
private Value[] SortedArray;
private int Size, Limit;

/** Constructor **/
public PQ(int Limit)
{
this.Limit = Limit + 1;
SortedArray = new Value[this.Limit];
Size = 0;
}
/** function to clear **/
public void clear()
{
SortedArray = new Value[Limit];
Size = 0;
}
/** function to check if empty **/
public boolean isEmpty()
{
return Size == 0;
}
/** function to check if full **/
public boolean isFull()
{
return Size == Limit - 1;
}
/** function to get Size **/
public int size()
{
return Size;
}
/** function to insert task **/
public void insert(String name, int priority)
{
Value Temp = new Value(name, priority);

SortedArray[++Size] = Temp;
int pos = Size;
while (pos != 1 && Temp.priority > SortedArray[pos/2].priority)
{
SortedArray[pos] = SortedArray[pos/2];
pos /=2;
}
SortedArray[pos] = Temp;
}
/** function to remove task **/
public Value remove()
{
int p, c;
Value item, temp;
if (isEmpty() )
{
System.out.println("array is empty");
return null;
}

temp = SortedArray[1];
item = SortedArray[Size--];

p = 1;
c = 2;
while (c <= Size)
{
if (c < Size && SortedArray[c].priority >SortedArray[c + 1].priority)
c++;
if (temp.priority <=SortedArray[c].priority)
break;

SortedArray[p] = SortedArray[c];
p = c;
c *= 2;
}
SortedArray[p] = temp;

return item;
}
}

public class PQTest
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
  

PQ pq = new PQ(4 );
  
pq.insert("A",1);
pq.insert("B",2);
pq.insert("C",10);
pq.insert("D",94);
System.out.println("Value A(32),B(2),C(1),D(94) inserted ");

System.out.println("Value removed "+pq.remove());
}

}

====================================================

Output:

akshay@akshay-Inspiron-3537:~/Chegg$ javac PQTest.java
akshay@akshay-Inspiron-3537:~/Chegg$ java PQTest
Value A(32),B(2),C(1),D(94) inserted

Value removed Value Name : A
Priority : 1

==========================================================

import java.util.*;
public class reverse {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<Integer>();
System.out.println("Enter elements");

Scanner sc=new Scanner(System.in);
int num;

while((num=sc.nextInt())>0)
{
stack.push(num);
}

System.out.println("Elements in reverse order");

reverseStack(stack);
for (int i = 0, n = stack.size(); i < n; i++) {
System.out.println(stack.elementAt(i));
}
}
public static <T> void reverseStack(Stack<T> stack) {
if (stack.isEmpty()) {
return;
}
T bottom = popBottom(stack);
  
reverseStack(stack);
  
stack.push(bottom);
}
private static <T> T popBottom(Stack<T> stack) {
T top = stack.pop();
if (stack.isEmpty()) {
return top;
} else {
T bottom = popBottom(stack);
stack.push(top);
return bottom;
}
}
}

=============================================

akshay@akshay-Inspiron-3537:~/Chegg$ javac reverse.java
akshay@akshay-Inspiron-3537:~/Chegg$ java reverse
Enter elements
4
5
6
7
8
9
10
-1
Elements in reverse order
10
9
8
7
6
5
4

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.