0

I need to enqueue a whole struct customer in the queue - I think. This is my homework. I am not asking for an answer. I need a mentor to explain what I am missing and what I have right per the assignment. I am very new. This is my second program. see below... thanks btw.

A store is having customers queue in several lines. After the cashier finishes helping a customer, he will survey all of the lines that are currently queued. Of all of the customers at the front of those lines, he’ll take the customer who has the fewest number of items. If there are two customers with the same number of items, he’ll take the customer who comes from the smaller line number. The lines are numbered 1 through 12. It’s possible that some of these lines will be empty, in which case these lines are ignored. The number of seconds the store clerk takes to check out a customer is 30 plus 5 times the number of items. Thus, if a customer has 8 times, the clerk would check her out in 30 + 8*5 = 70 seconds. The Problem You will write a program that reads in information about customers: which line they go to the back of (1 through 12), at what time (in seconds) they enter that line, and the number of items they have, and determines at what time each customer will check out.

Sample Input:

2

5
10 1 STEVEN 12
12 6 AHMAD 8
13 1 JENNY 40
22 6 JERMAINE 39
100000 12 AMALIA 53

6
100 1 A 100
200 2 B 99
300 3 C 98
400 4 D 97
500 5 E 96
600 6 F 95

Sample Output:

STEVEN from line 1 checks out at time 100.
AHMAD from line 6 checks out at time 170.
JERMAINE from line 6 checks out at time 395.
JENNY from line 1 checks out at time 625.
AMALIA from line 12 checks out at time 100295.

A from line 1 checks out at time 630.
F from line 6 checks out at time 1135.
E from line 5 checks out at time 1645.
D from line 4 checks out at time 2160.
C from line 3 checks out at time 2680.
B from line 2 checks out at time 3205.

Implementation Restrictions:

  1. You must create a struct that stores information about a customer (name, number of items, line number, time entering line). Note that the storage of the line number is redundant, but is designed to ease implementation.

  2. You must create a node struct for a linked list of customers. This struct should have a pointer to a customer struct, and a pointer to a node struct.

  3. You must create a struct to store a queue of customers. This struct should have two pointers – one to the front of the queue and one to the back.

  4. You must implement all of the lines that form as an array of size 12 (stored as a constant) of queues.

  5. You must dynamically allocate memory as appropriate for linked lists.

  6. Your queue must support the following operations: a. Enqueue b. Dequeue c. Return the front of the queue WITHOUT dequeing d. Empty (returns 1 if the queue is empty, 0 if it is not)

  7. You must free memory appropriately. Namely, when you dequeue, you’ll free memory for a node, but you will NOT free memory for the customer. You will free this memory a bit later right after you calculate when that customer will finish checking out.

  8. Due to the nature of the problem, when you process the input, you can add everyone into their appropriate lines right at the beginning, before checking anyone out.

This wouldn’t work in all simulations (some of which you have to do in time order), but because there is ONLY one check out line, you can get away with it. The only thing you have to be cognizant about is that when you select a line, if the current time is, 100 for example, and three lines have customers who arrived before time 100 and the other lines have customers in the front who arrived AFTER time 100, you have to ignore the customers in those lines who arrived after time 100. In the case that all the lines have customers who arrived after time 100, you would take the line which has a customer who arrived first. You are guaranteed no ties for arrival time so this would be unique.

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

#define TRUE 1
#define FALSE 0

typedef char customerName[9];

typedef struct node
{
    int data;
    struct node *next;
}node;

typedef struct queue
{
    int size;
    int front;
    int back;
    int *array;
    unsigned capacity;

}queue;

typedef struct customer
{
    customerName name;//1-9 upper case letters
    int lineNumber;
    int time;
    int numberItems;
} customer;


int isEmpty(queue *q);
void initialize(queue *q);


void initialize(queue *q)
{
    q->size = 0;
    q->front = -1;
    q->back = -1;
}

int isEmpty(queue *q){
    return (q->size == 0);//returns 1 if empty or 0 if false
}

int isFull(queue *q)
{  return (q->size == q->capacity);  }

void enqueue(queue *q, int item)
{
    if (isFull(q))
        return;
    q->back = (q->back + 1)%q->capacity;
    q->array[q->back] = item;
    q->size = q->size + 1;
}

