Queues.md

Queues

Queues are FIFO structure first in-first out. The first item added is the first one removed.

• Linked list implementation
• Array implementation

Types

• priority queues
• DEqueues

---

QueueInterface Class

#pragma once
template< class T> 
class QueueInterface 
{ 
public: 
    /** Sees whether this queue is empty. 
    @return True if the queue is empty, or false if not. */ 
    virtual bool isEmpty() const = 0; 

    /** Adds a new entry to the back of this queue. 
    @post If the operation was successful, newEntry is at the
    back of the queue. 
    @param newEntry The object to be added as a new entry. 
    @return True if the addition is successful or false if not. */ 
    virtual bool enqueue( const T& item) = 0;

    /** Removes the front of this queue. 
    @post If the operation was successful, the front of the queue
    has been removed. 
    @return True if the removal is successful or false if not. */ 
    virtual bool dequeue() = 0;

    /** Returns the front of this queue. 
    @pre The queue is not empty. 
    @post The front of the queue has been returned, and the
    queue is unchanged. 
    @return The front of the queue. */ 
    virtual T peekFront() = 0; 
}; // end QueueInterface 

---

Linked list implementation

A linked list implementation offers dynamic resizing as new elements are added

Class definition

template <typename T>
class ArrayQueue : public QueueInterface 
{
private:
    Node<T>* frontPtr;
    Node<T>* backPtr;
public:
    LinkedQueue();
    bool isEmpty() const;
    bool enqueue(const T& item);
    bool dequeue();
    T peekFront();
    ~ LinkedQueue();
};

• assuming class node is implemented
• We will need a head pointer as usual and a tail pointer for the enqueue operation

isEmpty

template <typename T>
bool LinkedQueue<T>::isEmpty() const
{
    return (!frontPtr && !backPtr);
}

enqueue

template <typename T>
bool LinkedQueue<T>::enqueue(T item)
{
    Node<T>* newNodePtr = new Node<T>(item);

    //if node inserted is the first one
    if (frontPtr == nullptr)
        frontPtr = newNodePtr;
    else
        backPtr->next = newNodePtr;

    backPtr = newNodePtr;
    return true;
}

dequeue

template <typename T>
bool LinkedQueue<T>::dequeue()
{
    if (isEmpty())
        throw std::out_of_range("can not dequeue from an empty queue");

    Node<T>* nodeToDeletePtr = frontPtr;
    frontPtr = frontPtr->next;
    delete nodeToDeletePtr;

    if (frontPtr == nullptr) //if list becomes empty set back to null
        backPtr = nullptr;

    return true;
}

peekfront

template< class T> 
ItemType ArrayQueue<T>::peekFront()
{ 
    if (isEmpty())
	throw std::out_of_range("peekFront() called with empty queue");
    return front->item; 
} 

Array implementation

An array implementation provides faster access

Naïve approach: linear array

Using a linear array isn't the most efficient way, every time we dequeue an item we have to shift all items to the left so we don't run out of space, that process takes O(n).

Circular array

A better approach is to use a circular array, when you reach the end of it you go back to the beginning in a cycle that way we won't need to shift anything!

There is just one small problem with circular array is you can't detect whether a queue is empty or full easily, Consider the following two examples:

In both cases: empty and full queue front can be ahead of back. There are multiple ways we can solve this problem: one way is to keep a count of the items or use a Boolean variable isFull .

Another solution would be to sacrifice one location of the array to always be empty and declare the array to be of size + 1

The new conditions become:

• for full queue: front == (back + 1) % (size + 1)
• for empty queue: front == back

and we increment the indices using the following relations:

• front = (front + 1) % (size + 1)
• back = (back + 1) % (size + 1)

In order for this solution to work and be easy to implement we either change:

• The front index to point to the location before the first item
• The back index to point to the location after the last item

The difference between both approaches is the way enqueue and peekFront() are implemented

• Front points to location before first item
  • In peekFront you return the element after front
• Back points to location after last item
  • In enqueue you add the item then increment the back index

Since they are both very similar we will explain only one (the second case)

Class definition

template <typename T>
class ArrayQueue : public QueueInterface 
{
private:
    int front;
    int back;
    int size;
    T* items;
public:
    ArrayQueue(int size);
    bool isEmpty() const;
    bool enqueue(const T& item);
    bool dequeue();
    T peekFront();
    ~ ArrayQueue();
};

• Front and back indices to keep track of start and end
• The array is dynamically allocated based on the size specified

Constructor

template <typename T>
bool ArrayQueue<T>::ArrayQueue(int size) : front(0), back(0), size(size)
{
    items = new T[size + 1];
}

isEmpty

template <typename T>
bool ArrayQueue<T>::isEmpty() const
{
    return front == back;
}

enqueue()

• The back index points to the location after the last item

template <typename T>
bool ArrayQueue<T>::enqueue(const T& item) 
{
    if(front == (back + 1) % (size + 1))
	throw std::out_of_range("queue is full can not add more items");

    items[back] = item;
    back = (back+1) % (size + 1);
    return true;
}

dequeue

template <typename T>
bool ArrayQueue<T>::dequeue() 
{
    if(isEmpty())
	throw std::out_of_range("can not dequeue from an empty queue");
		
    front = (front+1) % (size + 1);
    return true;
}

we increment the front index, note that "deleting" is advancing front and overwriting the old item when a new item is added to the same location.

peekFront

template <typename T>
T ArrayQueue<T>::peekFront() 
{
    if(isEmpty())
	throw std::out_of_range("empty queue");
    return items[front];
}

---

Applications

• Task scheduling: Operating systems schedule processes using queues, ensuring tasks are executed in the order they are received.
• Simulation: Queues can model real-world queues, such as lines at a store or traffic light wait times.
• Breadth-first search (BFS) in trees and graphs: BFS algorithms often use queues to explore nodes level by level.