# Week 4 - Stacks and Queues

## Team

Team name: coole team
Date: 12- 3 - 2021

Members

| Role | Name |
| ---- | ---- |
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Julia |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Julia |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Maurice |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Irene |

## Activities

### Activity 1: LIFO vs FIFO
FIFO is an abbreviation for first in, first out. It is a method for handling data structures where the first element is processed first and the newest element is processed last.
The new element is inserted below the existing element, so that the oldest element can be at the top and taken out first. Therefore the first element to be entered in this approach, gets out First.

LIFO is an abbreviation for Last in, first out. It is a method for handling data structures where the last element is processed first and the first element is processed last.
The new element is inserted above the existing element, so that the newest element can be at the top and taken out first. Therefore the first element to be entered in this approach, gets out Last.

Stacks are based on the LIFO principle (Last In First Out). Queues are based on the FIFO principe (First In First Out).

### Activity 2: Complete the stack implementation

void stack_push(Stack *p_stack, float value) {
    stack_ensure_capacity(p_stack, p_stack->count + 1);

    // add the value, update the count
    //[complete the code!]
    p_stack->pValues[p_stack->count] = value;
    p_stack->count++;

}

// checking the top value but not removing it
float stack_peek(Stack *p_stack) {
    if (p_stack->count > 0) {
        // return the top value
    	return p_stack->pValues[p_stack->count-1];
    }
    else {
        // no values available, indicate error
        return FP_NAN;
    }
}

// deleting an element from the stack and returning the deleted element
float stack_pop(Stack *p_stack) {
    float value;
    if (p_stack->count > 0) {
        // return the top value
        // count -1
        // free element memory?
    	value = stack_peek(p_stack);
    	p_stack->count--;
    }
    else {
        // no values available, indicate error
        return FP_NAN;
    }

    return value;

}

### Activity 3: Reverse Polish Notation

void process_rpn(const RPNSequence *sequence, Stack *pStack) {
    for (int i = 0; i < sequence->count; i++) {
        Token token = sequence->tokens[i];
        if (token.type == VALUE) {


            stack_push(pStack, token.value);
            printf("push %2.f\n", token.value);
        }
        else if (token.type == OPERATOR) {
            // apply operation to top 2 operands on the stack, push result
            // output a "mul", "add", "div", or "sub" to the console
            float value;
            switch(token.operator){
                case '*':
                    value = stack_pop(pStack) * stack_pop(pStack);
                    stack_push(pStack, value);
                    printf("mul\n");
                    break;
                case '+':
                    value = stack_pop(pStack) + stack_pop(pStack);
                    stack_push(pStack, value);
                    printf("add\n");
                    break;
                case '/':
                    value = stack_pop(pStack) / stack_pop(pStack);
                    stack_push(pStack, value);
                    printf("div\n");
                    break;
                case '-':
                    value = stack_pop(pStack) - stack_pop(pStack);
                    stack_push(pStack, value);
                    printf("sub\n");
                    break;

            }
        }
    }
}

Answer of the sum: 5,6

### Activity 4: Application of queues

1. ticket sale queue
2. files oplossen
3. Task manager

### Activity 5: Implement a Queue using a linked list

int llq_back(const LLQueue *p_queue) {
    // return value at end / rear of queue
    //[complete the code!]
    return p_queue->tail->value;
}

int llq_front(const LLQueue *p_queue) {
    // return value at front / head of queue
    //[complete the code!]
    return p_queue->head->value;
}

### Activity 6: Implement a Queue using an array

void aq_ensure_capacity(ArrayQueue *p_queue, int capacity) {
    if (capacity > p_queue->capacity) {
        const int min_new_capacity = p_queue->capacity * 3 / 2;
        if (capacity < min_new_capacity)
            capacity = min_new_capacity;

        p_queue->p_values = (int*) realloc(p_queue->p_values, sizeof(int) * capacity);
        if (p_queue->p_values == NULL) {
            fprintf(stderr, "Error re-allocating memory!\n");
        }

        // copy the values that wrapped around to indices [0...],
        int wrapped = p_queue->count - (p_queue->capacity - p_queue->idx_head);
        if (wrapped > 0) {
            memcpy(p_queue->p_values + p_queue->capacity,
                   p_queue->p_values, sizeof(int) * wrapped);
        }

        p_queue->capacity = capacity;
    }
}

