Assignment Chef icon Assignment Chef
All English tutorials

Programming lesson

Mastering Queues and Linked Lists: Build a Movie Ticketing Simulation in C

Learn how to implement queues using linked lists in C by building a movie ticketing simulation. Step-by-step guide with code examples and real-world analogies.

queues in C linked list queue implementation COP3502C assignment 2 movie ticketing simulation FIFO queue C programming data structures tutorial C programming project queue using linked list code customer service queue simulation booth assignment algorithm C dynamic memory allocation queue data structure explained coding assignment help linked list enqueue dequeue ticket queue system C programming for beginners

Introduction to Queues and Linked Lists in C

Queues are fundamental data structures that follow the First-In-First-Out (FIFO) principle. They are used everywhere: from printer spools to customer service lines. In this tutorial, you'll learn how to implement a queue using a linked list in C, a common assignment in courses like COP3502C. We'll build a movie ticketing system that simulates customers arriving, joining queues, and being served by multiple booths. This hands-on project will solidify your understanding of dynamic memory allocation, pointer manipulation, and queue operations.

Why Use a Linked List for a Queue?

Arrays can implement queues, but they have fixed size and inefficient dequeue operations (shifting elements). A linked list grows dynamically and allows O(1) enqueue and dequeue when we maintain pointers to head and tail. In our ticketing simulation, we don't know the number of customers in advance, so a linked list queue is perfect.

Project Overview: Movie Ticketing Queue

Imagine a movie theater with multiple booths. Customers arrive, enter their name and ticket count, and are assigned to a queue based on the first letter of their name. The queues are then distributed among booths. Each booth processes customers in FIFO order. We need to output for each booth the customers served and their checkout times.

This assignment tests your ability to implement a queue via linked list, design a program without given prototypes, and follow simulation rules. Let's break it down.

Step 1: Define the Queue Node Structure

Each node holds customer data: name, tickets, arrival time, and a pointer to the next node. We'll also store the queue number and the assigned booth for output.

typedef struct Node {
    char name[51];
    int tickets;
    int arrivalTime;
    int queueNum;
    int booth;
    int checkoutTime;
    struct Node* next;
} Node;

Step 2: Queue Structure and Operations

We need a queue structure with front and rear pointers. Basic operations: createQueue, enqueue, dequeue, isEmpty, and peek.

typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;

Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

void enqueue(Queue* q, Node* newNode) {
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

Node* dequeue(Queue* q) {
    if (q->front == NULL) return NULL;
    Node* temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    return temp;
}

Step 3: Determine Queue Number Based on Name

The assignment uses a specific rule: first letter's position p (0-25), then queue = p % 13, but if p%13 == 0, assign to the queue with the fewest customers among those that have at least one. We'll implement this logic.

int getQueue(char firstLetter, int* queueCounts) {
    int p = firstLetter - 'A';
    int q = p % 13;
    if (q != 0) return q;
    // find queue with smallest count among non-empty queues (1-12)
    int minCount = 1e9, minQueue = 1;
    for (int i = 1; i <= 12; i++) {
        if (queueCounts[i] > 0 && queueCounts[i] < minCount) {
            minCount = queueCounts[i];
            minQueue = i;
        }
    }
    return minQueue;
}

Step 4: Distribute Queues to Booths

We have b booths. First, identify non-empty queues (k). Then assign floor(k/b) or ceil queues per booth. The assignment describes a round-robin-like distribution: queues are sorted, then split sequentially. For example, queues [3,5,6,8,9,10,11,12] with 3 booths -> booth1: 3,5,6; booth2: 8,9,10; booth3: 11,12. We'll store mapping from queue to booth.

Step 5: Process Customers and Compute Checkout Times

We read all customers, create nodes, enqueue them into appropriate queues. Then for each booth, we process its queues in order. For each queue, we dequeue customers one by one. The processing time per customer = 30 + tickets * 5. The start time for a customer is max(arrivalTime, previousFinishTime). Checkout time = startTime + processingTime.

int processTime = 30 + node->tickets * 5;
int start = (node->arrivalTime > boothFreeTime[booth]) ? node->arrivalTime : boothFreeTime[booth];
node->checkoutTime = start + processTime;
boothFreeTime[booth] = node->checkoutTime;

Step 6: Output Results

For each booth, print "Booth Y" and then for each customer in order served: "CUSTOMER from line X checks out at time T." After each booth, print a blank line.

Full Example Walkthrough

Consider the sample input: 17 customers, 3 booths. We'll simulate step by step. First customer TANVIR arrives at time 2, name starts with T (p=19), 19%13=6, queue 6. ARUP (p=0) goes to queue with fewest customers: queue 6 has 1, others 0, so queue 6 again? Wait, the rule says if p%13==0, assign to queue that has seen fewest customers (but has seen at least one). At that moment, only queue 6 has a customer, so ARUP goes to queue 6. This matches sample (both TANVIR and ARUP in queue 6). After processing all, we have 8 non-empty queues. Distribute to 3 booths as described. Then compute checkout times. The sample output matches our simulation.

Common Pitfalls and Tips

  • Memory leaks: Free all allocated nodes after use.
  • Integer overflow: Times can be up to 10^9, processing time up to 30+500*5=2530, so use long long for checkout times.
  • Reading input: Use scanf carefully; names have no spaces.
  • Queue assignment for p%13==0: Ensure you pick the queue with the fewest customers among those that have at least one. If no queue has any customer yet? The problem says it's known in advance which queues will be non-empty, so at least one exists.

Real-World Connections

Queues are everywhere: in call centers, operating system task scheduling, and even in video games like Fortnite where players queue for matches. The recent Taylor Swift Eras Tour ticket sales used queue systems to manage millions of fans. Understanding linked list queues helps you build such systems.

Conclusion

By completing this assignment, you've mastered queues with linked lists in C. You've practiced dynamic memory, pointer manipulation, and simulation design. These skills are essential for data structures courses and technical interviews. Keep coding!