Wednesday, 11 December 2013

QUEUE DATA STRUCTURE


QUEUE:
Queue is a linear list of elements in which insertion takes place at REAR end and deletions can takes place from FRONT end .QUEUE is also called as FIFO (FIRST IN FIRST OUT) Data Structure.
A common example:  QUEUE at Bank is the best example, where every person enters in to the QUEUE from rear end and after payment/deposit exits from the front end.
INSERTION operation: The insertion operation on the QUEUE is done from the rear end.
DELETION operation: The deletion operation is done from the front end.
Initially when the QUEUE is empty then, front=0, rear=0 and count=0.
When we insert elements in to the Queue then
               a[rear] = item;
                rear++;
                count++;
When we want to delete elements from the Queue then
        if(count != 0){  
          a[front];
           front++;
           count--;
          }

Different types of QUEUE’s are
1)      Linear Queue: Normal First In First Out QUEUE  is known as Linear Queue.
2)      Circular Queue: In this, we can use free space efficiently. In circular Queue the gap between rear and front is equal to two.
3)      Priority Queue: In this type elements are processed as per the priority, it doesn’t follow FIFO order.
4)      DE-Queue (Double Ended Queue): In this, we can insert and delete elements from the both ends known as doubly Ended Queue. It is categorized in to two types. They are
i)                    Input Restricted Queue: Append can be done from one side only and serving can be done from both sides.
ii)                   Output Restricted Queue:  Append can be done from the both sides and serving can be done from one side only.



QUEUE PROGRAM:
import java.io.DataInputStream;
class DemoQueue {
    DataInputStream dis = new DataInputStream(System.in);
    int a[];
    int i, front = 0, rear = 0, n, item, count = 0;

    void getData() {
        try {
            System.out.println("Enter the limit: ");
            n = Integer.parseInt(dis.readLine());
            a = new int[n];
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
    }

    void enQueue() {
        try {
            if (count < n) {
                System.out.println("Enter the element to be added: ");
                item = Integer.parseInt(dis.readLine());
                a[rear] = item;
                rear++;
                count++;
            } else {
                System.out.println("QUEUE IS FULL");
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    void deQueue() {
       if(count != 0){
           System.out.println("The item selected is: " + a[front]);
           front++;
           count--;
       }else{
           System.out.println("QUEUE IS EMPTY");
           if(rear == n)
               rear = 0;
       }
    }

    void display() {
        int m = 0;
        if (count == 0) {
            System.out.println("QUEUE IS EMPTY");
        } else {
            for (i = front; m < count; i++, m++) {
                System.out.println(" " + a[i % n]);
            }
        }
    }
}

public class UsingQueue {
    static public void main(String args[]) {
        DataInputStream dis = new DataInputStream(System.in);
        int ch;
        DemoQueue obj = new DemoQueue();
        obj.getData();
        try {
            do {
                System.out.println("1.ENQUE" + "\n" + "2.DEQUEUE" + "\n" + "3.DISPLAY" + "\n" + "4.EXIT");
                System.out.println("Enter your choice");
                ch = Integer.parseInt(dis.readLine());
                switch (ch) {
                    case 1:
                        obj.enQueue();
                        break;

                    case 2:
                        obj.deQueue();
                        break;
                    case 3:
                        obj.display();
                    case 4:
                        break;
                    default:
                        System.out.println("invalid choice...");
                }
            } while (ch != 4);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

No comments:

Post a Comment

java binary tree program for inorder, preorder, postorder

import java.util.Queue; import java.util.LinkedList; public class TreeTraverse { private static class Node<T> { public Node<T> ...