# Week 4 - Stacks and Queues

## Team

Team name: Group 7
Date: 17/3/2021

Members
Len Bauer
Marco Schirrmacher
Sebastian Wojciechowski

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

## Activities

### Activity 1: LIFO vs FIFO

LIFO (Last-In-First-Out) - The LIFO principle implies that the element inserted at the last to a ***STACK*** is also the first to be deleted when a new one is added

FIFO (First-In-First-Out) - The FIFO principle implies that the first element inserted in a ***QUEUE*** is the first element to be deleted when a new one is added

### 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
    p_stack->pValues[++p_stack->count] = value;
}


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

float stack_pop(Stack *p_stack) {
    if (p_stack->count > 0) {
        // return the top value, decrement count
        return p_stack->pValues[p_stack->count--];
    }
    else {
        // no values available, indicate error
        return FP_NAN;
    }
}

### Activity 3: Reverse Polish Notation

void process_rpn(const RPNSequence *sequence, Stack *pStack) {
    int i ;
    for (i = 0; i < sequence->count; i++) {
        Token token = sequence->tokens[i];
        if (token.type == VALUE) {
            // push to the stack
            // output a "push xxx" to the console
            stack_push(pStack, token.value) ;
            printf("push %.0f\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 number1 = stack_pop(pStack) ;
            float number2 = stack_pop(pStack) ;
            float result ;
            switch(token.operator){
                case '*':
                    result = number2 * number1 ;
                    printf("mul\n") ;
                    break ;
                case '/':
                    result = number2 / number1 ;
                    printf("div\n") ;
                    break ;
                case '+':
                    printf("add\n") ;
                    result = number2 + number1 ;
                    break ;
                case '-' :
                    printf("sub\n") ;
                    result = number2 - number1 ;
                    break ;
            }
            stack_push(pStack, result);
        }
    }
}

### Activity 4: Application of queues

#### Applications:
- Call Centers (calling que)
- Serving shared resources (Printers, CPU Scheduling, Disk Scheduling)
- An internet browser’s history.
- Handling of interrupts in real-time systems
- Storing a computer code application’s list of undo operations.

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

int llq_back(const LLQueue *p_queue) {
    // return value at end / rear of queue
    return p_queue->tail->value;
}

int llq_front(const LLQueue *p_queue) {
    // return value at front / head of queue
    return p_queue->head->value;

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

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!)
    int idx_tail = aq_tail_index(p_queue);
   
    p_queue->p_values[(idx_tail + 1)%p_queue->capacity] = 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!
    if (p_queue->idx_head == 0) {
        p_queue->idx_head = p_queue->capacity - 1; 
        p_queue->p_values[p_queue->idx_head] = value; 
        p_queue->count ++; 
    } else {
        p_queue->p_values[--p_queue->idx_head] = value; 
        p_queue->count ++; 
    }
}

int aq_back(const ArrayQueue *p_queue) {
    // return value at end / rear of queue
    int idx_tail = aq_tail_index(p_queue);
    return p_queue->p_values[idx_tail];
}

int aq_front(const ArrayQueue *p_queue) {
    // return value at front / head of queue
    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;
}

int aq_pop_front(ArrayQueue *p_queue) {
    int value = aq_front(p_queue);
    // update idx_head & count. Hint: use the modulo (%) operator!
    p_queue->idx_head = (p_queue->idx_head + 1) % p_queue->capacity;
    if(p_queue->idx_head == p_queue->capacity)
    {
        p_queue->idx_head = 0;
    }
    p_queue->count --;
    return value;
}

### Activity 7: Algorithm analysis

Since the function consists of two nested for loops the time complexity will be quadratic, or in Big O notation `O(n²)`.

The runtime of the algorithm compuonds as every value has to be referenced twice, which is:`(O(n*n)) = O(n²)`.

### 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
        int val = array ->values[i];
        llq_push_back(&q, val);
        sum += val;

        while (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
            *count = q.count;
            return 1 + i - *count;
        }
    }
    // cleanup
    llq_free(&q);
    return -1;
}

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

int find_sum_arrayqueue(const Array *array, int target, int *count) {
    ArrayQueue q;
    aq_init(&q, 100);

    int sum = 0;
    for (int i = 0; i < array->count; i++) {
        // add element to queue, update sum, remove elements while sum greater than target
        int val = array->values[i];
        aq_push_back(&q, val);
        sum += val;

        while (sum > target) {
            sum -= aq_pop_front(&q);
        }
        
        // if sum == target, set *count and return index
        if (sum == target) {
            // cleanup
            aq_free(&q);

            // set *count, return index of sequence
            *count = q.count;
            return 1 + i - *count;
        }
    }
    // cleanup
    aq_free(&q);
    return -1;
}

### Activity 10: Benchmark the three algorithms

| Number of elements | ARRAY_QUEUE (ms) | LINKEDLIST_QUEUE (ms)| NAIVE (ms)|
| ------ | -------- | -------- | -------- |
| 15 | 0 | 0 | - |
| 62.5k | 2.37 | 6.95 | 18.88 |
| 125k | 4.86 | 15.29 |31.79 |
| 250K | 10.82 | 33.66 |65.25 |
| 500K | 19.16 | 54.75 |132.52 |
| 1M | 61.94 | 169.21 |327.34 |
| 2M | 95.92 | 333.5 | 647.7 |
### Activity 11: Time complexity
Since the reverse polish notation has a time complexity of 0(n), which is a linear time algorithm, meaning that the more elements we add to the stack, the time scales evenly with the number of elements added.

The stack and queue has a time complexity of 0(1), since the popping and pushing of elements to a stack can only be 1 number, which will always take the same amount of time irregardless the size of the number.

For both of the linked list queues and array queues, the time complexity will be the same as the queue and stack whcih is 0(1).

The Array queue has a time complexity of 0(n).
The linkedlist queue has a time complexity of 0(n) too.
While the first 2 algorithms have a time complexity of 0(n), the naive algorithm had a time complexity of 0(n²)

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

The Array data structure is the fastest of the three since it only needs to incerment its itterator, while the linked list has to keep track and change its head and tail respectively. While they have the same time complexity, processing of the array-based queue is easier than the linked list.
## Look back

### What we've learnt

We have learnt the basic implementation and use of stack and queues. We have learnt the time complexity of these algorithms aswell as "popping" and "pushing" said stacks and queues.

### What were the surprises

We're surprised that our code actual worked and posted the correct results, it took a lot of work and reading throug the code, but in the end we managed to get it to work properly.

### What problems we've encountered

We have struggled quite a bit for some of the coding exercises, more specifically activity 8 and 9. The implementation of the files into the code was primarily the issue and sorting said files into the algorithms.

### What was or still is unclear

The implementation of files is still a little unclear and how to read them in the code.

### How did the group perform?

The group performed well with frequent communication. The open communication of the group made it possible for help to be given more frequently and solve problems together than searching the internet, etc.