Queue FIFO.

dequeue.cc

/**
 * Dequeue:
 * Dequeue is also known as Double Ended Queue.
 * As the name suggests double ended,
 * it means that an element can be inserted or removed from both ends of the queue, unlike the other queues
 * in which it can be done only from one end. Because of this property, it may not obey the First In First Out property.
 *
 * implement using doubly linked list
 *
 * Operation    Description                                     Time Complexity
 * push_front() Inserts the element at the beginning.           O(1)
 * push_back()  Adds element at the end.                        O(1)
 * pop_front()  Removes the first element from the deque.       O(1)
 * pop_back()   Removes the last element from the deque.        O(1)
 * front()      Gets the front element from the deque.          O(1)
 * back()       Gets the last element from the deque.           O(1)
 * empty()      Checks whether the deque is empty or not.       O(1)
 * size()       Determines the number of elements in the deque. O(1)
*/

#include "iostream"

struct Node {
    unsigned int id;
    std::string name;
    Node *previous;
    Node *next;

    Node(unsigned int id, std::string name, Node *previous = nullptr, Node *next = nullptr) :
            id(id), name(name), previous(previous), next(next) {};
};

class Dequeue {
private:
    struct Node *head = nullptr;
    struct Node *tail = nullptr;
    int m_size = 0;
public:
    void push_front(unsigned int, std::string);

    void push_back(unsigned int, std::string);

    Node *pop_front();

    Node * pop_back();

    Node *front();

    Node *back();

    bool empty();

    int size();
};

void Dequeue::push_front(unsigned int id, std::string name) {
    Node *new_node = new Node(id, name);

    if (head == nullptr) {
        head = new_node;
        tail = new_node;

        m_size = 1;

        return;
    }

    head->previous = new_node;
    new_node->next = head;
    head = new_node;

    m_size++;
}

void Dequeue::push_back(unsigned int id, std::string name) {
    Node *new_node = new Node(id, name);

    if (tail == nullptr) {
        return push_front(id, name);
    }

    tail->next = new_node;
    new_node->previous = tail;
    tail = new_node;

    m_size++;
}

Node *Dequeue::pop_front() {
    if (head == nullptr)
        return nullptr;

    Node *tmp = head;

    head = head->next;
    if (head)
        head->previous = nullptr;
    else
        tail = nullptr;

    tmp->next = nullptr;

    m_size--;

    return tmp;
}

Node *Dequeue::pop_back() {
    if (tail == nullptr)
        return nullptr;

    Node *tmp = tail;

    tail = tail->previous;
    if (tail)
        tail->next = nullptr;
    else
        head = nullptr;

    tmp->previous = nullptr;

    m_size--;

    return tmp;
}

Node *Dequeue::front() {
    return head;
}

Node *Dequeue::back() {
    return tail;
}

bool Dequeue::empty() {
    return head == nullptr;
}

int Dequeue::size() {
    return m_size;
}

int main() {
    Dequeue dequeue;
    Node *tmp = nullptr;

    std::cout << "Size of queue: " << dequeue.size() << std::endl;

    dequeue.push_front(1, "Hello");
    dequeue.push_front(2, "World");
    dequeue.push_back(3, "Story");
    dequeue.push_back(4, "Single Linked List");
    dequeue.push_front(5, "Queue Data Structure");

    std::cout << "front in queue:\t" << dequeue.front()->id << ' ' << dequeue.front()->name << std::endl;
    std::cout << "back in queue:\t" << dequeue.back()->id << ' ' << dequeue.back()->name << std::endl;
    std::cout << "Size of queue: " << dequeue.size() << std::endl;

    while ((tmp = dequeue.pop_front()) != nullptr) {
        std::cout << tmp->id << ' ' << tmp->name << std::endl;
        delete tmp;
    }

    while (!dequeue.empty()) {
        tmp =  dequeue.pop_back();
        std::cout << tmp->id << ' ' << tmp->name << std::endl;
        delete tmp;
    }

    std::cout << "Size of queue: " << dequeue.size() << std::endl;

    return 0;
}