int dequeue(queue *q)
{
    if (isEmpty(q))
        return 0;
    int item = q->array[q->front];
    q->front = (q->front + 1)%q->capacity;
    q->size = q->size - 1;
    return item;
}

int front(queue* q){
    if(isEmpty(q)){
        return 0;
    }
    return q->array[q->front];
}


int main(int argc, const char * argv[]) {

    int testCases = 0;
    scanf("%d", &testCases);

    if(testCases > 0 && testCases <= 25){//shortcircuiting???

    while (testCases--){

        queue *q;
        q = malloc(sizeof(queue));
        initialize(q);// starting new queue

        int numCustomers;
        scanf("%d", &numCustomers);

        if(numCustomers < 0 || numCustomers > 11){
            return 0;
        }

        struct customer newCustomer[1];

        for ( int i = 0; i < numCustomers; i++){
            scanf("%d", &newCustomer[i].time);
            scanf("%d", &newCustomer[i].lineNumber);
            scanf("%s", newCustomer[i].name);
            scanf("%d", &newCustomer[i].numberItems);
            enqueue(q, newCustomer[i].time);
            enqueue(q, newCustomer[i].lineNumber);

        }




        for ( int i = 0; i < numCustomers; i++){
            printf("%d %d %s %d\n", newCustomer[i].time, newCustomer[i].lineNumber, newCustomer[i].name, newCustomer[i].numberItems);

               }


    }
}
    return 0;
}

Here is my latest code:

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

#define TRUE 1
#define FALSE 0
#define NUMLINES 12
int currtime = 0;

typedef char customerName[9];

typedef struct node
{
    int data;
    struct customer* data;
    struct node* next;

}node;

typedef struct queue
{
    node* front;
    node* back;
}queue;

typedef struct customer
{
    customerName name;//1-9 upper case letters
    int lineNumber;
    int time;
    int numberItems;
} customer;

typedef struct node *newNode;//define a node pointer

node createNode()
{
    newNode temp;//declare node
    temp = (newNode)malloc(sizeof(struct node));//allocate memory
    temp->next = NULL;//next point to null
    return *temp;// return the new node

}

struct queue* createQueue()
{
    struct queue* q = (struct queue*)malloc(sizeof(struct queue));
    q->front = q->back = NULL;
    return q;
}

int isEmpty(queue *q){
    return (q->back == NULL);//returns 1 if empty or 0 if false
}

void enqueue(queue *q, customer* data)
{
        // Create a new LL node
       struct node* temp = createNode(data);

       // If queue is empty, then new node is front and back both
       if (q->back == NULL) {
           q->front = q->back = temp;
           return;
       }

       // Add the new node at the end of queue and change back
       q->back->next = temp;
       q->back = temp;
}

void dequeue(queue *q)
{
     if (q->front == NULL)
           return;

       // Store previous front and move front one node ahead
       struct node* temp = q->front;
       q->front = q->front->next;

       // If front becomes NULL, then change rear also as NULL
       if (q->front == NULL)
           q->back = NULL;

       free(temp);
}

int front(queue* q){
    if(isEmpty(q)){
        return 0;
    }
    return q->front;
}

int main(int argc, const char * argv[]) {

    int testCases = 0;
    scanf("%d", &testCases);

    if(testCases > 0 && testCases <= 25){//shortcircuiting???

    while (testCases--){

        queue *q;
        q = malloc(sizeof(queue));
        initialize(q);// starting new queue

        int numCustomers;
        scanf("%d", &numCustomers);

        if(numCustomers < 0 || numCustomers > 11){
            return 0;
        }

        struct customer newCustomer[11];

        for ( int i = 0; i < numCustomers; i++){
            scanf("%d", &newCustomer[i].time);
            scanf("%d", &newCustomer[i].lineNumber);
            scanf("%s", newCustomer[i].name);
            scanf("%d", &newCustomer[i].numberItems);
            enqueue(q, newCustomer[i].time);
            enqueue(q, newCustomer[i].lineNumber);

        }

        for ( int i = 0; i < numCustomers; i++){
            printf("%d %d %s %d\n", newCustomer[i].time, newCustomer[i].lineNumber, newCustomer[i].name, newCustomer[i].numberItems);

               }

    }
}
    return 0;
}

