Understanding Queues: How to Build Custom Queues in Pseudocode

· 7 min read

Hey everyone, it’s alanturrr1703 back again! 😄 Today, we’re exploring another essential data structure that plays a crucial role in a wide range of applications: the Queue. Queues are everywhere in computer science and are particularly useful when we need to maintain the order of elements, such as in task scheduling, buffering, or handling requests.

In this blog, we’ll cover what a queue is, the types of queues, and how to implement operations like enqueue, dequeue, and peek using pseudocode. We’ll also discuss both array-based and linked-list-based implementations. Let’s dive in! 🚀

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 will be the first one to be removed. Think of it like a line of people waiting for service—whoever gets in line first is served first.

Basic Operations:

  • Enqueue: Add an element to the end of the queue.
  • Dequeue: Remove the element from the front of the queue.
  • Peek (Front): Look at the front element without removing it.
  • isEmpty: Check if the queue is empty.

Key Features:

  • FIFO: First In, First Out.
  • Sequential Access: You can only access the front or rear elements.
  • Dynamic Size: The queue can grow or shrink as needed, depending on the implementation.

Applications of Queues:

  • Task Scheduling: In operating systems, queues manage tasks or processes to be executed.
  • Buffering: Queues are used to store data that’s waiting to be processed, such as when streaming videos or handling network packets.
  • Breadth-First Search (BFS): Queues are used in graph traversal algorithms like BFS.
  • Print Queue: A print queue manages documents waiting to be printed in the order they were received.

Types of Queue Implementations

Queues can be implemented in two main ways:

  1. Array-based implementation
  2. Linked-list-based implementation

Let’s look at how to implement queues using these methods, complete with pseudocode for each operation.

Array-Based Queue Implementation

In an array-based implementation, we use an array to store queue elements. The front of the queue is at the beginning of the array, and the rear is at the end of the array.

(a) Initialize Queue

Function InitializeQueue(size):
    Create an array of size 'size'
    Set front = -1
    Set rear = -1

(b) Enqueue Operation

Function Enqueue(queue, rear, size, data):
    If rear == size - 1:
        Print "Queue Overflow"
        Return
    If front == -1:
        front = 0  # Initialize front on the first enqueue
    rear = rear + 1
    queue[rear] = data

(c) Dequeue Operation

Function Dequeue(queue, front, rear):
    If front == -1 or front > rear:
        Print "Queue Underflow"
        Return NULL
    data = queue[front]
    front = front + 1
    If front > rear:  # Reset the queue when it's empty
        front = -1
        rear = -1
    Return data

(d) Peek Operation

Function Peek(queue, front):
    If front == -1:
        Print "Queue is empty"
        Return NULL
    Return queue[front]

(e) isEmpty Operation

Function isEmpty(front):
    Return front == -1

Array-Based Example:

Queue = [1, 2, 3]  # Front element is 1
front = 0
rear = 2

In the array-based implementation, we need to watch out for queue overflow (when the queue is full) and queue underflow (when we try to dequeue from an empty queue). Additionally, with a simple array, the queue size is fixed.

Circular Queue Implementation

A circular queue solves the issue of wasting space in a standard array-based queue by making the queue wrap around. In a circular queue, when the rear reaches the end of the array, it can wrap around to the beginning of the array (if there’s free space).

(a) Enqueue Operation in Circular Queue

Function EnqueueCircular(queue, front, rear, size, data):
    nextRear = (rear + 1) % size
    If nextRear == front:
        Print "Queue Overflow"
        Return
    rear = nextRear
    queue[rear] = data

(b) Dequeue Operation in Circular Queue

Function DequeueCircular(queue, front, rear, size):
    If front == -1:
        Print "Queue Underflow"
        Return NULL
    data = queue[front]
    front = (front + 1) % size
    If front == (rear + 1) % size:  # Reset the queue when it's empty
        front = -1
        rear = -1
    Return data

In a circular queue, we efficiently use the space available in the array by making the queue wrap around when it reaches the end.

Linked-List-Based Queue Implementation

