# Week 4 - Stacks and Queues

## Team

Team name:
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. | |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | |

## Activities
Make sure to have the activities signed off regularly to ensure progress is tracked.

Set up a project in CLion to write the small programs needed in some of the activities.

### Activity 1: LIFO vs FIFO

Omdat een stack alleen de een boven op kan invoegen dus last in, en een boven op kan uitvoegen dus first out.

### Activity 2: Stacks and LIFO

ea
ea
eaqu
eaq
ea
eas
ea
e
ei
ei
e
-1

### Activity 3: Pushes and pops

b kan niet omdat 1 voor nul staat dus altijd eerst 1 zou komen

### Activity 4: Communication through a linked list

1. Hello, world!
2. Hello, world!
3. !dlrow ,olleH
4. !dlrow ,olleH

### Activity 5: FIFO and queues

easyquestion

### Activity 6: Arrays, linked lists, and queues

| Operation | Array | Linked List |
| --------------------------------- | --------------- | -------------- |
| Insert / remove **first **element |O(n)|O(1) |
| Insert / remove **last**element |O(1)|O(1)|
| Peek first / last element |O(1)|O(1) |

(doubly)
Linked List

### Activity 7: Time complexities, once again

| Operation | Time complexity |
| ----------------------------- | --------------- |
| Insert / remove first element | O(1) |
| Insert / remove last element | O(1) |
| Peek first / last element | O(1) |

Record your answer here

### Activity 8: Buffer initialization

// version 1
void buffer_init(buffer_t *queue, size_t capacity) {
    queue->head = queue->count = 0;
    queue->data = (char*) malloc(capacity * sizeof(char));
    if (queue->data != NULL) queue->capacity = capacity;
    else queue->capacity = 0;
}

// version 2
void buffer_init(buffer_t *queue, size_t capacity) {
    char data[capacity;]
    queue->head = queue->count = 0;
    queue->data = data;
    queue->capacity = capacity;
}

Program to test:

int main(void) {
	buffer_t queue;
	buffer_init(&queue, 100);
	for (int i = 0; i < 100; i++) queue->data[i] = '?';
	buffer_destroy(&queue);
}

Record your answer here

### Activity 9: Clock arithmetic

size_t buffer_rear(const buffer_t * queue) {
}

Record your answer here

### Activity 10: Writing into a circular buffer

void buffer_write(buffer_t * queue, char value) {
}

Record your answer here

### Activity 11: Reading from a circular buffer

char buffer_read(buffer_t * queue) {
}

Record your answer here

### Activity 12: Testing the queue

int main(void) {
    buffer_t buffer;
    buffer_init(&buffer, 10);
    char c = getchar();
    while (c != '#') {
	    if (c == '*') printf("Read: '%c'\n", buffer_read(&buffer));
	    else if (c != '\n') buffer_write(&buffer, c);
	    c = getchar();
    }
    buffer_destroy(&buffer);
    return 0;
}

Record your answer here

### Activity 13: Fullness and emptiness

// returns 1 if the buffer is full, 0 otherwise
int buffer_full(const buffer_t * queue) {
}

// returns 1 if the buffer is empty, 0 otherwise
int buffer_empty(const buffer_t * queue) {
}

Record your answer here

## Looking back

### What we've learnt

Formulate at least one lesson learned.

### What were the surprises

Fill in...

### What problems we've encountered

Fill in...

### What was or still is unclear

Fill in...

### How did the group perform?

How was the collaboration? What were the reasons for hick-ups? What worked well? What can be improved next time?

> Written with [StackEdit](https://stackedit.io/).