Tutorial Exercises Week 02

Assignment 1

Discuss the assignment. What needs to be completed for the first submission? Think of some testing ideas with your class and your tutor.

Your implementation must keep the lines of a textbuffer in a linked data structure such as a linked list or variant of that. Each line must be represented as a dynamically allocated character array. Discuss what this means.

Exercise 1

Using Stacks and Queues

Consider the following interfaces given in lectures, for a stack and a queue

// 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);

Using two stack data structures, show how you can implement a queue data structure.
Using two queue data structures, show how you can implement a stack data structure.
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);
```

Exercise 2

Implementing a Stack with a Linked List

Implement the functions from the Stack.h interface given in Exercise 1, using a linked list structure. How will you represent your stack?

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

Write a program which, given a string containing round, curly, and square brackets, will print 'success' if the parentheses are correctly balanced, and 'fail' otherwise.

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

Hint: the problem is similar to the postfix expression evaluation problem.

Exercise 4 - Function Pointers

Given the following function prototypes and assignments:

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

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

Give the correct variable declarations for x1, x2, and x3.

Exercise 5 - Testing

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

Exercise 6 - Blackbox testing

Imagine you have the following test file defined in a file called testStack.c and it includes the Stack.h interface from Exercise 1:

#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;
}

When compiling my test file using

gcc -Wall -Werror -c testStack.c

I get the following compile error

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

What does this mean?