Week 9 Tutorial — Sample Solutions

1. • The insert code shown is insertHead(). It 'creates' a new head of the linked list by inserting at the head.
   
   
   • The main similarity between the push and insert operations is that both insert a new node at the head of a linked list.
   • In the insertHead(), the new head is returned.
   • In the push(), the head qs does not change, just the pointer qs->next, which points to the newly inserted head.
   
   
   • The insert operation returns an address because the actual head changes. The push operation does not return a new head because just a pointer inside a 'permanent' (or 'dummy') head changes.
   • The reason that we do not want to change and return the head is that we want to use code such as:

   #include "quack.h" ... Quack q = NULL; q = createQuack(); push(1, q); pop(q);

   If the push operation returned a new head, then we would need to call push() as:

   q = push(1, q); // this is not so attractive

   so we create a 'dummy' head when we create a Quack, and push() returns a void.

2. We are considering the pop operation:

   1 int pop(Quack qs) { 2 int retval = 0; 3 if (qs == NULL) { 4 fprintf(stderr, "pop: quack not initialised\n"); 5 } else { 6 if (isEmptyQuack(qs)) { 7 fprintf(stderr, "pop: quack underflow\n"); 8 } else { 9 Quack topnode = qs->next; // top node must be there 10 retval = topnode->data; 11 qs->next = topnode->next; 12 free(topnode); 13 } 14 } 15 return retval; 16 }

   
   
   1. The node topnode is the second node in the linked list.
   
   
   2. The code does the following:

      if qs has been created ... and qs is not empty ... let topnode point to the second node in the linked list store the data from topnode remove topnode by relinking to topnode's next node free topnode return the data from topnode

   3. No topnode in Line 11 cannot be NULL becuse the quack cannot be empty at this line
   • yes, topnode->next in Line 13 can be NULL: this means that the quack consisted of just 1 element before the pop operation, and after the operation the quack will be empty.

3. 1. The variable top is the index of the top element on the quack.
      • if top == 0, there is one element on the quack (at array[0])
      • if top == HEIGHT-1, then there are HEIGHT elements on the quack: it is full
      • it should never happen that top == HEIGHT, a full quack should not go higher than top = HEIGHT-1
      
      
   2. To push an element data onto the quack qs, we do the following:

   ++(qs->top); // we are adding an element, so increment the index qs->array[qs->top] = data; // place the element at this location

   
   
   • to check for quack overflow:

     if (qs->top >= HEIGHT-1) { fprintf(stderr, "push: quack overflow\n"); }

   
   
   3. To pop an element from the quack qs, we use the following:

   data = qs->array[qs->top]; // 'get' the top element on the quack --(qs->top); // decrement the index indicating the top of quack return data; // return the top element

   Notice that we do not actually delete the element in the array.

   • to check for quack underflow:

     if (qs->top <= -1) { fprintf(stderr, "pop: quack underflow\n"); }