Week 10 Tutorial Sample Answers

In this week's lab please complete the myExperience survey for COMP1511.
Your tutor has asked a lab pair to present their week 9 work.
Discuss the good, the bad and the ugly aspects of their code.
Please be gentle in any criticism - we are all learning!
It's week 10! Well done on making it this far through the course, you've all worked very hard, and achieved some incredible results, and you should all feel proud about how far you've come in these ten short weeks. Take some time as a tute to look back over the semester, and think about how it has been for you. What were your favorite parts? What things weren't so good? And perhaps most importantly, who/what are you grateful for?
How are you progressing with the assignment?
Do you have any questions? Have you learned anything that would be useful to share with the rest of the tutorial?
What is the purpose of a Header file?
The header file contains the typedefs, function declarations and defines for a particular Abstract Data Type (doesn't always have to be an ADT, a header can just be functionality that is available in a separate file, but in this course, we've only seen ADTs in this format).
The header contains just enough information to be able to use the typedef struct pointer and functions, but nothing more. So no unsafe access to data, but easy to read access to the functions.
What is the purpose of a Implementation file?
The C file implements the typedef and the functions in the header.
This means it makes sure that everything that's declared in its header file has a complete set of working code so that when the function is called, it will be able to run.
The C file will #include the header so that it can see what declarations it needs to implement.
I have two files, a list.h and a list.c that describe a particular form of list that I want to use.
I then have a main.c that would like to use the functionality offered by the other two files.
Which files need to #include the other files?
The main.c includes the *.h, but not the *.c.
The *.c includes the *.h.
Remember that using #include is functionally very similar to copying and pasting the text from the *.h file into the exact position in the file that's including it.
In this way, it's very similar to earlier in the course where we were putting our function declarations at the top of our code files.
What is the compilation command that will combine these files into a single program?
dcc main.c list.c -o list_program
Remember that we're compiling all the c files so that all the implementation is translated into instructions for our computer to be able to run. The h files don't need to be compiled because they're included by the c files already.
What is a queue?
An abstract structure that is a collection of elements that follows specific rules about how it behaves.
It is "First In First Out". The oldest element in the queue will be the first to be removed from the queue.
Draw a diagram of a queue, if it was implemented by a Linked List. Show:
- How the linked list is structured, with a head pointer and pointers between nodes
- Which end of the list is the front and back of the queue
- Any extra structure(s) that might be needed to manage the queue
- What happens when a new object is added to the queue
- What happens when an object is removed from the queue
This will be answered in class with a diagram.
Important elements of this diagram:
- The linked list nodes all have pointers to the next node as well as their own data
- There's a head pointer aimed at the first node
- There's another struct that keeps track of the queue itself, with a pointer to each end of the list, the front and back. This is reasonably important because without it, an empty queue is a NULL pointer, which complicates all the functions that access the queue.
  The order of the queue is a matter of choice. The front can be the head or the tail, it will just change the way the functions are written.
- Adding an object involves creating a new node (malloc) and attaching it to the back of the queue. This means a normal insertion into a linked list as well as changing where the back pointer is aiming.
- Removing an object means using the front pointer to find the correct object to remove, then performing a standard linked list removal. After that, the front pointer will need to be assigned to the new front of the queue.
Keeping the same diagram, show what changes you'd need to make to turn this structure into a stack?
The only serious change to this diagram would be that the front and back pointers would now be aimed at the same end of the queue, since a stack adds and removes to the same end of its list.
If we want, we can also remove one of the two and rename it to a top pointer and then only trivial changes would need to be made to the functions for add and remove.

Given the abstract structure you have drawn for a queue, write the code that will represent your queue as well as the function to add an element to the queue.

You will need to show what code goes in the header file and what code goes in the implementation file.

We can assume that the data we're holding in each element of the queue is an integer.

You might like to use the following activity as a starting point.

Given the starter code below, complete these steps to implement and use a queue ADT.

Which 3 files do we need? What are the names of these files?
Which code belongs in which files?
Complete the implementation file
Create a file that uses the code. Should we use the following line in this file?
```
printf("%d\n", q->start->data);
```

    typedef struct queueInternals *Queue;
    void enqueue(Queue q, int item);
    int dequeue(Queue q);
    Queue newQueue(void);
    int main(void) {
        //TODO: Add some code that makes a queue
    }
    struct queueInternals {
        struct queueNode *front;
        struct queueNode *back;
    };
    struct queueNode {
        int data;
        struct queueNode *next;
    };
    Queue newQueue(void){
        //TODO: Implement  
    }
    // Add a queueNode to the end of the list (just after back)
    void enqueue(Queue q, int item) {
        //TODO: Implement
    }
    //Remove a queueNode from the beginning of the list (at the start) and return
    // the value of data at the start node
    int dequeue(Queue q){
        //TODO: Implement
    }

queue.h

queue.c

queue_used.c