# 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

LIFO refers to Last In First Out. It is a method for handling data structures where the last element is the first out. It is also obtained through the stack

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. It is often associated with the queue

### Activity 2: Stacks and LIFO
Pop Sequence :S,Y,E,U,Q,T,S,A,O,N,I,E

### Activity 3: Pushes and pops

b) 4 6 8 7 5 3 2 9 0 1 this sequence cannot occur because it is not possible to pop 0 before the 1 because it is not at the top of the stack

### Activity 4: Communication through a linked list

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

### Activity 5: FIFO and queues

Sequence: E,A,S,Y,Q,U,E,S,T,I,O,N

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

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

### 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) |

### Activity 8: Buffer initialization

//The correct version is 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;
}

The first version is correct because this function initialises the buffer so we need to allocate a piece of memory in variable "capacity" and here it s used malloc for that and in the second version the capacity it s not initialised correctly.

### Activity 9: Clock arithmetic

size_t buffer_rear(const buffer_t * queue) {
    return (queue->head+queue->count)%queue->capacity;
}

### Activity 10: Writing into a circular buffer

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

### 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/).