Week 9 Tutorial — Stacks and Queues

  1. In lectures we saw that a push operation on a quack could be implemented using a linked list as:

    void push(int data, Quack qs) {
       if (qs == NULL) {
          fprintf(stderr, "push: quack not initialised\n");
       } else {
          Quack newnode;
          newnode = (Quack)malloc(sizeof(struct _node));
          assert(newnode != NULL);
          newnode->data = data;
          newnode->next = qs->next;
          qs->next = newnode;
       }
    }
    

    In the tutorial last week, we saw that we can insert a node in a linked list using either insertHead() or insertTail(), corresponding to an insert at the start or end of the linked list.

    1. Which of these two insert operations is the following fragment of code?
    2. NodeT *??????(NodeT *head, int data) {
         NodeT *new;
         new = (NodeT *)malloc(sizeof(NodeT));
         assert(new != NULL);
         new->data = data;
         new->next = head;
         return new;
      }
      

    3. What similarity do you see between the push and insert operations?
    4. Why does the insert operation above need to return an address, but the push operation does not?
      • Why has the push operation been implemented this way?
  2. Complementary to the (linked-list) push operation, we have the (linked-list) 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. What is topnode in terms of the linked list?
    2. What exactly is this code doing in terms of the linked list?
    3. Can topnode be NULL in line 9?
      • Can topnode->next be NULL in Line 11? What does the value of topnode->next tell us about the quack before and after the pop operation?
  3. In the array implementation of a quack we used the struct:

    #define HEIGHT 1000
    struct _node {
       int array[HEIGHT];
       int top;
    };
    

    In createQuack() a struct _node is malloc'd. Assume the node is called qs. The variable top in this struct gets initialised as follows:
    qs->top = -1;
    

    1. What is the role of the variable top?
      • if top == 0, what can you say about the quack?
      • if top == HEIGHT-1, what does that say about the quack (in the code above)?
      • if top == HEIGHT, what does that say?

    2. To push an element data onto the quack qs, what code could we use?
      • Before we push an element onto the quack, we should check for quack overflow. How?

    3. To pop an element from the quack qs, what code could we use?
      • Before we pop an element from the quack, we should check for quack underflow. How?