Tutorial Solutions Week 02

Assignment 1

Exercise 1

Using Stacks and Queues

// Stack.h
typedef struct stackImp *Stack;
//Function Prototypes
Stack createStack( void );
void destroyStack( Stack stack );
Item pop( Stack stack);
void push( Stack stack, Item data);
int stackSize( Stack stack);

// Queue.h
typedef struct queueImp *Queue;
//Function Prototypes
Queue createQueue( void );
void destroyQueue( Queue queue );
Item get( Queue queue);
void put( Queue queue, Item data);
int queueSize( Queue queue);

1. Using two stack data structures, show how you can implement a queue data structure.

   Solution

   To add items to the queue, simply add the items to one of the stacks, stack1 say, using the pushStack(stack1, item) function.

   To remove the first item from the queue, pop items from stack1 and push them onto the other stack stack2 using push(stack2, pop(stack1)); repeatedly until stack1 is empty. Popping the top item off stack2 will give you the first item of the queue.

   Checking whether the queue is empty is the same as for the stack.

   stack1 can be re-obtained by the same process.

2. Using two queue data structures, show how you can implement a stack data structure.

   Solution

   To add items to the stack, simply add items to one of the queues, queue1 say, using the putQueue(queue1, item) function.

   To pop the top item off the stack, remove items one at a time using item = getQueue(queue1) and check whether queue1 is empty using queueSize(queue1) after each getQueue operation.

   If queue is empty, return item as the top of the stack, otherwise put the item on to the second queue queue2 using putQueue(queue2, item) and repeat the same process by dequeuing the next item from queue1.

3. Using only the functions for manipulating stacks in the stack interface, write a function that joins the two stacks stack1 and stack2 so that stack1 is "stacked" on stack2.

   Note that the contents of stack1 do not need to be preserved.

   void stackStacks(Stack stack1, Stack stack2);
   

   Solution

   void stackStacks(Stack stack1, Stack stack2) {
       Stack stack3 = createStack();
   
       while(stackSize(stack1) != 0) {
           push(stack3, pop(stack1));
       }
   
       while(stackSize(stack3) != 0) {
           push(stack2,pop(stack3));
       }
   }
   

Exercise 2

Implementing a Stack with a Linked List

typedef struct stackNode * link;

struct stackNode{
    //You need to decide what goes in here
}

struct stackImp { 
    //You need to decide what goes in here
};

Assume you have the following local helper function to create Nodes as follows

static link createNode(Item item);

Exercise 3 - Stacks

 
 
> ./check_parens "()"
success
> ./check_parens "([])"
success
> ./check_parens "([]){}"
success
> ./check_parens "([]){"
fail
> ./check_parens "([sdfdf]ss)fdfsd"
success

Item safePop (Stack s) {
  if (stackSize(s) == 0) {
    printf ("syntax error in postfix expression\n");
    abort ();
  } else {
    return (pop(s));
  }
}


char closing (char c) {
  if (c == '(') {
    return ')';
  } else if (c == '[') {
    return ']';
  } else if (c == '{') {
    return '}';
  } else return '\0';
}


int main (int argc, char *argv[]) { 
  Stack s;
  char *a;
  int i;
   
  if (argc < 2) {
    printf ("No argument string provided\n");
    return 0;
  }
  a = argv[1];
  
  s = createStack();
  for (i = 0; a[i] != '\0'; i++) {
    if ((a[i] == '(') || 
        (a[i] == '{') || 
        (a[i] == '[')) { 
      push(s,a[i]);
    } else if ((a[i] == ')') || 
               (a[i] == '}') || 
	       (a[i] == ']')) {
      if (closing (safePop (s)) != a[i]) {
	printf ("fail\n");
	return (0);
      }
    }
  }
    
  if (stackSize (s) == 0) {
    printf ("success\n");
  } else {
    printf ("fail\n");
  }
  return (0);
}       

Exercise 4 - Function Pointers

int  add (int n1, int n2);
link reverse (link ls);
void square (double *x);

 x1 = add;
 x2 = reverse;
 x3 = square;

int  (*x1) (int, int);
link (*x2) (link);
void (*x3) (double *);

Exercise 5 - Testing

What is the difference between black box and white box testing ADTs?

Black box testing tests the functionality of the code. It focuses on the input and output of the functions defined in the interface. It does not rely on the underlying implementation. It can't access the underlying implementation. Our black box tests should still work even if we change the underlying implementation.

White box testing tests the structure of the code. It relies on knowing, accessing and testing the internal state of the code. If we changed our implementation we would need to write new white box tests.

Exercise 6 - Blackbox testing

#include "Stack.h"

int main(int argc, char * argv[]){
    printf("Testing new stack\n");
    Stack s = createStack();
    assert(s->size == 0);
    printf("Test passed\n");
    return 0;
}

gcc -Wall -Werror -O -c testStack.c

testStack.c:12:5: error: dereferencing pointer to incomplete type

It this case we are getting the error as we are trying to use the internal structure of the ADT by saying s->size.

We have no access to the underlying implementation of the stack, we we can only access the ADT by the functions and typedefs provided in the interface (.h file).