[SOLVED] Cop3502c assignment # 2-queues and linked list

Queues and Linked List
Read all the pages before starting to write your code
Overview
Your solution should follow a set of requirements to get credit.
What should you submit?
Write all the code in a single file main.c file and submit it on codegrade.
Please include the following commented lines in the beginning of your code to declare your authorship of the code:
/* COP 3502C Assignment 1
This program is written by: Your Full Name */

Caution!!!
What to do if you need clarification on the problem?
How to get help if you are stuck?

Movie Ticketing Queue (Queues)

Objective
Give practice implementing a queue via a linked list.
Give practice designing a functioning program without all function prototypes being given. Give practice following and implementing rules in a simulation.
Background Story

Upon arrival, a customer enters the name (a single string with max length 50 with all upper case letters) and number of tickets nt (0< nt ≤500) in the kiosk. The time of arrival t (0 ≤ t ≤ 109) is automatically recorded and is unique for each customer. After receiving this data, the system extracts the first letter of the name and gets its position p (0 ≤ p < 26) in the alphabet. For example, if the name is ADAM, then p for ADAM is 0. (A = 0, B = 1, …, Z = 25) Then the system automatically assigns a queue number q based on the following strategy:
1. The queue number q of a customer is p%13, if p%13≠0

Processing the customers
For the purposes of this problem, we assume that before the employees start processing customers, it is known in advance which of the queues will be non-empty at some point in time. Let the number of queues that receive at least 1 customer at some point in time equal k.

The k queues will be split amongst the b booths as follows: Each booth will receive customers from at least ⌊⌋ queues, where ⌊⌋, represents the greatest integer
less than or equal to x. (This is the technical way to define integer division for positive integers, mathematically. It’s called the floor function.)
Let’s consider a couple examples.
Let the non-empty queues be 1, 3, 4, 8, 9 and 12 and let there be 4 booths.
Thus, for this example, all customers from queues 1 and 3 will go to booth 1, all customers from queues 4 and 8 will go to booth 2, all customers from queue 9 will go to booth 3 and all customers from queue 12 will go to booth 4.
Booth 1: Queues 2, 3, 4, 6
Booth 2: Queues 7, 8, 9
Booth 3: Queues 10, 11, 12
The booths start processing customers at time t = 0. As soon as the first customer arrives at a booth, the employee at that booth starts processing her order. The processing time (in seconds) of a customer is calculated by 30 + number of tickets * 5. For example, if a customer buys 8 tickets, then it would take 30 + 8*5 = 70 seconds to process her transaction.

The Problem
Write a program that will reads in information about customers: customer name, number of tickets and time of arrival, and uses this information to determine which booth each customer will buy tickets from, and at what time they will complete their transaction.

Input
The first line will contain 2 positive integers, n (n ≤ 500,000), the number of customers purchasing tickets and b (b ≤ 12), the number booths operating on that day.

The following n lines will have information about each customer. These n lines will be sorted from earliest arrival time to latest arrival time. Each of these lines will start with the name of the customer, a single string of 1 to 50 uppercase letters, followed by a positive integer, nt (0< nt ≤500), representing the number of tickets the customer is buying. The row ends with another unique positive int t (t ≤ 109), representing the time, in seconds, from the beginning of the simulation that the customer steps into a
line. It is guaranteed that all of the check in times are unique and that all of the customer names are unique as well. These pieces of information will be separated by white space on the line. (Please just use scanf to read in the input!)
The Output
For each booth and for each customer served by the booth print the checkout time in the order that they get checked out from that booth.

For each booth, print a single line with the following format:

Booth Y

where Y represents the booth number, starting with 1.

For each customer who bought tickets at that booth, output a single line with the following format:

CUSTOMER from line X checks out at time T.

where CUSTOMER is the name of the customer checking out, X is the queue they came from before arriving at the booth, and T is the number of seconds AFTER the start of the simulation, that they complete checking out. (Thus, this time is the time they get called by the booth, plus the time it takes them to process.)

After each booth, output a blank line.

Sample Input
17 3
TANVIR 10 2
ARUP 8 4
TRAVIS 40 5
LILY 5 10
XIE 60 15
GUSTAVO 55 16
JOSE 20 23
DANIEL 20 27
VENU 24 28
ANEESHA 70 29
ANSH 6 35
GUHA 40 36
MEADE 60 38
MASON 12 40
NELLY 10 150
SHARON 5 5000
LEAVENS 2 9000

