What is an Abstract Data Type?

An abstract data type (ADT) defines the behavior of a data structure—what operations it supports and how they behave—but it doesn’t define how it’s implemented.

For example, a Queue ADT can be implemented using:

• Arrays
• Linked Lists
• Stacks (using two stacks to form a queue)
• Heaps

So think of ADT as a blueprint or a contract that can be implemented in multiple ways.

What is a Queue?

A Queue is a linear data structure that follows the FIFO (First In, First Out) principle.

ATM Analogy:

• The first person to arrive is the first one served.
• Everyone else must wait in line until it’s their turn.

This concept maps perfectly to how a queue operates.

FIFO Explained:

• First item inserted → First item removed
• Example:
  • Enqueue: 10 → 6 → 18 → 1 → 56
  • Dequeue order: 10 → 6 → 18 → 1 → 56

Basic Operations on a Queue

Operation	Description
enqueue()	Adds (inserts) an item to the back of the queue
dequeue()	Removes the item from the front of the queue
peek() / front()	Returns the front item without removing it

dequeue() removes the element, but peek() just reads it.

Queue Use Case Example

Let’s walk through a simple example:

Initial State:

Queue is empty.

Sequence of enqueue():

enqueue(10) → Queue: [10]
enqueue(6)  → Queue: [10, 6]
enqueue(18) → Queue: [10, 6, 18]
enqueue(1)  → Queue: [10, 6, 18, 1]
enqueue(56) → Queue: [10, 6, 18, 1, 56]

Now perform dequeue():

dequeue() → 10 → Queue: [6, 18, 1, 56]
dequeue() → 6  → Queue: [18, 1, 56]
dequeue() → 18 → Queue: [1, 56]
dequeue() → 1  → Queue: [56]
dequeue() → 56 → Queue: []

At every point, only the first item inserted is accessible. You can’t jump to the middle or end of the queue.

Internal Implementation

A queue can be implemented using:

• Arrays (fixed size, may require resizing)
• Linked Lists (dynamic size, efficient enqueue and dequeue)
• Two Stacks (to simulate queue behavior)

Real-Life Applications of Queues

1. Operating Systems

• Thread Scheduling: OS schedules threads using a queue to manage task execution.
• CPU Scheduling: Tasks (processes) are put in a queue, and the CPU handles them one at a time.

2. Smartphone Apps

Imagine using your smartphone:

• Tapping the screen
• Opening multiple apps
• Downloading files
• Getting notifications

All of these actions generate tasks, and the OS needs to handle them one by one.

The queue stores:

• Touch events
• Network requests
• UI updates
• API call responses

The CPU processes them in order, ensuring a smooth user experience.

Implementation in Java

Node.java

package Queue;

public class Node<T extends Comparable<T>> {

	private T data;
	private Node<T> nextNode;

	public Node(T data) {
		this.data = data;
	}

	public T getData() {
		return data;
	}

	public void setData(T data) {
		this.data = data;
	}

	public Node<T> getNextNode() {
		return nextNode;
	}

	public void setNextNode(Node<T> nextNode) {
		this.nextNode = nextNode;
	}

	@Override
	public String toString() {
		return this.data.toString();
	}
}

Queue.java

package Queue;

public class Queue<T extends Comparable<T>> {

	private Node<T> firstNode;
	private Node<T> lastNode;
	private int count;
	
	public boolean isEmpty(){
		return this.firstNode == null;
	}
	
	public int size(){
		return this.count;
	}
	
	// O(1)
	public void enqueue(T newData){
		
		this.count++;
		
		Node<T> oldLastNode = this.lastNode;
		this.lastNode = new Node<>(newData);
		this.lastNode.setNextNode(null);
		
		if( isEmpty() ){
			this.firstNode = this.lastNode;
		}else{
			oldLastNode.setNextNode(this.lastNode);
		}
		
	}
	
	// O(1)
	public T dequeue(){
		
		this.count--;
		
		T dataToDequeue = this.firstNode.getData();
		this.firstNode=this.firstNode.getNextNode();
		
		if( isEmpty() ){
			this.lastNode = null;
		}
		
		return dataToDequeue;
	}
}

App.java

package Queue;

public class App {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		Queue<Integer> queue = new Queue<Integer>();
		
		queue.enqueue(10);
		queue.enqueue(20);
		queue.enqueue(30);
		
		System.out.println(queue.dequeue());
		
		System.out.println(queue.size());

	}

}