Linear Structures Lesson 6

Queues and Task Processing

beginner ⏱️ 40 minutes 🌍 Printer queues, customer service lines, web server request handling, message brokers

Building on our understanding of arrays, linked lists, and stacks, we now turn our attention to another essential linear data structure: the Queue. Unlike stacks’ LIFO behavior, queues operate on a FIFO (First-In, First-Out) principle, making them ideal for managing sequential processes and task processing where order is paramount.

Queue Data Structure (FIFO)

Elements are added to the rear and removed from the front. First-In, First-Out.

⬅️ Dequeue (Remove)

FRONT

Request 1

Request 2

Request 3

REAR

Enqueue (Add) ➡️

**FIFO:** **F**irst **I**n, **F**irst **O**ut

🚦 What is a Queue?

A queue is an abstract data type (ADT) that serves as a collection of elements, with two primary operations:

Enqueue: Adds an element to the back (or “rear”) of the collection.
Dequeue: Removes the element from the front of the collection.

This behavior is known as FIFO (First-In, First-Out). Think of a line at a grocery store: the first person to get in line is the first person to be served.

Core Operations:

enqueue(element): Adds an element to the rear of the queue.
dequeue(): Removes and returns the element from the front of the queue. If the queue is empty, it typically throws an error or returns a special value.
front() (or peek()): Returns the element at the front of the queue without removing it.
isEmpty(): Checks if the queue contains any elements.
size(): Returns the number of elements in the queue.

Analogy: A customer service line, a car wash, or a print job spool. The first one in gets processed first.

💻 Implementing a Queue

Queues can be implemented using either dynamic arrays or linked lists. The choice depends on performance considerations for enqueue and dequeue.

Using a Dynamic Array (List)

Implementing a queue with a dynamic array requires careful consideration to maintain O(1) for both enqueue and dequeue.

Challenge: If you enqueue (append) to the end and dequeue (remove) from the beginning of a dynamic array, dequeue would be O(N) due to shifting elements.

Solution: A common strategy is to use a “circular array” or a deque (double-ended queue) implementation where you keep track of both front and rear pointers, allowing both operations to be O(1). Or, if using a language like Python/JavaScript, if removing from the front is truly needed, accept the O(N) cost or use a more specialized structure. For simplicity, let’s show an array-based one with notes on complexity.

Queue Implementation (Dynamic Array - simple approach)


        
          
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int *data;
  int front;    // Index of the front element
  int rear;     // Index of the rear element
  int size;     // Current number of elements
  int capacity; // Current allocated capacity
} ArrayQueue;

// Initialize queue
void init_array_queue(ArrayQueue *q, int initialCapacity) {
  q->data = (int *) malloc(sizeof(int) * initialCapacity);
  if (q->data == NULL) { /* Handle error */ exit(EXIT_FAILURE); }
  q->front = 0;
  q->rear = -1; // Indicate empty queue
  q->size = 0;
  q->capacity = initialCapacity;
}

// Check if queue is empty
int is_empty_array_queue(ArrayQueue *q) {
  return q->size == 0;
}

// Enqueue an element (O(1) amortized, with resizing)
void enqueue_array_queue(ArrayQueue *q, int item) {
  if (q->size == q->capacity) { // Queue is full, resize
      q->capacity *= 2;
      q->data = (int *) realloc(q->data, sizeof(int) * q->capacity);
      if (q->data == NULL) { /* Handle error */ exit(EXIT_FAILURE); }
      printf("Queue resized to capacity: %d\n", q->capacity);
  }
  q->rear = (q->rear + 1); // Move rear pointer
  q->data[q->rear] = item;
  q->size++;
}

// Dequeue an element (O(N) if shifting, O(1) with circular buffer)
// This simple implementation *does not* re-shift, so front just advances.
// Effectively, this becomes a sparse array over time.
int dequeue_array_queue(ArrayQueue *q) {
  if (is_empty_array_queue(q)) {
      printf("Error: Queue is empty!\n");
      exit(EXIT_FAILURE);
  }
  int item = q->data[q->front];
  q->front++; // Just advance front pointer
  q->size--;
  // In a real circular array, front and rear wrap around, and
  // when front overtakes rear, you handle shrink or reset.
  return item;
}