Sample Output
Booth 1
TANVIR from line 6 checks out at time 82.
ARUP from line 6 checks out at time 152.
TRAVIS from line 6 checks out at time 382.
GUSTAVO from line 6 checks out at time 687.
DANIEL from line 3 checks out at time 817.
ANEESHA from line 3 checks out at time 1197.
GUHA from line 6 checks out at time 1427.
SHARON from line 5 checks out at time 5055.

Booth 2
XIE from line 10 checks out at time 345.
JOSE from line 9 checks out at time 475.
VENU from line 8 checks out at time 625.
ANSH from line 8 checks out at time 685.
NELLY from line 9 checks out at time 765.

Booth 3
LILY from line 11 checks out at time 65.
MEADE from line 12 checks out at time 395.
MASON from line 12 checks out at time 485.
LEAVENS from line 11 checks out at time 9040.

Sample Explanation
There are 17 customers and 3 booths open.

For Arup, the relevant calculation is 0%13 = 0. This means he gets placed in the queue which has seen the fewest customers (but has seen at least one), which is queue 6.

1
2 3 4
5 6 7
8 9 10 11 12

DANIEL
TANVIR VENU
JOSE
XIE
LILY

ARUP

TRAVIS
GUSTAVO

1
2 3 4 5 6 7
8 9 10 11 12
DANIEL SHARON TANVIR VENU JOSE XIE
LILY MEADE
ANEESHA

ARUP ANSH
NELLY
LEAVENS
MASON

TRAVIS
GUSTAVO
GUHA

There are 8 queues (3, 5, 6, 8, 9, 10, 11, 12) to split amongst 3 booths. The assignment of queues to booths is as follows:

Booth 1: Queues 3, 5, 6
Booth 2: Queues 8, 9, 10
Booth 3: Queues 11, 12

A tabular format of the numbers is shown below. The booth meeting time of a customer depends on the previous check out time and arrival time. Then the customer’s check out time is calculated based on the formula mentioned above:
Name No. of tickets Arrival time Calculated
TANVIR 10 2 6 6 b1 2 82
ARUP 8 4 0 6 b1 82 152
TRAVIS 40 5 6 6 b1 152 382
LILY 5 10 11 11 b3 10 65
XIE 60 15 10 10 b2 15 345
GUSTAVO 55 16 6 6 b1 382 687
JOSE 20 23 9 9 b2 345 475
DANIEL 20 27 3 3 b1 687 817
VENU 24 28 8 8 b2 475 625
ANEESHA 70 29 0 3 b1 817 1197
ANSH 6 35 0 8 b2 625 685
GUHA 40 36 6 6 b1 1197 1427
MEADE 60 38 12 12 b3 65 395
MASON 12 40 12 12 b3 395 485
NELLY 10 150 0 9 b2 685 765
SHARON 5 5000 5 5 b1 5000 5055
LEAVENS 2 9000 11 11 b3 9000 9040

Implementation Restrictions

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, AND an integer field to store the size of the queue.

4. For all the above structs, feel free to add more fields if necessary.

5. There are several different ways to simulate the process described, but in some way shape or form, you should use the queue struct and the associated functions in the simulation.

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

7. Your queue must support the following operations and you must use them appropriately in your code. Each of these operations should run in O(1) time, meaning you should not need to traverse a linked list to do an operation mentioned below. :
a. Enqueue
b. Dequeue
c. Peek: Return the front of the queue WITHOUT dequeuing.
d. Empty (returns 1 if the queue is empty, 0 if it is not)
e. Size (returns the size of the list)

8. 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.

Important note and hints:
– This assignment is challenging not because it’s algorithmically difficult, but because there are many small rules that don’t necessarily have a “clean” implementation.
– This means you need to get started early!!! (On average, I think this assignment will take twice as long as assignment #1.)
– As suggested, you must implement a queue of customer using linked list like the way discussed in the class for int. That will be your main base.
– Have an array of static queue of size 12 and don’t forget to initialize each of them.
– Load all the data into the array of queues based on the rules.
– List all the nonempty queues into an array and then use the length of the array and number of booths to do the calculations which items from that array will belong to booth 1, booth 2, etc.
– A good idea would be calculating how many customers a booth will serve and run a loop to serve the customers belong to that booth.