CS Notes

Implementing Linear Queues

11 min read

Implementing Linear Queues

How Do You Program a Queue?

  • To recap the main operations of Queues and how they work, follow this link
  • When programming a queue, the main operations listed below must be included in your program
    • Initialise the queue
    • Enqueue
    • Dequeue
    • Peek

Algorithm to Implement a Linear Queue

  • The code below initialises an array and index pointers to service a linear queue
  • The constant MAX_SIZE informs the size of the array
  • The front index pointer is initialised to 0 and the rear index pointer is initialised to -1
  • The rear index pointer will be incremented every time you add an item to the queue, so the initial value will ensure the first item is added into the first position of the array (index 0)
  • Once the first item has been added, both front and rear will correctly point to the item in the array
PseudocodePythonJava
MAX_SIZE = 6
ARRAY queue[max_size]
front = 0
rear = -1		MAX_SIZE = 6
queue[]
front = 0
rear = -1		public class Main {
public static final int MAX_SIZE = 6;
public static ArrayList<Integer> queue = new ArrayList<>();
public static int front = 0;
public static int rear = -1;
public static void main(String[] args) {
// Your code here
}
}
EnQueue Data
  • Before adding an item to the queue you need to check that the queue is not full
  • When the rear index pointer is pointing to the final space in the array there is no room to add new items
  • A subroutine isFull() is used to carry out the check
  • If the end of the array has not been reached, the rear index pointer is incremented and the new item is added to the queue
PseudocodePythonJava
FUNCTION isFull(rear)
IF(rear+1) == MAX_SIZE THEN
RETURN True
ELSE
RETURN False
ENDIF
ENDFUNCTION

FUNCTION enqueue(queue, rear, data)
IF isFull(rear) == True THEN
PRINT ("Full")
ELSE
rear = rear + 1
queue[rear] = data
ENDIF
RETURN rear
ENDFUNCTION		def isFull(rear):
if rear + 1 == MAX_SIZE:
return True
else:
return False

def enqueue(queue, rear, data):
if isFull(rear):
print("Full")
else:
rear = rear + 1
queue[rear] = data
return rear

# Example usage
queue = [None] * MAX_SIZE
rear = -1
rear = enqueue(queue, rear, 10)
rear = enqueue(queue, rear, 20)
rear = enqueue(queue, rear, 30)

print(queue) # [10, 20, 30]		public static boolean isFull(int rear) {
if (rear + 1 == MAX_SIZE) {
return true;
} else {
return false;
}
}

public static int enqueue(int[] queue, int rear, int data) {
if (isFull(rear)) {
System.out.println("Full");
} else {
rear = rear + 1;
queue[rear] = data;
}
return rear;
}
DeQueue Data
  • Before taking an item from the queue you need to make sure that the queue is not empty
  • A subroutine isEmpty() can be defined for this purpose
  • The subroutine will check whether the front index pointer is ahead of the rear index pointer
  • If the queue is not empty the item at the front of the queue is returned and front is incremented by 1
PseudocodePythonJava
FUNCTION isEmpty(front, rear)
IF front > rear THEN
RETURN True
ELSE
RETURN False
ENDIF
ENDFUNCTION

FUNCTION dequeue(queue, rear, front)
IF isEmpty(front, rear) THEN
PRINT ("Empty")
dequeuedItem = Null
ELSE
dequeuedItem = queue[front]
front = front + 1
ENDIF
RETURN (dequeuedItem, front)
ENDFUNCTION		def isEmpty(front, rear):
if front > rear:
return True
else:
return False

def dequeue(queue, rear, front):
if isEmpty(front, rear):
print("Empty")
dequeuedItem = None
else:
dequeuedItem = queue[front]
front = front + 1
return dequeuedItem, front

# Example usage
MAX_SIZE = 100
queue = [10, 20, 30, 40, 50]
front = 0
rear = len(queue) - 1

dequeuedItem, front = dequeue(queue, rear, front)
print("Dequeued item:", dequeuedItem)
print("Front:", front)

dequeuedItem, front = dequeue(queue, rear, front)
print("Dequeued item:", dequeuedItem)
print("Front:", front)		import java.util.Arrays;

public class Main {
public static boolean isEmpty(int front, int rear) {
if (front > rear) {
return true;
} else {
return false;
}
}

public static Object[] dequeue(int[] queue, int rear, int front) {
if (isEmpty(front, rear)) {
System.out.println("Empty");
Object[] result = { null, front };
return result;
} else {
Object[] result = { queue[front], front + 1 };
return result;
}
}

public static void main(String[] args) {
int MAX_SIZE = 100;
int[] queue = { 10, 20, 30, 40, 50 };
int front = 0;
int rear = queue.length - 1;

Object[] dequeuedResult = dequeue(queue, rear, front);
Object dequeuedItem = dequeuedResult[0];
front = (int) dequeuedResult[1];
System.out.println("Dequeued item: " + dequeuedItem);
System.out.println("Front: " + front);

dequeuedResult = dequeue(queue, rear, front);
dequeuedItem = dequeuedResult[0];
front = (int) dequeuedResult[1];
System.out.println("Dequeued item: " + dequeuedItem);
System.out.println("Front: " + front);
}
}

