Question

Queue data structure: please answer these two question properly

Q(1) What are their respective logical and physical / storage structures .Q(2) At least one application example combining data structure and algorithm should be given.

Answer 1

Answer:
1.)
logical and physical structure for Queue are mentioned below:

• Array : Queue is mostly uses Array as its underlying logical and physical storage.
• Linked List : Sometime Linked List is also used as underlying physical storage if space is constraint.

2.)
An example where queue is used is First Come First Serve OS scheduling algorithm.
The sample code using Queue as data structure and output is given below:

// Java program for array
// implementation of queue

// A class to represent a queue
class Queue {
   int front, rear, size;
   int capacity;
   int array[];

   public Queue(int cap)
   {
       this.capacity = cap;
       front = this.size = 0;
       rear = cap - 1;
       array = new int[this.capacity];
   }

   // Queue can be full when size becomes
   // equal to the capacity
   boolean isFull(Queue q)
   {
       return (q.size == q.capacity);
   }

   // Queue is empty when size is 0
   boolean isEmpty(Queue q)
   {
       return (q.size == 0);
   }

   // Method to add an item to the queue.
   // It changes rear and size
   void enqueue(int item)
   {
       if (isFull(this))
           return;
       this.rear = (this.rear + 1)
                   % this.capacity;
       this.array[this.rear] = item;
       this.size = this.size + 1;
       System.out.println(item
                       + " enqueued to process queue");
   }

   // Method to remove an item from queue.
   // It changes front and size
   int dequeue()
   {
       if (isEmpty(this))
           return Integer.MIN_VALUE;

       int item = this.array[this.front];
       this.front = (this.front + 1)
                   % this.capacity;
       this.size = this.size - 1;
       return item;
   }

   // Method to get front of queue
   int front()
   {
       if (isEmpty(this))
           return Integer.MIN_VALUE;

       return this.array[this.front];
   }

   // Method to get rear of queue
   int rear()
   {
       if (isEmpty(this))
           return Integer.MIN_VALUE;

       return this.array[this.rear];
   }
}

/**
* Driver class to execute FCFS in cpu scheduling of process
* */
public class Main {
   public static void main(String[] args)
   {
       Queue processQueue = new Queue(1000);

       processQueue.enqueue(10);
       processQueue.enqueue(20);
       processQueue.enqueue(30);
       processQueue.enqueue(40);

       System.out.println(processQueue.dequeue() + " is first process to be executed from queue\n");

       System.out.println("Front process is " + processQueue.front());

       System.out.println("Rear process is " + processQueue.rear());
   }
}

Run Debug Stop Share Save {} Beautify Language Java 6 } Main.java 1 // Java program for array 2 // implementation of queue 3 4 // A class to represent a queue 5 class Queue { int front, rear, size; 7 int capacity; 8 int array[]; 9 10 public Queue (int cap) 11 12 this.capacity cap; 13 front = this.size = 0; 14 rear = cap - 1; 15 array = new int[this.capacity]; 16 17 18 // Queue can be full when size becomes 19 // equal to the capacity 20 boolean isFull(Queue q) 21 { 22 return (q.size q.capacity); 23 24 25 // Queue is empty when size is o 26 boolean isEmpty(Queue q) 27 { 28 return (q. size 29 30 31 // Method to add an item to the queue. | 32 // It changes rear and size 33 void enqueue(int item) 34 - 35 if (isFull(this)) } == 0); }

return; this.rear = (this.rear + 1) % this.capacity; this.array[this.rear] item; this.size = this.size + 1; System.out.println(item + enqueued to process queue"); } // Method to remove an item from queue. // It changes front and size int dequeue() { if (isEmpty(this)) return Integer.MIN_VALUE; 36 File 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 int item = this.array[this.front]; this.front = (this.front + 1) % this.capacity; this.size = this.size - 1; return item; } // Method to get front of queue int front() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.array(this.front]; } // Method to get rear of queue int rear() {

} * */ 71 if (isEmpty(this)) 72 return Integer.MIN_VALUE; 73 74 return this.array[this.rear]; 75 76 } 77 78. /** 79 * Driver class to execute FCFS in cpu scheduling of process 80 81 public class Main { 82 public static void main(String[] args) 83 { 84 Queue processQueue = new Queue (1000); 85 86 processQueue.enqueue (10); 87 processQueue.enqueue (20); 88 processQueue.enqueue (30); 89 processQueue.enqueue (40); 90 91 System.out.println(processQueue.dequeue () is first process to be executed from queue\n"); 92 93 system.out.println("Front process is + processQueue. front()); 94 95 system.out.println("Rear process is + processQueue.rear()); 96 97 } 98 + }

OUTPUT=>

input 10 enqueued to process queue 20 enqueued to process queue 30 enqueued to process queue 40 enqueued to process queue 10 is first process to be executed from queue Front process is 20 Rear process is 40 ... Program finished with exit code o Press ENTER to exit console.)

(plz give me a thums up...if my answer helped you and if any suggestion plz comment, Yr thums up boost me)