priority-queue-sorted-array.cc

/**
 * Priority queue can be implemented using the following data structures:
 * Arrays
 * Linked list
 * Heap data structure
 * Binary search tree
 *
 * So, What are we going to do?
 * fulfills the requirements priority queue using sorted array-based approach with binary search for insertion.
 * It provides a simple and effective way to manage elements with different priorities.
 *
 * Here's a table summarizing the time and space complexity of each function in the PriorityQueue class:
 * Function	    Time Complexity	Space Complexity
 * enqueue	    O(n)	        O(n)
 * dequeue	    O(1)	        O(1)
 * size	        O(1)	        O(1)
 *
 * Explanation:
 * - enqueue: In the worst case, the enqueue function has a time complexity of O(n) because it may need to shift elements
 *      in the array to make space for the new element. The space complexity is also O(n) because resizing the array may
 *      require allocating new memory.
 * - dequeue: The dequeue function has a time complexity of O(1) because it simply removes the first element from the array.
 *      The space complexity is also O(1) because it does not require any additional memory allocation.
 * - size: The size function simply returns the size of the priority queue, which is stored as a member variable.
 *      Therefore, both the time and space complexity are O(1).
*/

#include "iostream"
#include "limits.h"
#include "string.h"

struct QueueData {
    unsigned int id;
    std::string name;
    int priority;

    QueueData(unsigned int id, std::string name, int priority = INT_MIN) :
            id(id), name(name), priority(priority) {};
};

class PriorityQueue {
private:
    int m_size;
    int m_capacity;
    struct QueueData **pStructQueueData;
public:
    PriorityQueue() : pStructQueueData(nullptr), m_size(0), m_capacity(0) {};

    ~PriorityQueue() {
        for (int i = 0; i < m_size; i++) {
            delete pStructQueueData[i];
        }
        delete[] pStructQueueData;
    }

    void enqueue(unsigned int id, std::string name, int priority = INT_MIN) {
        if (m_size == m_capacity)
            resize();

        int idx = binarySearch(priority);

        for (int i = m_size; i > idx; i--)
            pStructQueueData[i] = pStructQueueData[i - 1];

        pStructQueueData[idx] = new QueueData(id, name, priority);

        m_size++;
    }

    QueueData *dequeue() {
        if (!m_size)
            return nullptr;

        return pStructQueueData[--m_size];
    }

    int size() {
        return m_size;
    }

private:
    void resize() {
        int new_capacity = m_capacity > 0 ? m_capacity * 2 : 1;

        QueueData **tmp_queueData = new QueueData *[new_capacity];
        memcpy(tmp_queueData, pStructQueueData, m_size * sizeof(QueueData *));

        delete[] pStructQueueData;

        pStructQueueData = tmp_queueData;

        m_capacity = new_capacity;
    }

    /*
     * Time complexity of Binary Search is O(log n), where n is the number of elements in the array.
     * It divides the array in half at each step. Space complexity is O(1) as it uses a constant amount of extra space.
     */
    int binarySearch(int priority) {
//        int idx = m_size;
//        for (; idx > 0; idx--)
//            if (priority > pStructQueueData[idx - 1]->priority)
//                break;
//        return idx;

        int left = 0, right = m_size - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (pStructQueueData[mid]->priority == priority) {
                while (mid < m_size && pStructQueueData[mid]->priority == priority)
                    ++mid;

                return mid;
            } else if (pStructQueueData[mid]->priority < priority) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }
};