int main(int argc, const char * argv[]) {

    int testCases = 0;
    scanf("%d", &testCases);

    if(testCases > 0 && testCases <= 25){//shortcircuiting???

    while (testCases--){

        queue *q;
        q = malloc(sizeof(queue));
        qinit(q);// starting new queue

        int numCustomers;
        scanf("%d", &numCustomers);

        if(numCustomers < 0 || numCustomers > 11){
            return 0;
        }

        queue* customerArray = (queue*) malloc(sizeof(queue) * 12);

        for ( int i = 0; i < numCustomers; i++){

            customer* newCustomer = (customer*) malloc(sizeof(customer));

            scanf("%d", &(newCustomer->time));
            scanf("%d", &(newCustomer->lineNumber));
            scanf("%s", newCustomer->name);
            scanf("%d", &(newCustomer->numberItems));
            enqueue(&customerArray[newCustomer->lineNumber - 1], newCustomer);
        }


        int totalTime = INT_MAX;

        for(int i=0;i<12;i++)
        {
        customer* frontCustomer = qfront(&customerArray[i]);
         if(totalTime < frontCustomer->time)
            {
                totalTime = frontCustomer->time;
            }
            free(frontCustomer);
         }

       while(numCustomers--) {

           int customerToCheckOutLine = 0; int minNumberOfItems = INT_MAX;

        for( int j=11 ; j>=0; j--){

            customer* frontCustomer = qfront(&customerArray[j]);
            if(frontCustomer->time <= totalTime)
            {
                if(frontCustomer->numberItems < minNumberOfItems)
                {
                    customerToCheckOutLine = frontCustomer->lineNumber;
                    minNumberOfItems = frontCustomer->numberItems;
                }
                free(frontCustomer);
            }
        }


        customer* customerToCheckOut = qfront(&customerArray[customerToCheckOutLine -1 ]);
        totalTime += 30;
        totalTime += (customerToCheckOut->numberItems) * 5;
           dequeue(&customerArray[customerToCheckOutLine - 1]);
       }
        free(customerArray);

    }
}
    return 0;
}
Improve this question
3
  • 2
    It would be best if you could provide details on what you have specifically tested and what doesn't work (specific errors or other more specific question) rather than asking for general guidance. This site really is for specific questions. Did you run your program and encounter any specific issues? Commented Jun 2, 2020 at 21:15
  • I just learned about GDB yesterday. The teacher never mentioned it. I narrowed it down to not understanding how to enqueue the customer struct into the enqueue function. Commented Jun 3, 2020 at 16:13
  • 2
    On SO, the correct way to post updated code is to append it in a new code block instead of editing the original. This keeps continuity and allows the question to continue to make sense. Otherwise, sometimes, such a revision can semi-invalidate answers [because they're based on the original/unmodified code]. So, I've rolled back your edit and added the updated code in a second code block. Commented Jun 4, 2020 at 20:18

1 Answer 1

Reset to default
1

Your queue related functions look okay.

But, there are some bugs and the code needs refactoring to handle more things.

Your queue element array should be of type node * instead of int *.

You need the newCustomer array to be of length numCustomers (i.e. not 1).

At present, you have a single queue. But, you need an array of queues, one for each line, so an array length of 12.

When you queue a customer, you must select the queue [from the array of queues] based on the line number the customer is getting on.

Here's a biggie:

You can't queue two separate entries, one being time and the other being lineNumber. Well, you can I guess, but it's messy.

The way I'd do it is to change the data element of the node struct to be a pointer to the customer record. That way, every bit of data you need to determine the servicing order is [already] in the customer struct.

Anyway, here's some refactored code.

Per your request, it's not a solution, but some sample code as a basis for implementing the above fixes/suggestions.

You still have to change the queue struct and all queue related functions (if you decide to change the struct as I've suggested).

And, you still have to implement the selection/ordering process. And, the cleanup/deallocation.

This won't compile as is, because it's a "suggestion", but here it is:

 typedef char customerName[9];

typedef struct customer {
    customerName name;                  // 1-9 upper case letters
    int lineNumber;
    int time;
    int numberItems;
} customer;

typedef struct node {
#if 0
    int data;
#else
    customer *data;
#endif
    struct node *next;
} node;

typedef struct queue {
    int size;
    int front;
    int back;
#if 0
    int *array;
#else
    node *array;
#endif
    unsigned capacity;
} queue;

#if 1
#define NUMLINES        12
queue queue_list[NUMLINES];
#endif

int isEmpty(queue *q);
void initialize(queue * q);

void
initialize(queue *q)
{
    q->size = 0;
    q->front = -1;
    q->back = -1;
}

int
isEmpty(queue *q)
{
    return (q->size == 0);              // returns 1 if empty or 0 if false
}

int
isFull(queue *q)
{
    return (q->size == q->capacity);
}

void
enqueue(queue *q, int item)
{
    if (isFull(q))
        return;
    q->back = (q->back + 1) % q->capacity;
    q->array[q->back] = item;
    q->size = q->size + 1;
}

int
dequeue(queue *q)
{
    if (isEmpty(q))
        return 0;
    int item = q->array[q->front];

    q->front = (q->front + 1) % q->capacity;
    q->size = q->size - 1;
    return item;
}

int
front(queue *q)
{
    if (isEmpty(q)) {
        return 0;
    }
    return q->array[q->front];
}

int
main(int argc, const char *argv[])
{
    queue *q;

    int testCases = 0;

    scanf(" %d", &testCases);

    // NOTE/BUG: you need a separate queue for each line
    for (int qidx = 0;  qidx < NUMLINES;  ++qidx) {
        q = &queue_list[qidx];
        initialize(q);
    }

    // shortcircuiting???
    if (testCases > 0 && testCases <= 25) {
        while (testCases--) {
#if 0
            queue *q;
#endif

#if 0
            q = malloc(sizeof(queue));
            initialize(q);              // starting new queue
#endif

            int numCustomers;

            scanf(" %d", &numCustomers);

            if (numCustomers < 0 || numCustomers > 11) {
                return 0;
            }

            // NOTE/BUG: you need a larger array of customers
#if 0
            struct customer newCustomer[1];
#else
            struct customer newCustomer[numCustomers];
#endif

            for (int i = 0; i < numCustomers; i++) {
                customer *cust = &newCustomer[i];

                scanf(" %d", &cust->time);
                scanf(" %d", &cust->lineNumber);
                scanf(" %s", cust->name);
                scanf(" %d", &cust->numberItems);

                // NOTE/BUG: customer must be queued to the queue for the
                // line number they're on
                // NOTE/BUG: queue a single entry for each customer
#if 0
                enqueue(q, cust->time);
                enqueue(q, cust->lineNumber);
#else
                q = &queue_list[cust->lineNumber - 1];
                enqueue(q,cust);
#endif
            }

            for (int i = 0; i < numCustomers; i++) {
                printf("%d %d %s %d\n",
                    newCustomer[i].time,
                    newCustomer[i].lineNumber,
                    newCustomer[i].name,
                    newCustomer[i].numberItems);
            }
        }
    }

    return 0;
}

UPDATE:

woah, this is amaze balls. thank you so much. I think the assignment is confusing because he says the assignment is queues with linked list not an array but like you said it needs to be an array of queues. that would suggest multiple entries into a single line. so in a sense this is both an queues with linked lists and array?

You need an array of queues, indexed by linenumber. This is not to be confused with the q->array element within the queue, which is different.

I just completed a working and tested version [for myself, because I'm crazy that way :-)]. I had the same confusion.

The queue is a ring queue [with array]. If the array pointer is a customer *, I couldn't find a good way to use node. The only way to do it would be to convert queue into a linked list header struct. That would require queue to be restructured [along will all the access functions for it ;-)].

But, before doing that, if we keep the array/ring method, then initialize needs to take a capacity arg (called with initialize(q,numCustomer);). And, it needs to do (e.g.) q->array = realloc(q->array,sizeof(customer *) * capacity);

And, enqueue needs a fix: the increment of q->back needs to be moved after the q->array[q->back] = item;. Currently, there is an off by one gap.

To convert to a linked list:

The structs change a bit:

typedef struct node {
    customer *data;
    struct node *next;
} node;

typedef struct queue {
    node *front;
} queue;

You have an isFull function. That's not part of the requirements. If we switch queue into a linked list header for a list of node, it isn't even relevant/meaningful since, now, there is no maximum [as there was with q->capacity].

Now, when doing enqueue(q,cust);, the function would malloc a new node and append it to the end of the linked list. And, setup of (e.g.) newnode->next and newnode->data = cust;

When doing dequeue, it pops off the front element (a node), does cust = curnode->data;, then free(curnode), and returns cust.

Based on my rereading the requirements, I believe that this is what's required, and actually makes sense of all of them.

In other words, you can implement a queue with just a linked list (vs. what you did which was a ring queue with array--which I've also done in the past).

the ordering process is part of the reason I am so confused. I don't know where to do this. The list is already ordered by time the customer went to check out. I just need to calculate the total cashier time.there is only one cashier so all the people are served in order of entering the queue.

This is a bit tricky. You have to have a curtime global to keep track of the current time. Initially, this has to be set to the minimum of all cust->time values.

As you loop through all queues [i.e. waiting lines] to look at the first customer on the line, you have to do the following:

You skip the queue if it's empty.

You skip any customer if they have an arrival date in the future (i.e. cust->time > curtime).

Now you can "select" the customer. You need the find "best" customer [for the next one to be serviced]. That is, the one with the smallest order. The 2nd criteria of: with a tie, the customer with the lowest line number wins is handled automatically if you only update the "best" value if (cust->numberItems < best->numberItems) because we're traversing the queue_list array from low to high.

Then, service the "best" customer (i.e. print the message). Then, increment curtime by the elapsed time it takes to service the customer.

Repeat this until all queues are empty.

But, there is one gotcha. It happens with AMALIA.

The arrival time for this customer is so far in the future that the customer selection will fail to find any "best" customer because amalia->time is greater than curtime. Thus, it seems like AMALIA is not ready to be serviced.

So, if the selection fails (i.e. best is null), we have to loop through all front customers [again] and set curtime to the minimum of all their arrival times.

Then, we rescan/reselect for "best". Now, AMALIA will be selected

UPDATE #2:

in your example I don't understand what the #elseif etc. what are those? other than the obvious, I have never seen this

The lines starting with #if are preprocessor statements [just like #include, #ifdef, #else, #endif

The preprocessor is used to include/exclude code at compile time (vs using a real if language statement). You can think of the preprocessor as a separate pass before compilation that performs the conditional actions before passing the resultant file to the compile stage.

In my examples, I'm using them to show old code [yours] vs. new code [mine]:

#if 0
    // old code ...
    x = 1;
#else
    // new code ...
    x = 2;
#endif

When compiled, the old code is excluded, the new code is included as if we had done:

    // new code ...
    x = 2;

This is a useful technique in general. It allows you to "comment out" code that you suspect might be a bug. Or, for debug printf code. Or, you have working code (the "old" code), but you want to try something possibly cleaner or more efficient (the "new" code). You can flip back and forth during development just by changing #if 0 to #if 1 or vice versa

You can see the intermediate file by doing:

cc -E -P -o myfile.i myfile.c

Later on, when your code is [fully ;-)] debugged, you could hand edit out the #if cases you don't need/want.

can you do that same kind of example but for the linked list only implementation? or is that asking too much? :) why is there only a *front and no back of the list?

For a simple singly linked list, we only truly need a head/front pointer.

We don't need size because the empty case is: q->front == NULL. size is primarily useful if we had to sort the linked list (it saves a pass on the list to get the number of elements).

Using q->back adds a slight degree of complexity. It's a speedup when appending to the queue/list. If we don't have it, we find the last element in the list by traversing it. If we have back, that is the last element.

A singly linked list is sufficient for your use case. But, just for completeness, I've added doubly linked list support. We add a prev element to node [the backwards link].

Below, I've coded up the linked list structs and functions. To allow you to see the various modes, each optional element is wrapped in preprocessor #if/#endif pairs to include/exclude code, based on setting the given option on/off

DLINK [doubly linked list] is off by default

To enable it on a one time basis, you could do:

cc -DDLINK=1 -c myfile.c

Likewise for other options.

Anyway, here's the queue code based on a linked list:

// customer record
typedef char customerName[9];
typedef struct customer {
    customerName name;                  // 1-9 upper case letters
    int lineNumber;                     // line number customer gets on
    int time;                           // arrival time at line
    int numberItems;                    // number of items customer has
} customer;

// 1=use queue q->back
// need this for _doubly_ linked list
// speedup for append to end of queue for singly linked
#ifndef QBACK
#define QBACK       1
#endif

// 1=use queue q->size
#ifndef QSIZE
#define QSIZE       1
#endif

// 1=use doubly linked list
#ifndef DLINK
#define DLINK       0
#endif

// force QBACK on if doing doubly linked list
#if DLINK
#undef QBACK
#define QBACK       1
#endif

// [singly linked] queue element
typedef customer *qitem;
typedef struct node {
    qitem data;                         // pointer to actual data
    struct node *next;                  // forward pointer to next item
#if DLINK
    struct node *prev;                  // backward pointer to previous item
#endif
} node;

// queue definition (singly linked list)
// NOTE:
typedef struct queue {
    node *front;                        // pointer to first node in list
#if QBACK
    node *back;                         // pointer to last node in list
#endif
#if QSIZE
    int size;                           // current number of elements in list
#endif
} queue;

// list of queues (indexed by lineNumber - 1)
#define NUMLINES        12
queue queue_list[NUMLINES];

// qinit -- initialize/reset queue
void
qinit(queue *q)
{

    q->front = NULL;

#if QSIZE
    q->size = 0;
#endif

#if QBACK
    q->back = NULL;
#endif
}

// qempty -- returns 1 if empty or 0 if false
int
qempty(queue *q)
{
    // NOTE: size really isn't needed
#if 0
    return (q->size == 0);
#else
    return (q->front == NULL);
#endif
}

// enqueue -- append element to end of queue
void
enqueue(queue *q, qitem data)
{
    node *newnode;
    node *prev;

    newnode = malloc(sizeof(node));
    newnode->next = NULL;
    newnode->data = data;

    // NOTE: this is the only place where back is a speedup
#if QBACK
    prev = q->back;
#else
    // what we have to do find the back of the queue with only a front pointer
    prev = NULL;
    for (node *cur = q->front;  cur != NULL;  cur = cur->next)
        prev = cur;
#endif

    // append to tail of list
    if (prev != NULL)
        prev->next = newnode;

    // add to end of empty list
    else
        q->front = newnode;

#if DLINK
    newnode->prev = prev;
#endif

#if QBACK
    q->back = newnode;
#endif

#if QSIZE
    q->size += 1;
#endif
}

// dequeue -- dequeue from the front of the queue
qitem
dequeue(queue *q)
{
    node *curnode;
    qitem data;

    do {
        curnode = q->front;

        // bug out if list is empty
        if (curnode == NULL) {
            data = NULL;
            break;
        }

        // get node's data value (e.g. pointer to customer struct)
        data = curnode->data;

#if QBACK
        node *back = q->back;
#if DLINK
        curnode->prev = back;
#endif
        if (curnode == back)
            q->back = curnode->next;
#endif

        q->front = curnode->next;

#if QSIZE
        q->size -= 1;
#endif

        // release the node's storage back to the heap
        free(curnode);
    } while (0);

    return data;
}

// qfront -- peek at front of queue
qitem
qfront(queue *q)
{
    node *curnode;
    qitem data;

    curnode = q->front;
    if (curnode != NULL)
        data = curnode->data;
    else
        data = NULL;

    return data;
}

UPDATE #3:

so my main function has a memory leak and I cannot find it. I am trying to learn Valgrind and gdb but there is a learning curve. My Valgrind outran is like 90,000 characters for some reason and doesn't say hey I have a memory leak. I don't even know what line. I appended my new main to the bottom of the above code.

A few issues:

You malloc the q pointer at the top of the outer while (testCases--) loop but do not free it.

But, as I mentioned, you need an array of queues [which can be a fixed array] and you've already done that.

But, q was your original/legacy code. The rest of your code no longer uses q. You just forgot to remove it.

You are now using customerArray instead. But, you are not calling qinit on each array element, so you could have a random data in each.

In the problem definition, the number of customer lines is fixed at 12, so you really don't need to malloc and free it. That's why I used a global array instead.

You have a bug in your totalTime calculation loop. You're doing a free of the customer record. So, the record is no longer valid in the loop below it.

And, in that second loop, you're doing a second free of the same struct. So, at present, this is a "double free" bug. The second loop is actually the correct place for the free [not the first loop]

This program is ambitious for a second ever assignment, so you're "being thrown out into the middle of the lake and being asked to swim to shore".

I would have expected a few more intermediate steps/programs before trying to code up this one.

When starting out, as you are, sometimes it's as important to study working code as it is to write it from scratch.

So, spoiler alert, here's my final, fully working code:

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

#define TIME_PAST       -1              // infinite time in the past
#define TIME_FUTURE     INT_MAX         // infinite time in the future
int curtime;                            // current time

// customer record
typedef char customerName[9];
typedef struct customer {
    customerName name;                  // 1-9 upper case letters
    int lineNumber;                     // line number customer gets on
    int time;                           // arrival time at line
    int numberItems;                    // number of items customer has
} customer;

// 1=use queue q->back
// need this for _doubly_ linked list
// speedup for append to end of queue for singly linked
#ifndef QBACK
#define QBACK       1
#endif

// 1=use queue q->size
#ifndef QSIZE
#define QSIZE       1
#endif

// 1=use doubly linked list
#ifndef DLINK
#define DLINK       0
#endif

// force QBACK on if doing doubly linked list
#if DLINK
#undef QBACK
#define QBACK       1
#endif

// [singly linked] queue element
typedef customer *qitem;
typedef struct node {
    qitem data;                         // pointer to actual data
    struct node *next;                  // forward pointer to next item
#if DLINK
    struct node *prev;                  // backward pointer to previous item
#endif
} node;

// queue definition (singly linked list)
// NOTE:
typedef struct queue {
    node *front;                        // pointer to first node in list
#if QBACK
    node *back;                         // pointer to last node in list
#endif
#if QSIZE
    int size;                           // current number of elements in list
#endif
} queue;

// list of queues (indexed by lineNumber - 1)
#define NUMLINES        12
queue queue_list[NUMLINES];

// qinit -- initialize/reset queue
void
qinit(queue *q)
{

    q->front = NULL;

#if QSIZE
    q->size = 0;
#endif

#if QBACK
    q->back = NULL;
#endif
}

// qempty -- returns 1 if empty or 0 if false
int
qempty(queue *q)
{
    // NOTE: size really isn't needed
#if 0
    return (q->size == 0);
#else
    return (q->front == NULL);
#endif
}

// enqueue -- append element to end of queue
void
enqueue(queue *q, qitem data)
{
    node *newnode;
    node *prev;

    newnode = malloc(sizeof(node));
    newnode->next = NULL;
    newnode->data = data;

    // NOTE: this is the only place where back is a speedup
#if QBACK
    prev = q->back;
#else
    // what we have to do find the back of the queue with only a front pointer
    prev = NULL;
    for (node *cur = q->front;  cur != NULL;  cur = cur->next)
        prev = cur;
#endif

    if (prev != NULL)
        prev->next = newnode;
    else
        q->front = newnode;

#if DLINK
    newnode->prev = prev;
#endif

#if QBACK
    q->back = newnode;
#endif

#if QSIZE
    q->size += 1;
#endif
}

// dequeue -- dequeue from the front of the queue
qitem
dequeue(queue *q)
{
    node *curnode;
    node *nextnode;
    qitem data;

    do {
        // get the first node
        curnode = q->front;

        // if none, return null data
        if (curnode == NULL) {
            data = NULL;
            break;
        }

        // get the data payload
        data = curnode->data;

        // point to the next node (i.e. second node)
        nextnode = curnode->next;

#if QBACK
        node *back = q->back;
#if DLINK
        curnode->prev = back;
#endif
        if (curnode == back)
            q->back = nextnode;
#endif

        q->front = nextnode;

#if QSIZE
        q->size -= 1;
#endif

        free(curnode);
    } while (0);

    return data;
}

// qfront -- peek at front of queue
qitem
qfront(queue *q)
{
    node *curnode;
    qitem data;

    curnode = q->front;
    if (curnode != NULL)
        data = curnode->data;
    else
        data = NULL;

    return data;
}

// custfind -- find next customer to serve
customer *
custfind(void)
{
    int pass;
    int qidx;
    queue *q;
    int mintime;
    int moreflg;
    customer *cust;
    customer *best;

    // pass 1:
    // - remember the minimum time
    // - find best using curtime
    for (pass = 1;  pass <= 2;  ++pass) {
        best = NULL;
        mintime = TIME_FUTURE;
        moreflg = 0;

        // scan all queues -- examine _first_ customer on each line
        for (qidx = 0;  qidx < NUMLINES;  ++qidx) {
            q = &queue_list[qidx];

            // get first customer on current line
            cust = qfront(q);
            if (cust == NULL)
                continue;

            // remember that there is at least _one_ customer waiting
            moreflg = 1;

            // remember the minimum time
            if (cust->time < mintime)
                mintime = cust->time;

            // has the customer actually arrived yet? -- skip if not
            if (cust->time > curtime)
                continue;

            // no previous "best" customer -- set from current
            if (best == NULL) {
                best = cust;
                continue;
            }

            // get better customer (has fewer items to check out)
            if (cust->numberItems < best->numberItems) {
                best = cust;
                continue;
            }
        }

        // no more customers
        if (! moreflg)
            break;

        // found a best match
        // dequeue and free node
        if (best != NULL) {
            q = &queue_list[best->lineNumber - 1];
            dequeue(q);
            break;
        }

        // no best match found
        // all customers are in the future [based on curtime]
        // set new current time based on minimum time of all remaining customers
        // the second pass _will_ find at least one after we do this
        curtime = mintime;
    }

    return best;
}

// custdo -- check out customer
void
custdo(customer *cust)
{
    int elap;

    // current time has to be _at least_ the arrival time
    if (curtime < cust->time)
        curtime = cust->time;

    // get amount of time it takes to service this customer
    elap = 0;
    elap += 30;
    elap += cust->numberItems * 5;

    // set current time after servicing the customer
    curtime += elap;

    printf("%s from line %d checks out at time %d.\n",
        cust->name,cust->lineNumber,curtime);

    // release the customer record storage
    free(cust);
}

// testcase -- process a test case
void
testcase(FILE *fi)
{
    queue *q;
    customer *cust;

    // reset all queues
    // NOTE: probably not required
    for (int qidx = 0;  qidx < NUMLINES;  ++qidx) {
        q = &queue_list[qidx];
        qinit(q);
    }

    // get number of customers for this case
    int numCustomers;
    fscanf(fi," %d", &numCustomers);

    // read in all customer records for this test case
    for (int icust = 0;  icust < numCustomers;  ++icust) {
        cust = malloc(sizeof(*cust));

        fscanf(fi," %d", &cust->time);
        fscanf(fi," %d", &cust->lineNumber);
        fscanf(fi," %s", cust->name);
        fscanf(fi," %d", &cust->numberItems);

        // add customer to appropriate line/queue
        q = &queue_list[cust->lineNumber - 1];
        enqueue(q,cust);
    }

    // set current time to [way in the] past
    curtime = TIME_PAST;

    while (1) {
        // find the next customer
        cust = custfind();

        // no more customers
        if (cust == NULL)
            break;

        // service customer
        custdo(cust);
    }
}

int
main(int argc, char **argv)
{
    char *ifile;
    FILE *fi;

    --argc;
    ++argv;

    // open the input file
    if (argc > 0)
        ifile = *argv;
    else
        ifile = "input.txt";
    fi = fopen(ifile,"r");
    if (fi == NULL) {
        perror(ifile);
        exit(1);
    }

    // get number of test cases
    int testCases;
    fscanf(fi," %d", &testCases);

    // process all test cases
    for (;  testCases > 0;  --testCases)
        testcase(fi);

    fclose(fi);

    return 0;
}
Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

woah, this is amaze balls. thank you so much. I think the assignment is confusing because he says the assignment is queues with linked list not an array but like you said it needs to be an array of queues. that would suggest multiple entries into a single line. so in a sense this is both an queues with linked lists and array?
the ordering process is part of the reason I am so confused. I don't know where to do this. The list is already ordered by time the customer went to check out. I just need to calculate the total cashier time.there is only one cashier so all the people are served in order of entering the queue. 0-11.
thank you. Yes I have to use just the link list with the customer struct.
in your example I don't understand what the #elseif etc. what are those? other than the obvious, I have never seen this
can you do that same kind of example but for the linked list only implementation? or is that asking too much? :) why is there only a *front and no back of the list
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.