Queues

What are Queues ?

A Queue is a data structure that enables us to create an array of elements and manage its data in First-In-First-Out (FIFO) logic.

First In First Out

First in first out as we talked above is simply the way how a queue behaves. It's okay to say that every queue behaves this way. As an example, you rush to the highway in your car and sees a long queue before the tollbooth. You are the last to join and the first to join now passes the gate, then it should be the second to first and the third and so on. So just like that we can apply this in our programmings.

In programming there are plenty of scenarios we use queue data structure.

- Priority Scheduling

CPU bound tasks are scheduled. To process them efficiently priority scheduling is used. Uses fifo conecpt.

- Shortest Path Algorithm (Dijkstra)

To optimize the algorithm of shortest path, uses priority scheduling which uses queues.

Types of Queues

There are 2 main types of queues differencing from their concepts
They are Normal Queues and Circular Queues.

The following variables are used by a queue class.
size front items rear queue

private int size, front, items, rear;
private int[] queue;

// queue -> queue as an array
// size  -> initial length of queue
// front -> current first item's index
// items -> current length of queue
// rear  -> current last item's index

The followings implements a queue.

0. Queue

Queue parameterized constructor
Initializes a new queue with 'size' as parameter

public Queue(int size) {
   this.size = size;
   this.front = 0;
   this.rear = -1;
   this.items = 0;
   this.queue = new int[size];
   System.out.println("Queue Initialized!");
}

// queue array size is given as parameter
// first item's index = 0. because queue not served yet
// last item does not exist yet. so rear = -1
// current items = 0. currently queue is empty
// queue is initialized

1. Insert

Inserts an item to the queue

public void insert(int x) {
   if (rear == size - 1) {
      System.out.println("Queue Already Full!");
   }
   else {
      rear++;
      queue[rear] = x;
      items++;
      System.out.println(x + " Inserted to queue");
   }
}

// first checks if queue is full
// if queue is not full
// last item's index (rear) is increased
// items count also increases
// front = 0, rear = 0, items = 1

// let's add another item
// front = 0, rear = 1, items = 2
// our queue has two items now

// what if 
// if the last item's index has reached to
// possibly the queue's last index? (queue is full)
// i.e. - let's say queue is with size of 5 
// and we inserted 5 items
// inserted items' indexes -> 0 1 2 3 4
// front = 0, rear = 4, items = 5
// because rear equals (size - 1) equals 4
// so queue is full and cannot insert more

2. Peek

Prints the current first item in the queue

public void peek() {
   if (items == 0) {
      System.out.println("Queue is Empty!");
   }
   else {
      int frontItem = queue[front];
      System.out.println(frontItem + " is in front of queue");
   }
}

3. Delete

Deletes an item from the queue

public void delete() {
   if (items == 0) {
      System.out.println("Queue is Empty!");
   }
   else {
      int frontItem = queue[front];
      front++;
      items--;
      System.out.println(frontItem + " Deleted from queue");
   }
}

// first checks if items == 0 (if so queue is empty)
// if queue is empty cannot delete items from queue
// if it is not then take the first item with front as index
// the first item's index moves to the second item's index 
// total items count reduces by one also
// now second item is the first item

There are similarities between highway tollbooth example and this.
You join to the tollbooth queue -> insert method
You see the first vehicle in the queue -> peek method
First vehicle passes the gate with ticket -> delete method

The queue code sample explained above uses integers as its data type.
Source code is available in following url.

https://github.com/lizardkingLK/Queues

Blog

sndp