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

0
3
7
8
6
5
9
9

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

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


Stack *stackCreate(void){
    //At the moment s contains garbage
    Stack *s;
    //This line is saying go to the garbage address in memory and set the size field
    //This is illegal
    s->size = 0;
    return s;
}
//This is the correct version
Stack *stackCreate(void){  
    Stack *s = malloc(sizeof(struct stack));
    //It is good practice to check malloc succeeded
    if(s == NULL){
        fprintf(stderr,"Insufficient Memory\n");
        exit(EXIT_FAILURE);
    } 
    s->size = 0;
    return s;
}

//This is dangerous as it does not check whether the stack is full
//and will result in an array overflow if it is!
void stackPush(Stack *s, int item){
    s->items[s->size] = item;
    s->size++;
}

//This is the correct version
void stackPush(Stack *s, int item){
    int index = s->size;
    if(s->size < MAX_SIZE){
        s->items[index] = item;
        s->size++;
    } else {
        fprintf(stderr,"Stack full\n");
        stackDestroy(s);
        exit(EXIT_FAILURE);
    }
}


int stackTop(Stack *s){
   if(s->size == 0){
       fprintf(stderr,"Stack empty\n");
       stackDestroy(s);
       exit(EXIT_FAILURE);
   }
   //This is incorrect
   //For example if we had three items on the stack, size would be 3
   //and the index of the item at the top  would be size-1
   //Items: 9 10 11
   //Index: 0  1  2   
   return s->items[s->size];
}

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


int stackPop(Stack *s){
   if(s->size == 0){
       fprintf(stderr,"Stack empty\n");
       stackDestroy(s);
       exit(EXIT_FAILURE);
   }
   //This is the same issue as in the function top. Should be s->size-1
   int topItem = s->items[s->size];
   s->size--;
   return topItem;
}

//This is the correct version
int stackPop(Stack *s){
   if(s->size == 0){
       fprintf(stderr,"Stack empty\n");
       stackDestroy(s);
       exit(EXIT_FAILURE);
   }
   int topIndex = s->size -1;   
   int topItem = s->items[topIndex];
   s->size--;
   return topItem;
}

For example in {()} or ((())) the brackets are balanced. But in {){} or )))((( they are not.

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

void stackStacks(Stack *stack1, Stack *stack2);

void stackStacks(Stack *stack1, Stack *stack2) {
    Stack *stack3 = stackCreate();

    while(stackSize(stack1) != 0) {
        stackPush(stack3, stackPop(stack1));
    }

    while(stackSize(stack3) != 0) {
        stackPush(stack2,stackPop(stack3));
    }
    stackDestroy(stack3);
}

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

0
3
9
8
7
6
5
5

• 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

If we have an array such as
items:  3 4 5 6 9
Indexes:0 1 2 3 4
And we remove the item at index 0, we need to shift all items along so there is no gap
items:  4 5 6 9
Indexes:0 1 2 3 4
Alternatively
If we have an array such as
items:  3 4 5 6 9
Indexes:0 1 2 3 4
And we add an item, say 7 at index 0, we need to shift all items along to make room
items:  7 3 4 5 6 9
Indexes:0 1 2 3 4 5