int main() {
    PriorityQueue priorityQueue;
    QueueData *tmp = nullptr;

    std::cout << "Size: " << priorityQueue.size() << std::endl;

    priorityQueue.enqueue(1, "Friends", 0);
    priorityQueue.enqueue(2, "Jennifer Aniston", 3);
    priorityQueue.enqueue(3, "Courteney Cox", 2);
    priorityQueue.enqueue(4, "Lisa Kudrow", 1);
    priorityQueue.enqueue(5, "Matt LeBlanc", 1);
    priorityQueue.enqueue(6, "Matthew Perry", 2);
    priorityQueue.enqueue(7, "David Schwimmer", 3);

    std::cout << "Size: " << priorityQueue.size() << std::endl;

    while ((tmp = priorityQueue.dequeue()) != nullptr) {
        std::cout << tmp->priority << ' ' << tmp->name << ' ' << tmp->id << std::endl;
        delete tmp;
    }

    std::cout << "Size: " << priorityQueue.size() << std::endl;

    return 0;
}

priority-queue-sorted-doubly-linked-list.cc

#include "iostream"
#include "cstring"

struct QueueHolder {
    unsigned int id;
    std::string str;
};

class Queue {
private:
    int rear = 0;
    QueueHolder **queueHolder;
public:
    Queue() {
        rear = 0;
        queueHolder = nullptr;
    }

    void enqueue(unsigned int id, std::string name) {
        QueueHolder **tmp = new QueueHolder *[rear];

        tmp[rear] = new QueueHolder();
        tmp[rear]->id = id;
        tmp[rear]->str = name;

        memcpy(tmp, queueHolder, rear * sizeof(QueueHolder *));

        delete[] queueHolder;

        queueHolder = tmp;

        rear++;
    }

    QueueHolder *dequeue() {
        rear--;

        delete queueHolder[0];

        for (int i = 0; i < rear; i++) {
            queueHolder[i] = queueHolder[i + 1];
        }

        if (rear)
            return queueHolder[0];

        return nullptr;
    }

    QueueHolder *get_front() {
        if (is_empty()) {
            fprintf(stderr, "Queue is Empty\n");
            exit(EXIT_FAILURE);
        }

        return queueHolder[0];
    }

    QueueHolder *get_rear() {
        if (is_empty()) {
            fprintf(stderr, "Queue is Empty\n");
            exit(EXIT_FAILURE);
        }

        return queueHolder[rear - 1];
    }

    bool is_empty() {
        return rear == 0;
    }

    int size() {
        return rear;
    }
};

int main() {
    Queue queue;
    QueueHolder *queueHolder = nullptr;

    queue.enqueue(1, "Hello");
    queue.enqueue(2, "World");
    queue.enqueue(3, "Story");

    queueHolder = queue.get_front();
    do {
        std::cout << "[front]: " << queueHolder->id << ' ' << queueHolder->str << ' ';

        queueHolder = queue.get_rear();
        std::cout << "[rear]: " << queueHolder->id << ' ' << queueHolder->str << ' ';

        std::cout << "[size]: " << queue.size();

        std::cout << std::endl;
    } while ((queueHolder = queue.dequeue()) != nullptr);

    std::cout << "[size]: " << queue.size() << std::endl;

    return 0;
}

priority-queue-unsorted-array.cc

/**
 * Priority queue can be implemented using the following data structures:
 * Arrays
 * Linked list
 * Heap data structure
 * Binary search tree
 * 
 * So, What are we going to do?
 * fulfills the requirements for an array-based priority queue.
 * It provides a simple and effective way to manage elements with different priorities.
 *
 * Arrays           enqueue()               dequeue()   peek()  size()
 * Time Complexity  O(1) due to resizing    O(n)        O(n)    O(1)
 *
 * enqueue(): This function is used to insert new data into the queue.
 * dequeue(): This function removes the element with the highest priority from the queue.
 * peek()/top(): This function is used to get the highest priority element in the queue without removing it from the queue.
 */

#include "iostream"
#include "limits.h"
#include "string.h"

struct QueueData {
    unsigned int id;
    std::string name;
    int priority = INT_MIN;

    QueueData(unsigned int id, std::string name, int priority = INT_MIN) :
            id(id), name(name), priority(priority) {};
};

class PriorityQueue {
private:
    struct QueueData **m_queue = nullptr;
    int m_size = 0;
    int m_capacity = 0;
public:
    PriorityQueue() : m_queue(nullptr), m_size(0), m_capacity(0) {}

