Data Structures & Algorithms Notes Page

Queue ADT (Abstract Data Type)

What is it?

• A Queue is a linear data structure that follows the First-In-First-Out (FIFO) principle.
• Elements are added at the rear (enqueue) and removed from the front (dequeue).

Operations:

• enqueue(x): Add an element x to the rear of the queue
• dequeue(x): Remove and return an element at the front of the queue
• peek(): Return the element at the front of the queue WITHOUT removing it
• isEmpty(): Check if the queue is empty or not
• size(): Return the number of elements in the queue so far

Data Structures For Queues (FIFO):

• ArrayLists
• Linked Lists

Queue Implementation: Linked Lists

LinkedList list;

add(x) {list.add(x)}              // RT: O(1)
remove {list.removeFirst()}       // RT: O(1)

// In Java:
	Queue <E> q = new LinkedList<>()