void aq_init(ArrayQueue *p_queue, int initial_capacity) {
    p_queue->count = p_queue->idx_head = 0;
    p_queue->capacity = initial_capacity;
    p_queue->p_values = (int*) malloc(sizeof(int) * initial_capacity);
}

void aq_free(const ArrayQueue *p_queue) {
    free(p_queue->p_values);
}

// werkt: niet aan komen
void aq_push_back(ArrayQueue *p_queue, int value) {
    // make sure there's enough space in the queue
    aq_ensure_capacity(p_queue, p_queue->count + 1);

    // append value & update count (hint: use the modulo (%) operator!)
    // [complete the code!
    int index = (p_queue->idx_head + p_queue->count) % p_queue->capacity;
    p_queue->p_values[index] = value;
    p_queue->count++;
}

void aq_push_front(ArrayQueue *p_queue, int value) {
    // make sure there's enough space in the queue
    aq_ensure_capacity(p_queue, p_queue->count + 1);

    // prepend value, update idx_head & count, make sure that idx_head does not become negative!
    //[complete the code!]
    p_queue->idx_head = p_queue->idx_head - 1;

    if(p_queue->idx_head < 0){
        p_queue->idx_head = p_queue->count;
        p_queue->count++;
        p_queue->p_values[p_queue->idx_head] = value;
    }else{
        p_queue->p_values[p_queue->idx_head] = value;
        p_queue->count++;
    }

}

int aq_back(const ArrayQueue *p_queue) {
    return p_queue->p_values[aq_tail_index(p_queue)];
}

int aq_front(const ArrayQueue *p_queue) {
    // return value at front / head of queue
    //[complete the code!]
    return p_queue->p_values[p_queue->idx_head];
}

int aq_pop_back(ArrayQueue *p_queue) {
    int value = aq_back(p_queue);
    p_queue->count--;
    return value;
}

// werkt: niet aan komen
int aq_pop_front(ArrayQueue *p_queue) {
    int value = aq_front(p_queue);
    // update idx_head & count. Hint: use the modulo (%) operator!
    //[complete the code!]

    // [1,2,3] remove the first element 1 is at index 0 current head was at index 0 but now is 1 because the first element is 2 when you remove 1jjjjjjjjj

    p_queue->idx_head++;
    if(p_queue->idx_head == p_queue->count){
        p_queue->idx_head = 0;
    }
     // moving the head to the next element (index)
    p_queue->count--; // removing the first element;
    if(p_queue->count < 0){
        p_queue->count = p_queue->capacity;
    }
    return value;

}

// computes the index of the tail, based on idx_head, count, and capacity
// NOTE: if idx_head and count are both 0, returned index is -1, but represents
// a meaningless number
int aq_tail_index(const ArrayQueue *p_queue) {
    return (p_queue->idx_head + p_queue->count - 1) % p_queue->capacity;
}

int aq_size(const ArrayQueue *p_queue) {
    return p_queue->count;
}

### Activity 7: Algorithm analysis

O(n^2)

### Activity 8: Solve the problem using the linked list-based queue

int find_sum_llqueue(const Array *array, int target, int *count) {
    LLQueue q;
    llq_init(&q);

    int sum = 0;
    for (int i = 0; i < array->count; i++) {
        // add element to queue, update sum, remove elements while sum greater than target
        //[complete the code!]
        llq_push_back(&q, array->values[i]);
        sum += llq_front(&q);
        if(sum > target) sum -= llq_pop_front(&q);

        // if sum == target, set *count and return index
        if (sum == target) {
            // cleanup
            llq_free(&q);

            // set *count, return index of sequence
            //[complete the code!]
            *count = i++;
            return i;

        }
    }

    // cleanup
    llq_free(&q);
    return -1;
}

### Activity 9: Solve the problem using the array-based queue

### Activity 10: Benchmark the three algorithms

### Activity 11: Time complexity

### Activity 12: Explain the impact of the chosen data structure

## Look back

### What we've learnt

stacks en queues, programmeren

### What were the surprises

veel werk

### What problems we've encountered

bugs in onze code

### What was or still is unclear

de algorithmes

### How did the group perform?

prima, iedereen was aanwezig

##### Links:
https://www.programiz.com/dsa/deque