Chapter 3: Data Structures - Queue

Chapter 3: Queue Data Structure

What is Queue ? Explain.

Queue is a First In First Out (FIFO) Data structure, which means that element inserted first will also be removed first.

Element is inserted from one end called REAR (also called as tail). Element is delete from the other end called as FRONT (also called as head).

The process of adding an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.

Fig 3.1 Queue

Queue Data structure uses:

• Resource allocation(Memory, CPU, Printer) in Operating system
• Incoming call handling in Call center

Implementation of Queue

Queue data structure is implemented using Enqueue and Dequeue operations.

Steps for ENQUEUE operation

• Check if the queue is full or not.
• If the queue is full, then print overflow error and exit the program.
• If the queue is not full, then increment the tail and add the element.

Steps for DEQUEUE operation

• Check if the queue is empty or not.
• If the queue is empty, then print underflow error and exit the program.
• If the queue is not empty, then print the element at the head and increment the head.

Display elements in Queue

Steps to display elements in queue

• Check if the queue is empty or not.
• If the queue is empty, then print message “Queue is empty, cannot display”.
• If the queue is not empty, then print the element at the head and increment the head, continue till the end of the queue.

Java program to implement queue using array

public class  QDemo {
int capacity = 3;
 int arr[] = new int[capacity];
 int size = 0;
 int top = -1;
 int rear = 0;

 public void push(int pushedElement) {
  if (top < capacity - 1) {
   top++;
   arr[top] = pushedElement;
   System.out.println("Element " + pushedElement + " is pushed to Queue !");
   display();
  } else {
   System.out.println("Queue Overflown, cannot add element ");
  }
 }

 public void pop() {
  if (top >= rear) {
   rear++;
   System.out.println("Pop operation done !");
   display();
  } else {
   System.out.println("Queue Underflow, no elements in queue ");
  }
 }

 public void display() {
  if (top >= rear) {
   System.out.println("Elements in Queue : ");
   for (int i = rear; i <= top; i++) {
    System.out.println(arr[i]);
   }
  }
 }

 public static void main(String[] args) {
  QDemo QDemo = new QDemo();
  QDemo.pop();
  QDemo.push(10);
  QDemo.push(20);
  QDemo.pop();
  QDemo.pop();
}

}

<< Previous Index Next >>