// Peek at the front element (O(1))
int front_array_queue(ArrayQueue *q) {
  if (is_empty_array_queue(q)) {
      printf("Error: Queue is empty for front!\n");
      exit(EXIT_FAILURE);
  }
  return q->data[q->front];
}

// Cleanup
void free_array_queue(ArrayQueue *q) {
  free(q->data);
  q->data = NULL;
  q->front = 0;
  q->rear = -1;
  q->size = 0;
  q->capacity = 0;
}

int main() {
  ArrayQueue q;
  init_array_queue(&q, 2);

  enqueue_array_queue(&q, 10); // [10]
  enqueue_array_queue(&q, 20); // [10, 20]
  printf("Front: %d\n", front_array_queue(&q)); // 10
  enqueue_array_queue(&q, 30); // [10, 20, 30] (resizes)

  printf("Dequeued: %d\n", dequeue_array_queue(&q)); // 10
  printf("Dequeued: %d\n", dequeue_array_queue(&q)); // 20
  printf("Is Empty: %d\n", is_empty_array_queue(&q)); // 0 (false)
  printf("Dequeued: %d\n", dequeue_array_queue(&q)); // 30
  printf("Is Empty: %d\n", is_empty_array_queue(&q)); // 1 (true)

  free_array_queue(&q);
  return 0;
}


        
          
# Python's built-in list can simulate a queue but dequeueing from the start
# (list.pop(0)) is O(N). For efficient queues, use collections.deque.

from collections import deque

class Queue:
  def __init__(self):
      self._items = deque() # Use a deque for efficient queue operations

  def is_empty(self):
      return len(self._items) == 0

  def enqueue(self, item):
      self._items.append(item) # O(1)

  def dequeue(self):
      if self.is_empty():
          raise IndexError("dequeue from empty queue")
      return self._items.popleft() # O(1) (efficiently remove from left)

  def front(self):
      if self.is_empty():
          raise IndexError("front from empty queue")
      return self._items[0] # O(1)

  def size(self):
      return len(self._items)

# Main for demonstration
q = Queue()
q.enqueue(10) # [10]
q.enqueue(20) # [10, 20]
print(f"Front: {q.front()}") # 10
q.enqueue(30) # [10, 20, 30]

print(f"Dequeued: {q.dequeue()}") # 10
print(f"Dequeued: {q.dequeue()}") # 20
print(f"Is Empty: {q.is_empty()}") # False
print(f"Dequeued: {q.dequeue()}") # 30
print(f"Is Empty: {q.is_empty()}") # True


        
          
// JavaScript arrays can simulate a queue.
// Using push() for enqueue and shift() for dequeue.
// Note: Array.prototype.shift() is O(N) because it re-indexes all elements.
// For true O(1) queue behavior, you might need a linked list or custom implementation.

class Queue {
  constructor() {
      this._items = [];
  }

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

  enqueue(item) {
      this._items.push(item); // O(1) amortized
  }

  dequeue() {
      if (this.isEmpty()) {
          throw new Error("dequeue from empty queue");
      }
      return this._items.shift(); // O(N) - careful with performance!
  }

  front() {
      if (this.isEmpty()) {
          throw new Error("front from empty queue");
      }
      return this._items[0]; // O(1)
  }

  size() {
      return this._items.length;
  }
}

// Main for demonstration
const q = new Queue();
q.enqueue(10); // [10]
q.enqueue(20); // [10, 20]
console.log("Front:", q.front()); // 10
q.enqueue(30); // [10, 20, 30]

console.log("Dequeued:", q.dequeue()); // 10
console.log("Dequeued:", q.dequeue()); // 20
console.log("Is Empty:", q.isEmpty()); // false
console.log("Dequeued:", q.dequeue()); // 30
console.log("Is Empty:", q.isEmpty()); // true

