CIRCULAR QUEUE

 Question:

Develop a menu driven Program in C for the following operations on Circular QUEUE of 

Characters  (Array Implementation of Queue with maximum size MAX)

  1. Insert an Element on to Circular QUEUE

  2. Delete an Element from Circular QUEUE

  3. Demonstrate Overflow and Underflow situations on Circular QUEUE

  4. Display the status of Circular QUEUE

  5. Exit

Support the program with appropriate functions for each of the above operations

 

Your C code implements a Circular Queue with the following operations:

  • Insertion (with overflow demonstration)

  • Deletion (with underflow demonstration)

  • Display (to show current queue contents)

  • Exit

However, there's a small issue in how characters are inputted and managed due to the way scanf works with newline characters. Specifically, the scanf("%c", &item) doesn't consume the newline (\n) left in the input buffer, which causes issues when you input characters. We can address this by ensuring that any residual newline characters are flushed properly.

Fixing the Program:

  1. __fpurge(stdin) Issue:

    • The function __fpurge(stdin) is not portable across compilers, especially on some systems (like Linux) it might not even work. We can replace it with a more general solution for clearing the buffer.

  2. Handling the Newline Character:

    • After scanning the integer for the menu (scanf("%d", &ch)), a newline (\n) may be left in the input buffer, which could cause issues when reading the next character. We'll use getchar() to consume that residual newline.

Here is the corrected and improved version of your code:

Corrected C Program: Circular Queue with Menu-Driven Operations

#include <stdio.h>
#include <stdlib.h>

#define MAX 3  // Maximum size of the Circular Queue

// Circular Queue structure
char cq[MAX];
int front = -1, rear = -1;

// Function prototypes
void insert(char item);
void delete();
void display();

// Main function to provide a menu-driven interface
void main()
{
    int ch;
    char item;
    while (1)
    {
        printf("\n\n~~Main Menu~~");
        printf("\n==> 1. Insertion and Overflow Demo");
        printf("\n==> 2. Deletion and Underflow Demo");
        printf("\n==> 3. Display");
        printf("\n==> 4. Exit");
        printf("\nEnter Your Choice: ");
        scanf("%d", &ch);
        getchar();  // Consume the leftover newline character from buffer

        switch (ch)
        {
        case 1:
            printf("\n\nEnter the element to be inserted: ");
            scanf("%c", &item);
            insert(item);
            break;
        case 2:
            delete();
            break;
        case 3:
            display();
            break;
        case 4:
            printf("\nExiting...\n");
            exit(0);
        default:
            printf("\n\nPlease enter a valid choice.\n");
        }
    }
}

// Function to insert an element into the circular queue
void insert(char item)
{
    if (front == (rear + 1) % MAX)  // Check if the queue is full (overflow condition)
    {
        printf("\n\n~~Circular Queue Overflow~~\n");
    }
    else
    {
        if (front == -1)  // First element being inserted
            front = rear = 0;
        else
            rear = (rear + 1) % MAX;  // Wrap around the rear pointer

        cq[rear] = item;
        printf("\nElement '%c' inserted into the queue\n", item);
    }
}

// Function to delete an element from the circular queue
void delete()
{
    char item;
    if (front == -1)  // Check if the queue is empty (underflow condition)
    {
        printf("\n\n~~Circular Queue Underflow~~\n");
    }
    else
    {
        item = cq[front];
        printf("\n\nDeleted element from the queue is: '%c'\n", item);

        if (front == rear)  // Only one element left in the queue
            front = rear = -1;  // Reset the queue to empty
        else
            front = (front + 1) % MAX;  // Wrap around the front pointer
    }
}

// Function to display the current status of the circular queue
void display()
{
    int i;
    if (front == -1)  // Check if the queue is empty
    {
        printf("\n\nCircular Queue is Empty\n");
    }
    else
    {
        printf("\nCircular Queue contents are:\n");
        printf("Front[%d] -> ", front);

        // Display elements from front to rear, wrapping around
        for (i = front; i != rear; i = (i + 1) % MAX)
        {
            printf(" %c", cq[i]);
        }
        printf(" %c", cq[i]);  // Print the rear element
        printf(" <- Rear[%d]\n", rear);
    }
}


