Queues - A quick introduction with real-life example

  • Venky Karukuri
Queues - A quick introduction with real-life example

In our daily lives, we have experienced queues for various reasons such as buying tickets or getting on the bus or flight. At all these places, we have to wait for our turn to get the service.

A queue is another example of a linear list or an ordered list with data inserted at and deleted from different ends. The end at which data is inserted is called the rear, and the end at which it is deleted is called the front.

Consider a queue Q of customers standing at a ticket counter.

Q = {Laasya, Sundar, Ram, Subra, Satheesh, Srini, Robert, Jay} In the queue Q, Laasya is at the front end and Jay is at the rear end.

Queues are a popular data processing structure, frequently used in many areas of system software such as operating systems, network and database implementations. They are especially helpful for time-sharing and distributed computer systems in which multiple users access the same system at once. When a user places a request, it is added to the end of the queue of orders awaiting execution. The CPU then processes the task at the front of the line.

A queue is a first-in-first-out (FIFO) or last-in-last-out (LILO) structure that ensures that data is processed in order as it is entered.

 

Creating a queue as an abstract data type requires the use of a suitable data structure to store its elements as well as its functions. Basic queue operations include

  • adding elements
  • deleting elements, 
  • traversing the queue
  • checking whether the queue is full or empty
  • finding who is at the front and who is at the rear ends

The following are the minimal operations on a queue:

  • create()—creates an empty queue, Q
  • enqueue(i,Q)—adds the element i to the rear end of the queue and returns the resulting queue
  • dequeue(Q)—takes out an element from the front end of the queue and returns the resulting queue
  • getFront(Q)—returns the element that is at the front position of the queue
  • isEmpty(Q)—returns true if the queue is empty; otherwise returns false 

We can implement a queue using arrays or linked lists. For the former, we use static memory allocation, while for the latter, we use dynamic memory allocation.

A quick example of Queue using Java:

// Copyrights to venkys.io
// For more programs visit venkys.io
// Java program for Queue

class Node {
int data;
Node next;

Node(int data) {
this.data = data;
}
}
class Queue {
Node head;
Node tail;

void enqueue(int data) {
if (tail == null) {
Node temp = new Node(data);
tail = temp;
head = temp;
} else {
Node temp = new Node(data);
tail.next = temp;
tail = temp;

}
}

void dequeue() {
if(head!=null){
if(head==tail)tail=tail.next;
head=head.next;
}
}

void print() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
}

public class Main {
public static void main(String[] args) {
Queue q = new Queue();
q.enqueue(10);
q.enqueue(20);
q.print();
q.dequeue();
q.dequeue();
q.print();
q.enqueue(30);
q.enqueue(40);
q.enqueue(50);
q.print();
}
}