# Week 4 - Stacks and Queues

## Team

Team name:Error
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. |Hoang Minh Le(511907) |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. |Kaloyan Zhekov(511216) |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. |Thanh Tran (516467) |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Hoa than (487272) |

## 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** is acronyms of Last In First Out. It is a method of handling data where the first element will be processed last and vice versa, the last element will be processed first.

**FIFO** is acronyms of First In First Out. This is another method of handling data where first element will be processes first and the last element will be process last

**Stack** is a linear data structure and it follows the principal of LIFO – the last inputted element will be the first element come out.
### Activity 2: Stacks and LIFO

Record your answer here
SYEUQTSAONIE

### Activity 3: Pushes and pops

(b) 4 6 8 7 5 3 2 9 0 1
The correct one is: 4 6 8 7 5 3 2 9 1 0

### Activity 4: Communication through a linked list

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

### Activity 5: FIFO and queues

Record your answer here
Value in return after each deque
1. E
2. A
3. SYQ
4. UES
5. T
6. ION

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

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

Record your answer here

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

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
The right version is the first one, because it allocates memory for the queue and updates that memory if needed, while the second version is just initializing a character array with the 'data' member values and do not allocates memory;

### 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) {
    queue->data[buffer_rear(queue)] = value;
    ++queue->count;
}

Record your answer here

### Activity 11: Reading from a circular buffer

char buffer_read(buffer_t * queue){
    if(queue->count == 0) return 0;
    queue->count--;
    queue->head = (queue->head + 1) % queue->capacity;
    return queue->data[queue->head];
}

Record your answer here

### Activity 12: Testing the queue

#include <stdio.h>
#include <stdlib.h>

typedef struct buffer {
    size_t head;
    size_t count;
    size_t capacity;
    char *data;
} buffer_t;

void buffer_destroy(buffer_t *queue) {
    free(queue->data);
    queue->data = NULL;
}

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;
}

void buffer_write(buffer_t * queue, char value) {
    for(int i=0;i<queue->capacity;i++){
        queue->data[i] = value;
        queue->count++;
    }
}

char buffer_read(buffer_t * queue){
    if(queue->count == 0) return 0;
    queue->count--;
    queue->head = (queue->head + 1) % queue->capacity;
    return queue->data[queue->head];
}
// returns 1 if the buffer is full, 0 otherwise
int buffer_full(const buffer_t * queue){
    return (queue->count == queue->capacity);

}
// returns 1 if the buffer is empty, 0 otherwise
int buffer_empty(const buffer_t * queue){
    return (queue->count == 0);
}

int main(void) {
    buffer_t buffer;
    buffer_init(&buffer, 1);
    char c = getchar();
    while (c != '#') {
        if (c == '*') printf("Read: '%c'\n", buffer_read(&buffer));
        else if (c != '\n') buffer_write(&buffer, c);
            c = getchar();
    }
    printf("%d\n", buffer_full(&buffer));
    printf("%d\n", buffer_empty(&buffer));
    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){
    return (queue->count == queue->capacity);

}
// returns 1 if the buffer is empty, 0 otherwise
int buffer_empty(const buffer_t * queue){
    return (queue->count == 0);
}

Record your answer here

## Looking back

### What we've learnt

Formulate at least one lesson learned.

### What were the surprises

There is no surpries
### What problems we've encountered

We have some problem to do Activity 9

### What was or still is unclear

We still unclear about Activity 9

### How did the group perform?
Good, everyone cooperates and works together

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