Implementing Circular Queues

Algorithm to Implement a Circular Queue

  • When you manipulate the items in a circular queue you must be able to advance the index pointers in such a way that they will reset to 0 once the end has been reached

(pseudo) (pointer + 1) MOD MAX_SIZE

  • This can be used to calculate the new position for the index pointer
  • Where the pointer is front or rear and max_size is the maximum number of items in the queue
Initial PositionPointer + 1(Pointer + 1) MOD 7New Position
0111
1222
2333
3444
4555
5666
6700
  • When the index pointer references the last position in the array, position 6, the next position is calculated as (6+1) MOD 7 which gives the result 0
  • This allows the index pointer to move back to the reference at the start of the array

Initialise Circular Queue

  • The initialisation is the same as a linear queue apart from you initialise the front index to -1 as this will allow you to be certain that you have an empty queue
PseudocodePythonJava
MAX_SIZE = 4
ARRAY cQueue[max_size]
front = -1
rear = -1		MAX_SIZE = 4
cQueue[]
front = -1
rear = -1		public class CircularQueue {
private static final int MAX_SIZE = 4;
private int[] cQueue = new int[MAX_SIZE];
private int front = -1;
private int rear = -1;

public static void main(String[] args) {
CircularQueue circularQueue = new CircularQueue();
// Use the circularQueue object to perform operations on the circular queue
}
}

Enqueue Circular Queue

  • Before an item can be enqueued the array needs to be checked to see if it’s full
  • It will be full if the next position to be used is already occupied by the item at the front of the queue
  • If the queue is not full then the rear index pointer must be adjusted to reference the next free position so that the new item can be added
PseudocodePythonJava
MAX_SIZE = 4
ARRAY cQueue[max_size]
front = -1
rear = -1

FUNCTION is_full(front, rear)
IF (rear + 1) MOD MAX_SIZE == front THEN
RETURN True
ELSE
RETURN False
ENDFUNCTION

FUNCTION enqueue(queue, front, rear, data)
IF is_full(front, rear) == True THEN
PRINT("Queue is full")
ELSE
rear = (rear + 1) MOD MAX_SIZE
queue[rear] = data
IF front = -1 THEN // First item to be queued
front = 0
ENDIF
ENDIF
RETURN (front, rear)
ENDFUNCTION		MAX_SIZE = 4
cQueue = [None] * MAX_SIZE
front = -1
rear = -1

def is_full(front, rear):
if (rear + 1) % MAX_SIZE == front:
return True
else:
return False

def enqueue(queue, front, rear, data):
if is_full(front, rear):
print("Queue is full")
else:
rear = (rear + 1) % MAX_SIZE
queue[rear] = data
if front == -1: # First item to be queued
front = 0
return front, rear		public class CircularQueue {
private static final int MAX_SIZE = 4;
private int[] cQueue = new int[MAX_SIZE];
private int front = -1;
private int rear = -1;

public static void main(String[] args) {
CircularQueue circularQueue = new CircularQueue();
// Use the circularQueue object to perform operations on the circular queue
}
}

// Note: Java code for enqueue would be implemented as methods in the class

DeQueue Circular Queue

  • Before dequeuing the array needs to be checked if it’s empty. If the queue is not empty then the item at the front is dequeued
  • If this is the only item that was in the queue, the rear and front pointers are reset
  • Otherwise the pointer moves to reference the next item in the queue
PseudocodePythonJava
MAX_SIZE = 4
ARRAY cQueue[max_size]
front = -1
rear = -1

FUNCTION is_empty(rear)
IF front == -1 THEN
RETURN True
ELSE
RETURN False
ENDFUNCTION

FUNCTION dequeue(queue, front, rear)
IF is_empty(rear) == True THEN
PRINT("Queue is empty - nothing to dequeue")
dequeued_item = Null
ELSE
dequeued_item = queue[front]
// Check if the queue is empty
IF front == rear THEN
front = -1
rear = -1
ELSE
front = (front + 1) MOD maxsize
ENDIF
ENDIF
RETURN (dequeued_item, front, rear)
ENDFUNCTION		def is_empty(front):
if front == -1:
return True
else:
return False