Complexity (Queue Operations using Dynamic Array):

Enqueue: O(1) (amortized) - Appending to the end of a dynamic array is efficient.
Dequeue: O(N) in naive array implementations (like Array.shift() in JS) because all subsequent elements must be shifted. However, with a circular array or a specialized deque (like Python’s collections.deque), dequeue can be O(1).
Front: O(1)
isEmpty: O(1)
Space Complexity: O(N) for storing N elements.

Using a Linked List

A linked list provides an elegant and efficient way to implement a queue, ensuring all primary operations are O(1).

Implementation Strategy:

Maintain head (front) and tail (rear) pointers.
Enqueue: Add to the tail (O(1)).
Dequeue: Remove from the head (O(1)).

Queue Implementation (Linked List)


        
          
#include <stdio.h>
#include <stdlib.h>

typedef struct QNode {
  int data;
  struct QNode* next;
} QNode;

typedef struct Queue {
  QNode *front; // Pointer to front of queue
  QNode *rear;  // Pointer to rear of queue
} Queue;

// Create a new node
QNode* new_qnode(int k) {
  QNode* temp = (QNode*) malloc(sizeof(QNode));
  if (temp == NULL) { /* Handle error */ exit(EXIT_FAILURE); }
  temp->data = k;
  temp->next = NULL;
  return temp;
}

// Create an empty queue
Queue* create_queue() {
  Queue* q = (Queue*) malloc(sizeof(Queue));
  if (q == NULL) { /* Handle error */ exit(EXIT_FAILURE); }
  q->front = q->rear = NULL;
  return q;
}

// Add an item to the queue (enqueue)
void enqueue(Queue* q, int k) {
  QNode* temp = new_qnode(k);

  if (q->rear == NULL) { // If queue is empty
      q->front = q->rear = temp;
      return;
  }

  q->rear->next = temp; // Link new node at rear
  q->rear = temp;       // Move rear to new node
}

// Remove an item from queue (dequeue)
int dequeue(Queue* q) {
  if (q->front == NULL) { // If queue is empty
      printf("Error: Dequeue from empty queue!\n");
      exit(EXIT_FAILURE);
  }

  QNode* temp = q->front; // Store previous front
  int data = temp->data;
  q->front = q->front->next; // Move front pointer

  if (q->front == NULL) { // If front becomes NULL, then queue became empty
      q->rear = NULL;
  }
  free(temp); // Free old front node
  return data;
}

// Get front element
int front_queue(Queue* q) {
  if (q->front == NULL) {
      printf("Error: Front from empty queue!\n");
      exit(EXIT_FAILURE);
  }
  return q->front->data;
}

// Check if empty
int is_empty_queue(Queue* q) {
  return q->front == NULL;
}

// Cleanup
void free_queue(Queue* q) {
  QNode* current = q->front;
  while (current != NULL) {
      QNode* next = current->next;
      free(current);
      current = next;
  }
  free(q);
}

int main() {
  Queue* q = create_queue();

  enqueue(q, 10);
  enqueue(q, 20);
  printf("Front: %d\n", front_queue(q)); // 10
  enqueue(q, 30);

  printf("Dequeued: %d\n", dequeue(q)); // 10
  printf("Dequeued: %d\n", dequeue(q)); // 20
  printf("Is Empty: %d\n", is_empty_queue(q)); // 0 (false)
  printf("Dequeued: %d\n", dequeue(q)); // 30
  printf("Is Empty: %d\n", is_empty_queue(q)); // 1 (true)

  free_queue(q);
  return 0;
}


        
          
class QNode:
  def __init__(self, data):
      self.data = data
      self.next = None

