Engineering Fluency OS

Why This Matters

When you send a document to a printer, it enters a queue. The first document sent is the first one printed. This First-In-First-Out principle is how fairness works in computing: tasks are processed in the order they arrive.

Queues are fundamental to operating systems (process scheduling), networking (packet delivery), web servers (request handling), and algorithms like breadth-first search. Where stacks track the most recent item, queues track the oldest item. Together, stacks and queues are the two essential linear data structures that power state management in every layer of software.

Define Terms

Visual Model

enqueue()add to back

Afront

Dback

dequeue()remove from front

The full process at a glance. Click Start tour to walk through each step.

A queue: First In, First Out (FIFO). Enqueue at the back, dequeue from the front. Both O(1).

Code Example

Code

// Queue implementation using an array
class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(value) {
    this.items.push(value);
  }

  dequeue() {
    if (this.isEmpty()) throw new Error("Queue underflow");
    return this.items.shift();
  }

  front() {
    if (this.isEmpty()) throw new Error("Queue is empty");
    return this.items[0];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  get size() {
    return this.items.length;
  }
}

// Basic queue usage
const q = new Queue();
q.enqueue("Task A");
q.enqueue("Task B");
q.enqueue("Task C");
console.log(q.front());    // "Task A"
console.log(q.dequeue());  // "Task A"
console.log(q.dequeue());  // "Task B"
console.log(q.size);       // 1

// Practical example: recent counter
// Counts how many requests occurred in the last 3000ms
class RecentCounter {
  constructor() {
    this.queue = new Queue();
  }

  ping(timestamp) {
    this.queue.enqueue(timestamp);
    while (this.queue.front() < timestamp - 3000) {
      this.queue.dequeue();
    }
    return this.queue.size;
  }
}

const counter = new RecentCounter();
console.log(counter.ping(1));      // 1
console.log(counter.ping(100));    // 2
console.log(counter.ping(3001));   // 3
console.log(counter.ping(3002));   // 3

Interactive Experiment

Try these exercises:

Create a queue, enqueue 5 items, then dequeue them all. Confirm they come out in order.
Compare queue vs stack: push A, B, C onto a stack and enqueue A, B, C into a queue. Pop/dequeue all and observe the different orderings.
Simulate a print queue: enqueue 3 "documents", then process them one at a time.
What happens if you dequeue from an empty queue?
Modify the recent counter to use a 5000ms window instead of 3000ms.

Quick Quiz

Coding Challenge

Recent Counter

Implement a `RecentCounter` class that counts the number of recent requests within a time window. It has one method: `ping(timestamp)` which adds a new request at the given timestamp (in milliseconds) and returns the number of requests that occurred in the past 3000 milliseconds (including the new request). Timestamps are strictly increasing.

Loading editor...

Real-World Usage

Queues are critical infrastructure in production systems:

Task queues: Background job processors (Celery, Bull, SQS) use queues to schedule work and guarantee order.
Print queues: Documents are printed in the order they were submitted.
Web servers: Incoming HTTP requests are queued and processed by worker threads in arrival order.
Breadth-first search: BFS algorithms use a queue to explore nodes level by level in graphs and trees.
Message brokers: Systems like RabbitMQ and Kafka deliver messages to consumers in FIFO order for reliable event processing.

Queues