def dequeue(queue, front, rear):
if is_empty(front):
print("Queue is empty - nothing to dequeue")
dequeued_item = None
else:
dequeued_item = queue[front]
if front == rear:
front = -1
rear = -1
else:
front = (front + 1) % MAX_SIZE
return dequeued_item, front, rear		public class CircularQueue {
private static final int MAX_SIZE = 4;
private Object[] cQueue = new Object[MAX_SIZE];
private int front = -1;
private int rear = -1;

public static void main(String[] args) {
CircularQueue circularQueue = new CircularQueue();
// Use the circularQueue object to perform operations on the circular queue
}

private boolean isEmpty(int front) {
if (front == -1) {
return true;
} else {
return false;
}
}

private void dequeue(Object[] queue, int front, int rear) {
if (isEmpty(front)) {
System.out.println("Queue is empty - nothing to dequeue");
Object dequeuedItem = null;
} else {
Object dequeuedItem = queue[front];
if (front == rear) {
front = -1;
rear = -1;
} else {
front = (front + 1) % MAX_SIZE;
}
}
}
}

Implementing Priority Queues

Algorithm to Implement a Priority Queue

  • A priority queue is where each item in the queue has a priority
  • When new items are added, they are inserted ahead of those with a lower priority and behind items of equal priority
  • If you want to implement a priority queue it is best to use OOP
  • Encapsulating the data and methods within class definitions provides a neat solution and once written, the class can be reused in other applications that require a queue

Pseudocode

FUNCTION enqueue(queue, element, priority)
    // Insert the element into the queue based on its priority
    // Higher priority elements are placed towards the front

    IF queue is empty OR priority is higher than the first element's priority
        Insert element at the front of the queue
    ELSE IF priority is lower than or equal to the last element's priority
        Insert element at the end of the queue
    ELSE
        Find the appropriate position in the queue to insert the element based on priority
        Shift the elements to the right to make space for the new element
        Insert the element at the determined position
    ENDIF
ENDFUNCTION

FUNCTION dequeue(queue)
    // Remove and return the element with the highest priority from the queue

    IF queue is empty
        Return an error indicating that the queue is empty
    ELSE
        Remove and return the element from the front of the queue
    ENDIF
ENDFUNCTION

FUNCTION peek(queue)
    // Return the element with the highest priority without removing it from the queue

    IF queue is empty
        Return an error indicating that the queue is empty
    ELSE
        Return the element from the front of the queue
    ENDIF
ENDFUNCTION

FUNCTION is_empty(queue)
    // Check if the queue is empty

    IF queue is empty
        Return True
    ELSE
        Return False
    ENDIF
ENDFUNCTION

Python

class PriorityQueue:
    def __init__(self):
        self.queue = []

    def enqueue(self, element, priority):
        # Insert the element into the queue based on its priority
        # Higher priority elements are placed towards the front

        if len(self.queue) == 0 or priority > self.queue[0][1]:
            self.queue.insert(0, (element, priority))
        elif priority <= self.queue[-1][1]:
            self.queue.append((element, priority))
        else:
            index = 0
            while index < len(self.queue) and priority <= self.queue[index][1]:
                index += 1
            self.queue.insert(index, (element, priority))

    def dequeue(self):
        # Remove and return the element with the highest priority from the queue

        if self.is_empty():
            raise IndexError("Queue is empty - nothing to dequeue")
        else:
            return self.queue.pop(0)[0]

    def peek(self):
        # Return the element with the highest priority without removing it from the queue

        if self.is_empty():
            raise IndexError("Queue is empty - nothing to peek")
        else:
            return self.queue[0][0]

    def is_empty(self):
        # Check if the queue is empty

        return len(self.queue) == 0

Java

import java.util.ArrayList;
import java.util.List;

class PriorityQueue {
    private List<Element> queue;

    public PriorityQueue() {
        this.queue = new ArrayList<>();
    }

    public void enqueue(Object element, int priority) {
        // Insert the element into the queue based on its priority
        // Higher priority elements are placed towards the front

        if (queue.isEmpty() || priority > queue.get(0).getPriority()) {
            queue.add(0, new Element(element, priority));
        } else if (priority <= queue.get(queue.size() - 1).getPriority()) {
            queue.add(new Element(element, priority));
        } else {
            int index = 0;
            while (index < queue.size() && priority <= queue.get(index).getPriority()) {
                index++;
            }
            queue.add(index, new Element(element, priority));
        }
    }

    public Object dequeue() {
        // Remove and return the element with the highest priority from the queue

        if (isEmpty()) {
            throw new IndexOutOfBoundsException("Queue is empty - nothing to dequeue");
        } else {
            return queue.remove(0).getElement();
        }
    }

    public Object peek() {
        // Return the element with the highest priority without removing it from the queue

        if (isEmpty()) {
            throw new IndexOutOfBoundsException("Queue is empty - nothing to peek");
        } else {
            return queue.get(0).getElement();
        }
    }

    public boolean isEmpty() {
        return queue.isEmpty();
    }
}

// Assuming Element class is defined elsewhere

Graph View

Backlinks