# Week 4 - Stacks and Queues

## Team

Team name: **Group [497441]**
Date: 01/08/2021

Members: Maxx Thielen

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

## Activities

### Activity 1: LIFO vs FIFO

* FIFO stands for **First-in-First-out** and is used to describe a data strcuture in which the first element passed to it is processed first and the newest element is processed last.
* LIFO stands for **Last-in-First-out** and is used to describe a data structure in which the last element passed to it is processed first and the first element is processed last.

A stack therefore, is concidered a LIFO data structure due to its magazine like function, only giving the user access to the top/last element in the structure.
In the case where where a stack provides access to both the bottom and top element of its structure it would indeed have FIFO ablities since the first/bottom element would be able to be retrieved.

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

float stack_peek(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;
    }
}

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

### 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) {
            // push to the stack
            // output a "push xxx" to the console
            // TODO [complete the code!]
            stack_push(pStack, token.value);
            printf("push %.2f\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
            // TODO [complete the code!]
            float value1 = stack_pop(pStack);
            float value2 = stack_pop(pStack);
            float product;
            if(token.operator=='+'){
                product=value2+value1;
                printf("add -> %.2f+%.2f = %.2f\n",value2,value1,product);
            }
            else if(token.operator=='-'){
                product=value2-value1;
                printf("sub -> %.2f-%.2f = %.2f\n",value2,value1,product);
            }
            else if(token.operator=='*'){
                product=value2*value1;
                printf("mul -> %.2f*%.2f = %.2f\n",value2,value1,product);
            }
            else {
                product=value2/value1;
                printf("div -> %.2f/%.2f = %.2f\n",value2,value1,product);
            }
            stack_push(pStack, product);
        }
    }
}

**Output:**

### Activity 4: Application of queues

Queues are very helpful in cases of:
* process schedules
* message queues for comunication
* data buffers for I/O devices

Most of the time having limited resources and having to share it across mutlibe processes requires setting up a queue to manage incoming requests.
### Activity 5: Implement a Queue using a linked list

void llq_push_back(LLQueue *p_queue, int value) {
    LinkedListNode *node = (LinkedListNode*) malloc(sizeof(LinkedListNode));
    node->value = value;
    node->next = NULL;
    node->prev = p_queue->tail;

    if (p_queue->head == NULL) {
        p_queue->head = node;
    }
    else {
        p_queue->tail->next = node;
    }
    p_queue->tail = node;
    p_queue->count++;
}

void llq_push_front(LLQueue *p_queue, int value) {
    LinkedListNode *node = (LinkedListNode*) malloc(sizeof(LinkedListNode));
    node->value = value;
    node->prev = NULL;
    node->next = p_queue->head;

    if (p_queue->tail == NULL) {
        p_queue->tail = node;
    }
    else {
        p_queue->head->prev = node;
    }
    p_queue->head = node;
    p_queue->count++;
}

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

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

int llq_pop_back(LLQueue *p_queue) {
    LinkedListNode *back = p_queue->tail;
    p_queue->tail = p_queue->tail->prev;
    if (p_queue->tail != NULL) {
        // break connection from queue's tail to back
        p_queue->tail->next = NULL;
    }
    else {
        // also set head to NULL
        p_queue->head = NULL;
    }
    int value = back->value;

    // release memory
    free(back);
    p_queue->count--;
    return value;
}

int llq_pop_front(LLQueue *p_queue) {
    LinkedListNode *front = p_queue->head;
    p_queue->head = p_queue->head->next;
    if (p_queue->head != NULL) {
        // break connection from queue's head to front
        p_queue->head->prev = NULL;
    }
    else {
        // also set tail to NULL
        p_queue->tail = NULL;
    }
    int value = front->value;

    // release memory
    free(front);
    p_queue->count--;
    return 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!)
    if(p_queue->count!=0){p_queue->idx_tail=(p_queue->idx_tail+1)%p_queue->capacity;}

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

    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
    return p_queue->p_values[p_queue->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->idx_tail=(p_queue->idx_tail-1)%p_queue->capacity;
    if(p_queue->idx_tail==-1){p_queue->idx_tail=p_queue->capacity-1;}

    p_queue->count--;
    return value;
}

int aq_pop_front(ArrayQueue *p_queue) {
    int value = aq_front(p_queue);

    p_queue->idx_head=(p_queue->idx_head+1)%p_queue->capacity;

    p_queue->count--;
    return value;
}

### Activity 7: Algorithm analysis
The time compexity of find_sum_naive, using using two nested for loops to interate through the given array of numnbers, is relativily high due to alot of the double work being done by the for loops. As the array increases in size the time complexity would grow quadratically with it, making it O(n^2).

int find_sum_naive(const Array *array, int target, int *count) {
    for (int i = 0; i < array->count; i++) {
        int sum = 0;
        for (int j = i; j < array->count; j++) {
            sum += array->values[j];

            if (sum == target) {
                // found!
                *count = j - i + 1;
                return i;
            }
            else if (sum > target)
                break;
        }
    }

    return -1;
}

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

    // 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
        aq_push_back(&q, array->values[i]);
        sum+=array->values[i];
        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 i - q.count + 1;
        }
    }

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

### Activity 10: Benchmark the three algorithms
**The Daytona 500 Leaderboard:**

### Activity 11: Time complexity
Acording to the data gathered above all of the data structurs scale liniarly with time complexity O(n). Dividing the run times from 1M and 2M results in roughly twice the amount of time needed for 2M.

### Activity 12: Explain the impact of the chosen data structure
When looking at the scaling factor of the algorithms they all scale relativly the same however it is obvoius from the run times the the Array queue performs the best out of the three. I suspect the reson to lie in the fact that circular arrays need to be expanded less than a linked list or a pointer array.
## Look back

### What we've learnt

This week I leaned about two new abstract linear data structures that can be applied on both arrays and linked lists. The data structures are good for cases where the user only needs to have access to a part of the whole datastructre.

### What were the surprises

What suprised me this week was the application of a circular array. This new way of using an array is a bit strange to think about in the begining however turned out to be extremely efficient.

### What problems we've encountered

This week was rather problem free.

### What was or still is unclear

I dont have any unaswered questions from this week.

### How did the group perform?

N/A