    ~PriorityQueue() {
        for (int i = 0; i < m_size; ++i) {
            delete m_queue[i];
        }
        delete[] m_queue;
    }

    void enqueue(unsigned int id, std::string name, int priority = INT_MIN) {
        if (m_capacity <= m_size)
            resize();

        m_queue[m_size++] = new QueueData(id, name, priority);
    }

    void dequeue() {
        if (m_size == 0) {
            return;
        }

        int idx = findHighestPriorityIndex();

        if (idx < 0)
            return;

        delete m_queue[idx];

        m_queue[idx] = m_queue[--m_size];
    }

    QueueData *peek() {
        if (m_size == 0) {
            return nullptr;
        }

        int idx = findHighestPriorityIndex();

        return m_queue[idx];
    }

    int size() {
        return m_size;
    }

private:
    int findHighestPriorityIndex() const {
        int idx = -1;

        int high_priority = INT_MIN;

        for (int i = 0; i < m_size; i++) {
            if (high_priority <= m_queue[i]->priority) {
                high_priority = m_queue[i]->priority;
                idx = i;
            }
        }

        return idx;
    }

    void resize() {
        int new_capacity = m_capacity > 0 ? m_capacity * 2 : 1;

        struct QueueData **tmp_queue = new QueueData *[new_capacity];

        memcpy(tmp_queue, m_queue, m_size * sizeof(QueueData *));

        delete[] m_queue;
        m_queue = tmp_queue;

        m_capacity = new_capacity;
    }
};

int main() {
    PriorityQueue priorityQueue;
    QueueData *tmp = nullptr;

    std::cout << "Size: " << priorityQueue.size() << std::endl;

    priorityQueue.enqueue(1, "Hello");
    priorityQueue.enqueue(2, "World", 3);
    priorityQueue.enqueue(3, "Story", 0);
    priorityQueue.enqueue(4, "vividly", 5);
    priorityQueue.enqueue(5, "explicitly", 4);
    priorityQueue.enqueue(7, "Gorgeous", 4);

    std::cout << "Size: " << priorityQueue.size() << std::endl;

    while ((tmp = priorityQueue.peek())) {
        std::cout << tmp->id << ' ' << tmp->name << ' ' << tmp->priority << std::endl;
        priorityQueue.dequeue();
    }

    std::cout << "Size: " << priorityQueue.size() << std::endl;

    return 0;
}

queue.c

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

struct Information {
    unsigned int id;
    char *str;
};

struct Queue {
    size_t rear;
    struct Information **information;
};

int is_empty(struct Queue);
void enqueue(struct Queue*, unsigned int, char*);
void dequeue(struct Queue*);
struct Information* get_front(struct Queue*);
struct Information* get_rear(struct Queue*);
int size(struct Queue);

void enqueue(struct Queue *queue, unsigned int id, char *str) {
    queue->information = realloc(queue->information, sizeof(struct Information*) * (queue->rear + 1));

    queue->information[queue->rear] = (struct Information*)malloc(sizeof(struct Information));
    queue->information[queue->rear]->id = id;
    queue->information[queue->rear]->str = strdup(str);

    queue->rear++;
}

void dequeue(struct Queue *queue) {
    if (is_empty(*queue)) {
        fprintf(stderr, "Queue is empty\n");
        exit(EXIT_FAILURE);
    }

    queue->rear--;

    free(queue->information[0]->str);
    free(queue->information[0]);

    for (size_t i = 0; i < queue->rear; i++) {
        queue->information[i] = queue->information[i+1];
    }

    queue->information = realloc(queue->information, sizeof(struct Information*) * queue->rear);
}

struct Information* get_front(struct Queue *queue) {
    if (is_empty(*queue)) {
        fprintf(stderr, "Queue is empty\n");
        exit(EXIT_FAILURE);
    }

    return queue->information[0];
}

