In data structures, a queue is a data structure that is \"first in, first out\".

Question

In data structures, a queue is a data structure that is "first in, first out". It contains two methods: enqueue - adds an item to the queue dequeue - removes an item from the queue For this assignment you are going to implement a variation on this called a priority queue, where an integer corresponding to the priority is passed into the enqueue method upon invocation. As an example, we can have three successive calls to add items to the queue: q.enqueue("X", 10) q.enqueue("Y", 1) q.enqueue("Z", 3) Invoking dequeue on the object will then remove the item "X" from the queue, since it has the highest priority. A second invocation of the method returns "Z" while the third invocation returns "Y". Use an ArrayList as a representation of the queue. Include a main method which demonstrates successive adds and removals from your queue. Save your solution in a file named PriorityQueue.java.

Explanation / Answer

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

// A structure to represent a queue

struct Queue

{

    int front, rear, size;

    unsigned capacity;

    int* array;

};

// function to create a queue of given capacity.

// It initializes size of queue as 0

struct Queue* createQueue(unsigned capacity)

{

    struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));

    queue->capacity = capacity;

    queue->front = queue->size = 0;

    queue->rear = capacity - 1; // This is important, see the enqueue

    queue->array = (int*) malloc(queue->capacity * sizeof(int));

    return queue;

}

// Queue is full when size becomes equal to the capacity

int isFull(struct Queue* queue)

{ return (queue->size == queue->capacity); }

// Queue is empty when size is 0

int isEmpty(struct Queue* queue)

{ return (queue->size == 0); }

// Function to add an item to the queue.

// It changes rear and size

void enqueue(struct Queue* queue, int item)

{

    if (isFull(queue))

        return;

    queue->rear = (queue->rear + 1)%queue->capacity;

    queue->array[queue->rear] = item;

    queue->size = queue->size + 1;

    printf("%d enqueued to queue ", item);

}

// Function to remove an item from queue.

// It changes front and size

int dequeue(struct Queue* queue)

{

    if (isEmpty(queue))

        return INT_MIN;

    int item = queue->array[queue->front];

    queue->front = (queue->front + 1)%queue->capacity;

    queue->size = queue->size - 1;

    return item;

}

// Function to get front of queue

int front(struct Queue* queue)

{

    if (isEmpty(queue))

        return INT_MIN;

    return queue->array[queue->front];

}

// Function to get rear of queue

int rear(struct Queue* queue)

{

    if (isEmpty(queue))

        return INT_MIN;

    return queue->array[queue->rear];

}

// Driver program to test above functions./

int main()

{

    struct Queue* queue = createQueue(1000);

    enqueue(queue, 10);

    enqueue(queue, 20);

    enqueue(queue, 30);

    enqueue(queue, 40);

    printf("%d dequeued from queue ", dequeue(queue));

    printf("Front item is %d ", front(queue));

    printf("Rear item is %d ", rear(queue));

    return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.