# Week 4 - Stacks and Queues
## Team
Team name: Big Floppa's
Date:
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. | Sam |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Marnix |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Camiel |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Sam |
## Activities
### Activity 1: LIFO vs FIFO
LIFO: **L**ast **I**n **F**irst **O**ut
FIFO: **F**irst **I**n **F**irst **O**ut
Stacks are referred to as LIFO since you can generally only acces the top. So whenever an element is added, it is also the only, and thus the first, you can access at that time.
If you could add/remove items from both bottom and the top of the stack, you would have FIFO access.
### Activity 2: Complete the stack implementation
```c=
//
// Created by Saxion on 3/5/2021.
//
#include "stack.h"
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
void stack_ensure_capacity(Stack *p_stack, int capacity) {
if (p_stack->capacity < capacity) {
// must resize
const int min_new_capacity = p_stack->capacity * 3 / 2;
if (capacity < min_new_capacity)
capacity = min_new_capacity;
p_stack->pValues = (float*) realloc(p_stack->pValues, sizeof(float) * capacity);
p_stack->capacity = capacity;
}
}
void stack_init(Stack *p_stack, int initial_capacity) {
p_stack->pValues = (float*) malloc(initial_capacity * sizeof(float));
p_stack->count = 0;
p_stack->capacity = initial_capacity;
}
void stack_free(const Stack *p_stack) {
free(p_stack->pValues);
}
void stack_push(Stack *p_stack, float value) {
stack_ensure_capacity(p_stack, p_stack->count + 1);
// add the value, update the count
// This was added
p_stack->pValues[p_stack->count] = value;
p_stack->count++;
}
float stack_peek(Stack *p_stack) {
if (p_stack->count > 0) {
// return the top value
// This was added
return p_stack->pValues[p_stack->count - 1];
}
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
// This was added
float value = p_stack->pValues[p_stack->count - 1];
p_stack->pValues[p_stack->count] = 0.0;
p_stack->count = p_stack->count - 1;
return value;
}
else {
// no values available, indicate error
return FP_NAN;
}
}
```
### Activity 3: Reverse Polish Notation
```c=
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 %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 first = stack_pop(pStack);
printf("pop\n");
float second = stack_pop(pStack);
printf("pop\n");
switch (token.operator) {
case '+': {
printf("add\n");
stack_push(pStack, first + second);
break;
}
case '-': {
printf("sub\n");
stack_push(pStack, second - first);
break;
}
case '*': {
printf("mul\n");
stack_push(pStack, first * second);
break;
}
case '/': {
printf("div\n");
stack_push(pStack, second / first);
break;
}
default:
break;
}
}
}
}
```
Calling the function
```c=
process_rpn_s("3 4 * 5 +", 17.0f);
```
Results in:
```c
push 3.000000
push 4.000000
pop
pop
mul
push 5.000000
pop
pop
add
Verifying RPN result...
------------------
Result: 17.00
```
### Activity 4: Application of queues
__3 applications:__
- Stealing algorithm (https://en.wikipedia.org/wiki/Work_stealing)
- palindrome checker
(a palindrome is a word that reads the same forwards as it does backwards, for example "racecar")
- undo-redo operations in software applications
### Activity 5: Implement a Queue using a linked list
```c=
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
```c=
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 tail = aq_tail_index(p_queue);
if (tail >= 0) {
p_queue->p_values[(tail + 1) % p_queue->capacity] = value;
p_queue->count++;
} else {
p_queue->p_values[p_queue->idx_head] = value;
p_queue->count++;
}
}
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;
p_queue->count--;
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;
}
void aq_print(const ArrayQueue *p_queue) {
for (int i = 0; i < p_queue->capacity; i++) {
printf("%d: %d\n", i, p_queue->p_values[i]);
}
printf("head index: %d, tail index: %d\n", p_queue->idx_head, aq_tail_index(p_queue));
}
```
Result:
```
count must be 1
PASS
idx_head must be 0
PASS
count must be 4
PASS
idx_head must be 0
PASS
popped value must be 1
PASS
count must be 3
PASS
idx_head must be 1
PASS
count must be 4
PASS
idx_head must be 1
PASS
index 0 must contain 5
PASS
popped value must be 5
PASS
count must be 3
PASS
idx_head must be 1
PASS
popped value must be 4
PASS
count must be 2
PASS
idx_head: 1
idx_head: 0
count must be 3
PASS
idx_head must be 0
PASS
idx_head: 0
idx_head: 3
count must be 4
PASS
idx_head must be 3
PASS
popped value must be 7
PASS
0: 6
1: 2
2: 3
3: 7
head index: 0, tail index: 2
popped value must be 6
PASS
```
### Activity 7: Algorithm analysis
`O(n^2)` want er is een nested for-loop.
### Activity 8: Solve the problem using the linked list-based queue
### 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
We hebben geleerd over Stacks en Queues en waarvoor deze handig zijn
### What were the surprises
De code die we kregen om de implementaties mee te testen zorgde voor heel veel onduidelijkheid. Hierdoor konden we de opdrachten niet succesvol voltooien.
### What problems we've encountered
We konden de opdrachten niet allemaal maken omdat we niet snapte waarom onze implementatie niet werkte. Dit omdat er meer code was om te testen dan onze implementatie.
### What was or still is unclear
Het is voor ons onduidelijk waarom we zoveel test code krijgen. Deze code staat totaal los van de opdracht en zorgt ervoor dat we onze code heel moeilijk kunnen debuggen.
### How did the group perform?
Good
Google Drive
Gist
Clipboard
Sign in with Wallet
