C Exercises: Find the median of the elements in a queue

C Queue: Exercise-13 with Solution

Write a C program to find the median of the elements in a queue.

From Wikipedia,
In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution.
The median of a finite list of numbers is the "middle" number, when those numbers are listed in order from smallest to greatest.
If the data set has an odd number of observations, the middle one is selected. For example, the following list of seven numbers,
1, 3, 3, 6, 7, 8, 9
has the median of 6, which is the fourth value.
If the data set has an even number of observations, there is no distinct middle value and the median is usually defined to be the arithmetic mean of the two middle values. For example, this data set of 8 numbers1, 2, 3, 4, 5, 6, 8, 9 has a median value of 4.5, that is (4+5)/2 . (In more technical terms, this interprets the median as the fully trimmed mid-range).

Sample Solution:

C Code:

#include <stdio.h>

#define MAX_SIZE 100
int queue[MAX_SIZE];
int front = -1, back = -1;
// Function to insert an element into the queue
void enqueue(int item) {
    if (back == MAX_SIZE - 1) {
        printf("Error: Queue is full\n");
        return;
    }
    if (front == -1) {
        front = 0;
    }
    back++;
    queue[back] = item;
}

// Function to remove an element from a queue
int dequeue() {
    if (front == -1 || front > back) {
        printf("Error: Queue is empty\n");
        return -1;
    }
    int item = queue[front];
    front++;
    return item;
}

// Function to find the median of the elements in the queue
float find_median() {
    // First, make a copy of the queue
    int n = back - front + 1;
    int temp[n];
    for (int i = 0; i < n; i++) {
        temp[i] = queue[front + i];
    }
    // Then, sort the copy in ascending order
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (temp[j] < temp[i]) {
                int t = temp[i];
                temp[i] = temp[j];
                temp[j] = t;
            }
        }
    }
    // Calculate the median based on the sorted copy
    if (n % 2 == 0) {
        int m1 = temp[n/2 - 1];
        int m2 = temp[n/2];
        return (float)(m1 + m2) / 2;
    } else {
        int m = temp[n/2];
        return (float)m;
    }
}

// Function to display the elements in the queue
void display_elements() {
   for (int i = front; i <= back; i++) {
        printf("%d ", queue[i]);
    }
    printf("\n");
}

int main() {
    // Insert some elements into the queue.
    printf("Input some elements into a queue:\n");
    enqueue(1);
    enqueue(2);
    enqueue(3);
    enqueue(4);
    enqueue(5);
    printf("Queue elements are:\n");
    display_elements();
    // Find the median of the elements in the queue.
    float median = find_median();
    printf("The median of the elements in the queue is %f\n", median);
    printf("\nInput one more element:");
    enqueue(6);
	printf("\nQueue elements are:\n");
    display_elements();
    // Find the median of the elements in the queue.
    median = find_median();
    printf("The median of the elements in the queue is %f\n", median);	
	return 0;
}

Sample Output:

Input some elements into a queue:
Queue elements are:
1 2 3 4 5 
The median of the elements in the queue is 3.000000

Input one more element:
Queue elements are:
1 2 3 4 5 6 
The median of the elements in the queue is 3.500000

Flowchart:

C Programming Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Sort a queue in ascending order.