class LinkedListQueue:
  def __init__(self):
      self.front = None
      self.rear = None
      self._size = 0

  def is_empty(self):
      return self.front is None

  def enqueue(self, item):
      new_node = QNode(item)
      if self.is_empty():
          self.front = self.rear = new_node
      else:
          self.rear.next = new_node
          self.rear = new_node
      self._size += 1

  def dequeue(self):
      if self.is_empty():
          raise IndexError("dequeue from empty queue")
      
      removed_data = self.front.data
      self.front = self.front.next
      
      if self.front is None: # If list becomes empty after dequeue
          self.rear = None
      self._size -= 1
      return removed_data

  def front_item(self):
      if self.is_empty():
          raise IndexError("front from empty queue")
      return self.front.data

  def size(self):
      return self._size

# Main for demonstration
q = LinkedListQueue()
q.enqueue(10)
q.enqueue(20)
print(f"Front: {q.front_item()}") # 10
q.enqueue(30)

print(f"Dequeued: {q.dequeue()}") # 10
print(f"Dequeued: {q.dequeue()}") # 20
print(f"Is Empty: {q.is_empty()}") # False
print(f"Dequeued: {q.dequeue()}") # 30
print(f"Is Empty: {q.is_empty()}") # True


        
          
class QNode {
  constructor(data) {
      this.data = data;
      this.next = null;
  }
}

class LinkedListQueue {
  constructor() {
      this.front = null;
      this.rear = null;
      this.size = 0;
  }

  isEmpty() {
      return this.front === null;
  }

  enqueue(item) {
      const newNode = new QNode(item);
      if (this.isEmpty()) {
          this.front = this.rear = newNode;
      } else {
          this.rear.next = newNode;
          this.rear = newNode;
      }
      this.size++;
  }

  dequeue() {
      if (this.isEmpty()) {
          throw new Error("dequeue from empty queue");
      }
      const removedData = this.front.data;
      this.front = this.front.next;

      if (this.front === null) { // If list becomes empty
          this.rear = null;
      }
      this.size--;
      return removedData;
  }

  frontItem() {
      if (this.isEmpty()) {
          throw new Error("front from empty queue");
      }
      return this.front.data;
  }
}

// Main for demonstration
const q = new LinkedListQueue();
q.enqueue(10);
q.enqueue(20);
console.log("Front:", q.frontItem()); // 10
q.enqueue(30);

console.log("Dequeued:", q.dequeue()); // 10
console.log("Dequeued:", q.dequeue()); // 20
console.log("Is Empty:", q.isEmpty()); // false
console.log("Dequeued:", q.dequeue()); // 30
console.log("Is Empty:", q.isEmpty()); // true

Complexity (Queue Operations using Linked List):

Enqueue: O(1)
Dequeue: O(1)
Front: O(1)
isEmpty: O(1)
Space Complexity: O(N) for storing N elements.

🚀 Queues in Task Processing

Queues are fundamental in scenarios where tasks need to be processed in the order they arrive, ensuring fairness and preventing system overload.

Common Applications:

Printer Queues: Documents are printed in the order they are sent.
Web Servers: Incoming client requests are often put into a queue to be processed by available server threads.
Operating Systems: Task scheduling, I/O requests (e.g., disk operations) often use queues.
Message Queues/Brokers: Systems like RabbitMQ, Kafka, or AWS SQS use queues to pass messages between different parts of an application, decoupling components and handling asynchronous processing.
Buffering: Temporary storage of data that arrives faster than it can be processed.
Breadth-First Search (BFS): An algorithm used to traverse or search tree or graph data structures.

⚖️ Stacks vs. Queues

Feature	Stack	Queue
Principle	LIFO (Last-In, First-Out)	FIFO (First-In, First-Out)
Primary Ops	`push`, `pop` (top)	`enqueue` (rear), `dequeue` (front)
Analogy	Stack of plates, browser undo history	Waiting line, printer queue
Common Impl	Dynamic array (end), Linked List (head)	Linked List (head/tail), Circular Array
Use Case	Function call management, recursion, undo	Task scheduling, request buffering, BFS

Note: While both are linear data structures, their restricted access patterns make them uniquely suited for different problems. Stacks are about “what’s next for me right now?”, while queues are about “who’s turn is it?”.