Implementing simple queue using linked list

Question

I am trying to implement a queue that will hold people waiting in line for the bathroom but the thing is that the bathroom is for both men and women, but when men are present women can't enter and when women are present men can't enter. This is my problem. (Its a demo for one of my classes its not graded its barely academic)

I can insert people in the bathroom and into the queue (when a women tries to enter and there is a man in the bathroom she gets added to the queue) but I cant take the people from the queue and insert then into the bathroom when they are eligible to enter. Here is my code.

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

struct Node
{
    int Data;
    struct Node* next;
}*rear, *front;

void delQueue()
{
    struct Node *temp, *var=rear;
    if(var==rear)
    {
        rear = rear->next;
        free(var);
    }
    else
    printf("\nQueue Empty");
}

void push(int value)
{
    struct Node *temp;
    temp=(struct Node *)malloc(sizeof(struct Node));
    temp->Data=value;
    if (front == NULL)
    {
        front=temp;
        front->next=NULL;
        rear=front;
    }
    else
    {
        front->next=temp;
        front=temp;
        front->next=NULL;
    }
}

void display()
{ 
    struct Node *var=rear;
    if(var!=NULL)
    {
        printf("\nElements in queue are:  ");
        while(var!=NULL)
        {
            printf("\t%d",var->Data);
            var=var->next;
        }
    printf("\n");
    } 
    else
    printf("\nQueue is Empty\n");
}

int main() { 

int man_busy = 0;
int woman_busy = 0;
int input = 0;
int i = 0;

printf("\n(1) Man enters\n");
printf("(2) Woman enters\n");
printf("(3) Man leaves\n");
printf("(4) Woman leaves\n");


    printf("\nEmpty!\n");


    for(i=0; i<20; i++) {

        scanf("%d", &input);

        if(input == 1){
            if(woman_busy > 0){
                printf("Man Can't enter when women are present\n");
                printf("You will have to wait in the queue\n");
                push(input);
                display();
            }   
            else if(woman_busy == 0) {
                man_busy = man_busy + 1;    
                printf("Occupied By Man: %d\n", man_busy);
            }
        }
        else if(input == 2) {
            if(man_busy > 0){
                printf("Woman Can't enter when men are present\n");
                printf("You will have to wait in the queue\n");
                push(input);
                display();
            }   
            else if(man_busy == 0) {
                woman_busy = woman_busy + 1;    
                printf("Occupied By Woman: %d\n", woman_busy);
            }
        }
        else if(input == 3) {
            man_busy = man_busy - 1;
            if (man_busy == 0 && woman_busy == 0){
                printf("Empty!\n");
                delQueue();
                display();
            }
            else if (man_busy < 0) {
                printf("Invalid command!\n");
                man_busy = man_busy + 1;
            }           
            else {
                printf("Occupied By Man: %d\n", man_busy);
            }
        }
        else if(input == 4) {
            woman_busy = woman_busy - 1;
            if (man_busy == 0 && woman_busy == 0) {
                printf("Empty!\n");
                delQueue();
                display();
            }
            else if (woman_busy < 0) {
                printf("Invalid command!\n");
                    woman_busy = woman_busy + 1;
            }
            else {
                printf("Occupied By Woman: %d\n", woman_busy);
            }
        }
    }
        return 0;

}

Do men jump ahead of women waiting in the queue if a man is already in the bathroom, and v.v.? — Will A
– Will A, Commented May 3, 2013 at 23:51
yes men jump the line and enter if there are men already in the bathroom, and it works both ways — user2133160
– user2133160, Commented May 3, 2013 at 23:53

Sudhee · Accepted Answer · 2013-05-04 06:13:03Z

1

You need a routine dequeue (I recommend function names enqueue and dequeue, as push /pop nomenclature is used for stack).

When you hit the condition bathroom empty, and if queue is not empty, you need to dequeue all elements of type of first element (ie, all men or all women based on whether it was a man or woman who is first in queue) and put them inside the bathroom. Repeat this when ever bathroom is empty.

answered May 4, 2013 at 6:13

Sudhee

7146 silver badges12 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Grzegorz Piwowarek Over a year ago

pop() and push() are fine for queues

Grzegorz Piwowarek · Accepted Answer · 2013-05-04 06:53:30Z

If You want to remove people from the queue You I'd have to chop off the desired Node and glue the list and set "rear" and "front" again when needed. In order to do this You will have to keep track of the previous node.

Case#1:

1<-2<-3-<4 Rear:1 Front:4

We want to chop off 3 and the previous node is 2.

1<-2<- |3| -<4 Rear:1 Front:4

and then glue previous->next to the chopped_off->next

1<-2<-----4 Rear:1 Front:4

Also there won't be any need for glueing anything if the desired element is pointed to by "rear" or "front".

Case#2:

1<-2<-3-<4 Rear:1 Front:4

We want to chop off 1 and there is not any preceding node!

|1| <-2<-3-<4 Rear:1 Front:4

Resetting Rear

2<-3-<4 Rear:2 Front:4

Bathroom can handle infinite number of people? If Yes You will be always chopping off the element pointed by rear. and there is no need for saving the previous node. That would be surprisingly easy because You would have to flush the whole queue because at every single moment there are exclusively men or women in the queue and when bathroom is empty they all would simply walk in.

If You are dealing with some kind of menu choice never use if-elseif-else. If there is a big choice of options You're hurting people. Learn about switch-case statements. They are designed for things like this. It will make Your work easier.
You should begin Your variables' names with a lower case. That's the convention and it might confuse people if You do not follow it.
It would be a good idea to have an insight into the whole queue after each operation.
It would be a good idea to implement something that could distinguish different men and women in the queue for debugging purposes. You'd like to check if correct people are removed from the queue.
#include <time.h>?

Collectives™ on Stack Overflow

Implementing simple queue using linked list

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related