Answer to Question #250384 in C for Ram

Question

Write a program for implementation of priority queue with character data elements. Each
element has an integer priority number between 1-5. Implement Enqueue () and Dequeue ()
functions in each of the following cases.
1. Linked list implementation of priority queue.
2. Array implementation of priority queue.

Answer 1

#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
class Node{
    public:
    char data;
    int priority;
    Node *next;
    Node();
    Node(char, int);
};


class LinkedQueue{
    Node *head, *tail;
    int size;
    public:
    LinkedQueue();
    void enqueue(char, int);
    void dequeue();
    void dispqueue();
    bool isEmpty();
};


class ArrayQueue{
    char *data;
    int size, *priority;
    public:
    ArrayQueue();
    void enqueue(char, int);
    void dequeue();
    void dispqueue();
    bool isEmpty();
};


int main(){
    LinkedQueue Lqueue;
    ArrayQueue Aqueue;
    srand(time(NULL));
    for(int i = 'A'; i <= 'J'; i++){
        int priority = rand() % 5 + 1;
        Lqueue.enqueue(i, priority);
        Aqueue.enqueue(i, priority);
    }
    cout<<"Linked List priority queue: \n"; 
    Lqueue.dispqueue();
    Lqueue.dequeue();
    cout<<"Dequeue once"<<endl;
    Lqueue.dispqueue();
    cout<<"Array Queue priority queue: \n"; 
    Aqueue.dispqueue();
    Aqueue.dequeue();
    cout<<"\nDeque once"<<endl;
    Aqueue.dispqueue();



    return 0;
}


Node::Node(){
    next = NULL;
}
Node::Node(char data, int priority){
    this->data = data;
    this->priority = priority;
    next = NULL;
}
LinkedQueue::LinkedQueue(){
    head = NULL;
    tail = NULL;
    size = 0;
}
void LinkedQueue::enqueue(char data, int priority){
    if(tail == NULL){
        tail = new Node(data, priority);
        head = tail;
        size++;
    }
    else{
        Node *temp = new Node(data, priority);
        Node *curr = head, *prev = NULL;
        while(curr != NULL){
            if(priority <= curr->priority){
                prev = curr;
                curr = curr->next;
            }
            else{
                break;
            }
        }
        if(prev == NULL){
            temp->next = head;
            head = temp;
            return;
        }
        temp->next = prev->next;
        prev->next = temp;
        if(prev == tail) tail = temp;
        size++;
    }
}
void LinkedQueue::dequeue(){
    if(head != NULL){
        Node *temp = head;
        head = head->next;
        if(temp == tail) tail = NULL;
        delete temp;
        size--;
    }
}
void LinkedQueue::dispqueue(){
    Node* curr = head;
    while(curr != NULL){
        cout<<"Data: "<<curr->data<<" Priority: "<<curr->priority<<endl;
        curr = curr->next;
    }
    cout<<endl;
}
bool LinkedQueue::isEmpty(){
    return !size;
}
ArrayQueue::ArrayQueue(){
    data = new char[50];
    priority = new int[50];
    size = 0;
}
void ArrayQueue::enqueue(char data, int priority){
    if(size == 0){
        this->data[size] = data;
        this->priority[size++] = priority;
        return;
    }
    if(size == 50) return; //currently max size
    int index = 0;
    for(int i = 0; i < size; i++){
        if(priority <= this->priority[i]){
            index++;
        }
        else{
            break;
        }
    }
    for(int i = size; i > index; i--){
        this->priority[i] = this->priority[i - 1];
        this->data[i] = this->data[i - 1];
    }
    this->priority[index] = priority;
    this->data[index] = data;
    size++;
}
void ArrayQueue::dequeue(){
    if(size == 0) return;
    for(int i = 0; i < size - 1; i++){
        this->priority[i] = this->priority[i + 1];
        this->data[i] = this->data[i + 1];
    }
    size--;
}
void ArrayQueue::dispqueue(){
    for(int i = 0; i < size; i++){
        cout<<"Data: "<<this->data[i]<<" Priority: "<<this->priority[i]<<endl;
    }
    cout<<endl;
}
bool ArrayQueue::isEmpty(){
    return !size;
}