Step 1 of 5

20% Complete

Introduction to Queues

Learn what queues are and the FIFO principle

What is a Queue?

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue is the first one to be removed. Think of a queue like a line of people waiting for a service — the person who arrives first gets served first.

Front (Dequeue from here)Rear (Enqueue here)

In the visualization above, you can see a simple queue with four elements. The front of the queue is on the left, and the rear is on the right. When we add a new element (enqueue), it goes to the rear. When we remove an element (dequeue), it comes from the front.

The FIFO Principle

The defining characteristic of a queue is its FIFO (First-In-First-Out) behavior. This means:

The first element added to the queue will be the first element removed.
Elements can only be added to the rear and removed from the front of the queue.
Access to other elements in the queue is restricted — you can't access elements in the middle without first removing the elements at the front.

Real-world Queue Examples:

People waiting in line at a checkout counter
Print jobs sent to a printer
Requests to a web server
Processes waiting for CPU time in an operating system
Messages in a message broker system

Basic Queue Operations

Enqueue: Add an element to the rear of the queue.
Dequeue: Remove and return the element at the front of the queue.
Peek/Front: View the element at the front without removing it.
isEmpty: Check if the queue is empty.
Size: Get the number of elements in the queue.

Queue Implementation Overview

There are several ways to implement a queue:

Array-based Implementation

Uses an array to store elements. The front is at the beginning of the array, and the rear is at the end.

Simple to implement
Fixed size (in some languages)
Inefficient dequeue operation (O(n))

Circular Queue Implementation

Uses an array with front and rear pointers that wrap around to the beginning when they reach the end.

Efficient operations (O(1))
Better space utilization
More complex implementation

Linked List-based Implementation

Uses a linked list where the head represents the front and the tail represents the rear.

Dynamic size
Efficient operations (O(1))
More memory overhead

Double-ended Queue (Deque)

A queue that allows insertion and deletion at both ends.

More versatile
Can be used as both stack and queue
More complex implementation

In this tutorial, we'll focus on the array-based and linked list-based implementations as they're commonly used.

Basic Queue Class Structure

class Queue {
  constructor() {
    this.items = [];  // Initialize empty array to store elements
  }
 
  // Core operations will be implemented in the following sections
  enqueue(element) { /* Add element to the rear */ }
  dequeue() { /* Remove and return the front element */ }
  peek() { /* Return the front element without removing it */ }
  
  // Utility methods
  isEmpty() {
    return this.items.length === 0;
  }
  
  size() {
    return this.items.length;
  }
}

Advantages and Disadvantages

Advantages

Simple and intuitive concept
Preserves the order of elements
Useful for managing resources and scheduling
Efficient for FIFO access patterns

Disadvantages

Limited access (can only access the front element)
Simple array implementations have O(n) dequeue operations
No random access to elements
Searching requires emptying the queue

Queue vs. Stack

Queues and stacks are both linear data structures, but they differ in how elements are accessed:

Queue (FIFO)

First element in is the first element out
Elements are added at the rear and removed from the front
Like a line of people waiting
Used for breadth-first search, scheduling, etc.

Stack (LIFO)

Last element in is the first element out
Elements are added and removed from the same end (top)
Like a stack of plates
Used for depth-first search, undo operations, etc.

Check Your Understanding

Next Steps

Now that you understand what queues are and their basic principles, let's move on to implementing the core operations of a queue, starting with the enqueue operation.