Key Fixes and Enhancements:

  1. Newline Character Handling:

    • We use getchar() right after scanf("%d", &ch) to consume any leftover newline character (\n) that may remain in the input buffer after reading an integer. This prevents the issue when reading characters next time.

  2. Menu-Driven Interface:

    • The program provides a clear interface where the user can select between inserting, deleting, displaying the queue, or exiting the program.

  3. Circular Queue Operations:

    • Overflow occurs when you try to insert an element into a full queue.

    • Underflow occurs when you try to delete an element from an empty queue.

    • The display() function loops through the circular array and handles the wrap-around behavior correctly using the modulo operation.

Sample Input/Output:

ceciot@cec-IOT:~$ cd Desktop/
ceciot@cec-IOT:~/Desktop$ gcc circlequeue.c -o abcd
ceciot@cec-IOT:~/Desktop$ ./abcd


~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 1
Enter the element to be inserted: A
Element 'A' inserted into the queue


~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 1
Enter the element to be inserted: B
Element 'B' inserted into the queue


~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 1
Enter the element to be inserted: C
Element 'C' inserted into the queue

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 1
Enter the element to be inserted: D
~~Circular Queue Overflow~~


~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 3
Circular Queue contents are:
Front[0] ->  A B C <- Rear[2]

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 2
Deleted element from the queue is: 'A'

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 3
Circular Queue contents are:
Front[1] ->  B C <- Rear[2]


~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice:

 -------------------------------------------------------------------------------

 

 Explanation:

 Visualizing the Circular Queue:

Let’s say the queue has a maximum size of 5 (i.e., MAX = 5), and we start with an empty queue.

Initial Empty Queue:

Queue: [ _, _, _, _, _ ]
front = -1, rear = -1

  • The queue is empty because both front and rear are set to -1.

Inserting Elements (Enqueue Operations):

Let’s insert elements one by one into the queue.

  1. Insert A:

    • front and rear both point to 0, since it’s the first element.

    • front = rear = 0

    • Queue: [ A, _, _, _, _ ]

  2. Insert B:

    • rear moves to 1, while front remains the same.

    • Queue: [ A, B, _, _, _ ]

  3. Insert C:

    • rear moves to 2.

    • Queue: [ A, B, C, _, _ ]

  4. Insert D:

    • rear moves to 3.

    • Queue: [ A, B, C, D, _ ]

  5. Insert E:

    • rear moves to 4.

    • Queue: [ A, B, C, D, E ]

After inserting these 5 elements, the queue is full.

Full Queue:

Queue: [ A, B, C, D, E ]
front = 0, rear = 4

  • The queue is full because front = 0 and rear = 4, and the next position after the rear ((rear + 1) % MAX) is equal to the front pointer.

Dequeuing Elements:

Let’s now dequeue elements, and observe the behavior.

  1. Dequeue Operation (Remove A):

    • front moves to 1.

    • Queue: [ _, B, C, D, E ]

    • front = 1, rear = 4

  2. Dequeue Operation (Remove B):

    • front moves to 2.

    • Queue: [ _, _, C, D, E ]

    • front = 2, rear = 4

  3. Dequeue Operation (Remove C):

    • front moves to 3.

    • Queue: [ _, _, _, D, E ]

    • front = 3, rear = 4

Inserting After Deletion (Wrap-Around):

Since the queue had a space available after removing C, we can insert new elements without wasting space.

  1. Insert F (Wrap-Around):

    • Now, since rear = 4 and the next position is (rear + 1) % MAX = 0, rear wraps around to index 0.

    • Queue: [ F, _, _, D, E ]

    • front = 3, rear = 0

  2. Insert G:

    • rear moves to 1.

    • Queue: [ F, G, _, D, E ]

    • front = 3, rear = 1

Final Queue State:

Queue: [ F, G, _, D, E ]
front = 3, rear = 1

  • Front pointer is at index 3 (element D).

  • Rear pointer is at index 1 (element G).

Visual Representation of the Circular Queue:

Let's visualize all the operations using a chart.

Step 1: Empty Queue

Queue: [ _, _, _, _, _ ]
front = -1, rear = -1

Step 2: Inserting A, B, C, D, E (Queue Full)

Queue: [ A, B, C, D, E ]
front = 0, rear = 4

Step 3: Dequeueing A, B, C

Queue: [ _, _, C, D, E ]
front = 3, rear = 4

Step 4: Inserting F, G (Wrap-Around)

Queue: [ F, G, _, D, E ]
front = 3, rear = 1

No comments:

Post a Comment

Subscribe to: Posts (Atom)