COMP1911 Week 10 Tutorial Questions

Given the following typedefs and function prototypes in Stack.h

typedef struct stack Stack;

Stack* stackCreate(void);
void stackPush(Stack s*, int item);
int stackTop(Stack s*);
int stackPop(Stack s*);
int stackSize(Stack s*);
void stackDestroy(Stack s*);

What would the output of the following program be?

#include "Stack.h"

int main(int argc, char * argv[]){
    Stack *s = stackCreate();
    printf("%d\n",stackSize(s));
    stackPush(s,9);
    stackPush(s,8);
    stackPush(s,7);
    printf("%d\n",stackSize(s));
    printf("%d\n",stackPop(s));
    printf("%d\n",stackPop(s));
    stackPush(s,6);
    printf("%d\n",stackPop(s));
    stackPush(s,5);
    printf("%d\n",stackPop(s));
    printf("%d\n",stackTop(s));
    printf("%d\n",stackPop(s));
    stackDestroy(s);
}

What would happen if we tried to do one more stackPop(s) before we destroyed the stack in the previous question?

Indentiy and fix the errors in the following Stack.c code

struct stack{
    int items[MAX_SIZE];
    int size;  
};


Stack *stackCreate(void){
    Stack *s;
    s->size = 0;
    return s;
}

void stackPush(Stack *s, int item){
    s->items[s->size] = item;
    s->size++;
}

void stackDestroy(Stack *s){
    free(s);
}

int stackSize(Stack *s){
    return s->size;
}


int stackTop(Stack *s){
   if(s->size == 0){
       fprintf(stderr,"Stack empty\n");
       stackDestroy(s);
       exit(EXIT_FAILURE);
   }
   return s->items[s->size];
}

int stackPop(Stack *s){
   if(s->size == 0){
       fprintf(stderr,"Stack empty\n");
       stackDestroy(s);
       exit(EXIT_FAILURE);
   }
   int topItem = s->items[s->size];
   s->size--;
   return topItem;
}

Discuss how you could use a stack to solve the problem of determining whether brackets are balanced. Note: DO NOT write actual code for this. This is the first lab exercise.
For example in {()} or ((())) the brackets are balanced. But in {){} or )))((( they are not.
Using only the functions for manipulating stacks in the Stack.h 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);
```

Given the following typedefs and function prototypes

typedef struct queue Queue;

Queue *queueCreate(int maxSize);
void enqueue(Queue *q, int item);
int queueFront(Queue *q);
int dequeue(Queue *q);
int queueSize(Queue *q);
void queueDestroy(Queue *q);

What would the output of the following program be?

#include "Queue.h"

int main(int argc, char * argv[]){
    Queue *q = queueCreate(10);
    printf("%d\n",queueSize(q));
    enqueue(q,9);
    enqueue(q,8);
    enqueue(q,7);
    printf("%d\n",queueSize(q));
    printf("%d\n",dequeue(q));
    printf("%d\n",dequeue(q));
    enqueue(q,6);
    printf("%d\n",dequeue(q));
    enqueue(q,5);
    printf("%d\n",dequeue(q));
    printf("%d\n",queueFront(q));
    printf("%d\n",dequeue(q));
    queueDestroy(q);
}

When using an array to implement a queue we can either
- enqueue or add items to the end of the array and dequeue or remove Items from index 0
- enqueue or add items to index 0 and dequeue or remove Items from the end
What is the difficulty with removing or adding items at the beginning of an array? (Do not write code for this. Just discuss. This will be written in the lab)