Week 8 Tutorial — Stacks, Queues, Linked Lists

1. Show the effect of executing the following sequence of operations on an initially empty stack:

   push 1; push 5; push 3; pop; push 4; push 2; pop; pop; pop; pop;

   What sequence of numbers will be generated by the pop commands?

2. Show the effect of executing the following sequence of operations on an initially empty queue:

   enqueue 1; enqueue 5; enqueue 3; dequeue; enqueue 4; enqueue 2; dequeue; dequeue; dequeue; dequeue;

   What sequence of numbers will be generated by the dequeue commands?

3. 1. The following function inserts given data v into a linked list:

      void insertData(NodeT *head, int v) { // create new node and set data NodeT *new = (NodeT *)malloc(sizeof(NodeT)); assert (new != NULL); new->data = v; new->next = head; }

      • Where is the data being placed in the list?
      • Draw a diagram showing before and after the insertion. Considere the cases:
      • an empty list
      • a list containing a single node
      • a list containing many nodes
      • The function has a problem. What is it? Fix it.

   2. Modify the function to place the data at the end of a linked list.
      • Draw a diagram showing before and after the insertion.
      • Consider the cases: an empty list, a single node, and many nodes

4. Assume that we have a sequence of characters.

   • In a single right rotation of the sequence, the last character is moved to the start of the sequence. For example, the sequence a1234b would become ba1234.
   • In a single left rotation, the first character is moved to the end of the sequence. For example, the sequence a1234b would become 1234ba.

   Assume the character string is stored in a linked list, one character in each node. Think of 2 different strategies to implement left and right rotation of a string stored in a linked list. Both strategies will require you to traverse the entire linked list:

   • consider what needs to happen during the traversal in each strategy
   • pay attention to the 'boundary conditions'
   • what needs to happen at the start and end of the traversal?
   • what happens when the list is empty or consists of a single node?

5. Suppose we are given a sorted linked list of numbers. We are interested in knowing whether there are any duplicate nodes (i.e. nodes that have the same data) in the list.

   • What do we need to do?
   • Implement a function that returns 0 if there are no duplicate nodes, and 1 if there are any. The function should have prototype:

   int hasDupList(NodeT *); // 1 if true, 0 if false