In the linked-list-based implementation, the queue is dynamic in size. Each element is represented as a node with two fields: data and a pointer to the next node. The front pointer points to the front of the queue, and the rear pointer points to the end.

Node Structure

Structure Node:
    data
    next

(a) Initialize Queue

Function InitializeQueue():
    Set front = NULL
    Set rear = NULL

(b) Enqueue Operation

Function Enqueue(front, rear, data):
    Create newNode with data
    If rear is NULL:
        front = newNode
        rear = newNode
    Else:
        rear.next = newNode
        rear = newNode
    Return front, rear

(c) Dequeue Operation

Function Dequeue(front, rear):
    If front is NULL:
        Print "Queue Underflow"
        Return NULL
    data = front.data
    front = front.next
    If front is NULL:
        rear = NULL  # Reset rear if the queue is empty
    Return data, front, rear

(d) Peek Operation

Function Peek(front):
    If front is NULL:
        Print "Queue is empty"
        Return NULL
    Return front.data

(e) isEmpty Operation

Function isEmpty(front):
    Return front == NULL

Linked-List-Based Example:

Let’s visualize the queue as a linked list:

front → [data: 1, next: → [data: 2, next: → [data: 3, next: NULL]]] ← rear

Here, the front element is 1 and the rear element is 3.

Double-Ended Queue (Deque)

A deque (double-ended queue) is a more generalized form of a queue that allows insertion and deletion from both ends—front and rear.

(a) Insert at Front (Deque)

Function InsertAtFront(deque, front, rear, data):
    Create newNode with data
    If front is NULL:
        front = newNode
        rear = newNode
    Else:
        newNode.next = front
        front = newNode
    Return front, rear

(b) Insert at Rear (Deque)

Function InsertAtRear(deque, front, rear, data):
    Create newNode with data
    If rear is NULL:
        front = newNode
        rear = newNode
    Else:
        rear.next = newNode
        rear = newNode
    Return front, rear

(c) Delete from Front (Deque)

Function DeleteAtFront(deque, front, rear):
    If front is NULL:
        Print "Deque Underflow"
        Return NULL
    data = front.data
    front = front.next
    If front is NULL:
        rear = NULL
    Return data, front, rear

(d) Delete from Rear (Deque)

Function DeleteAtRear(deque, front, rear):
    If rear is NULL:
        Print "Deque Underflow"
        Return NULL
    If front == rear:
        data = rear.data
        front = NULL
        rear = NULL
        Return data, front, rear
    Set current = front
    While current.next != rear:
        current = current.next
    data = rear.data
    rear = current
    rear.next = NULL
    Return data, front, rear

A deque is useful when you need to efficiently insert and delete elements from both ends of the queue.

Queue Operations and Time Complexity

  • **

Enqueue**: O(1) – We add an element at the rear.

  • Dequeue: O(1) – We remove an element from the front.
  • Peek: O(1) – We look at the front element.
  • isEmpty: O(1) – We check if the queue is empty.

All these operations are highly efficient and take constant time.

Real-World Applications of Queues

1. Task Scheduling

Operating systems use queues to manage tasks and processes that need to be executed. The CPU processes tasks in the order they are added to the queue.

2. Printer Queue

When multiple documents are sent to a printer, they are placed in a queue and printed in the order they arrived.

3. Network Buffers

In networking, queues are used to manage packets of data waiting to be processed or transmitted. Routers, for example, use queues to manage incoming and outgoing data packets.

4. Breadth-First Search (BFS)

In graph traversal, BFS uses a queue to explore nodes level by level, ensuring that each node is processed in the order it was discovered.

5. Request Handling

Web servers and databases often use queues to manage incoming requests, ensuring that requests are processed in the order they are received.

Wrapping It Up

Queues are a fundamental data structure that is incredibly useful in many real-world applications. Whether you’re using an array or a linked list, queues allow you to manage elements in a sequential, orderly manner. Understanding how queues work and how to implement them in pseudocode will make you a stronger programmer and better prepared to tackle various algorithmic challenges.

That’s all for today! I hope this blog helped you understand the concepts of queues and their operations. Until next time, happy coding! 🚀