struct Information* get_rear(struct Queue *queue) {
    if (is_empty(*queue)) {
        fprintf(stderr, "Queue is empty\n");
        exit(EXIT_FAILURE);
    }

    return queue->information[queue->rear-1];
}

int is_empty(struct Queue queue) {
    return queue.rear == 0;
}

int size(struct Queue queue) {
    return queue.rear;
}

int main() {
    struct Queue queue;
    queue.information = NULL;
    queue.rear = 0;

    enqueue(&queue, 1, "Hello");
    enqueue(&queue, 2, "World");
    enqueue(&queue, 3, "Store");

    struct Information *i = NULL;

    while (!is_empty(queue)) {
        i = get_front(&queue);
        printf("[front]: %d %s", i->id, i->str);

        i = get_rear(&queue);
        printf(" [rear]: %d %s\n", i->id, i->str);

        dequeue(&queue);
    }

    free(queue.information);

    return 0;
}

queue.cc

#include "iostream"
#include "cstring"

struct QueueHolder {
    unsigned int id;
    std::string str;
};

class Queue {
private:
    int rear = 0;
    QueueHolder **queueHolder;
public:
    Queue() {
        rear = 0;
        queueHolder = nullptr;
    }

    void enqueue(unsigned int id, std::string name) {
        QueueHolder **tmp = new QueueHolder *[rear];

        tmp[rear] = new QueueHolder();
        tmp[rear]->id = id;
        tmp[rear]->str = name;

        memcpy(tmp, queueHolder, rear * sizeof(QueueHolder *));

        delete[] queueHolder;

        queueHolder = tmp;

        rear++;
    }

    QueueHolder *dequeue() {
        rear--;

        delete queueHolder[0];

        for (int i = 0; i < rear; i++) {
            queueHolder[i] = queueHolder[i + 1];
        }

        if (rear)
            return queueHolder[0];

        return nullptr;
    }

    QueueHolder *get_front() {
        if (is_empty()) {
            fprintf(stderr, "Queue is Empty\n");
            exit(EXIT_FAILURE);
        }

        return queueHolder[0];
    }

    QueueHolder *get_rear() {
        if (is_empty()) {
            fprintf(stderr, "Queue is Empty\n");
            exit(EXIT_FAILURE);
        }

        return queueHolder[rear - 1];
    }

    bool is_empty() {
        return rear == 0;
    }

    int size() {
        return rear;
    }
};

int main() {
    Queue queue;
    QueueHolder *queueHolder = nullptr;

    queue.enqueue(1, "Hello");
    queue.enqueue(2, "World");
    queue.enqueue(3, "Story");

    queueHolder = queue.get_front();
    do {
        std::cout << "[front]: " << queueHolder->id << ' ' << queueHolder->str << ' ';

        queueHolder = queue.get_rear();
        std::cout << "[rear]: " << queueHolder->id << ' ' << queueHolder->str << ' ';

        std::cout << "[size]: " << queue.size();

        std::cout << std::endl;
    } while ((queueHolder = queue.dequeue()) != nullptr);

    std::cout << "[size]: " << queue.size() << std::endl;

    return 0;
}

Basic Operations on Queue:

A Queue Data Structure is a fundamental concept in computer science used for storing and managing data in a specific order. It follows the principle of “First in, First out” (FIFO), where the first element added to the queue is the first one to be removed. Queues are commonly used in various algorithms and applications for their simplicity and efficiency in managing data flow.

• enqueue(): Inserts an element at the end of the queue i.e. at the rear end.
• dequeue(): This operation removes and returns an element that is at the front end of the queue.
• front(): This operation returns the element at the front end without removing it.
• rear(): This operation returns the element at the rear end without removing it.
• isEmpty(): This operation indicates whether the queue is empty or not.
• isFull(): This operation indicates whether the queue is full or not.
• size(): This operation returns the size of the queue i.e. the total number of elements it contains.

So what have we done now?

• Queue
• Queue
• Priority queue unsorted array
• Priority queue sorted doubly linked list
• Priority wueue sorted arry
• Dequeue