# Week 4- Stacks and Queues

## Team

Team name: Totally Useless
Date: 09/03/2022

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

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

The acronyms LIFO stands for Last In First out and FIFO which means First In First out.
A stack is sometimes called a LIFO memory buffer because a memory buffer is a region of the memory used to temporarily store data while it is being moved from one place to another and the stack operates in a way that the last element to go in will be the last element to go out.

### Activity 2: Stacks and LIFO

The sequence of the values returned from the pop operation are the following:

S Y E U Q T S A O N I E

### Activity 3: Pushes and pops
The line "(b)" cannot occur because popping it in that order is not possible.
| Sequence | Popped Sequence |
| ----------------------------- | --------------- |
| ( a ) 4 3 2 1 0 9 8 7 6 5 | 0 1 2 3 4 ***** 5 6 7 8 9*** |
| ( b ) 4 6 8 7 5 3 2 9 0 1 | 0 1 2 3 4 * 5 6* 7 8 **** 9 *** |
| ( c ) 2 5 6 7 4 8 9 3 1 0 | 0 1 2 3 4 5 * 6 * 7 ** 8 * 9 **** |
| ( d ) 4 3 2 1 0 5 6 7 8 9 | 0 1 2 3 4 **** 5 * 6 * 7 * 8 * 9 * |

As it can be seen by the table the line b wont deliver the expected popped sequence. The popped sequence that is possible with the pops is 4 5 8 7 5 3 2 9 1 0.
### Activity 4: Communication through a linked list
"Hello, world!"
Which string does the consumer receive in case:
1. The producer inserts characters at the front of the list, and the consumer removes characters from the rear of the list?
**"!dlrow, olleH"**
2. The producer inserts characters at the rear of the list, and the consumer removes characters from the front of the list?
**"!dlrow, olleH"**
3. The producer and consumer both insert / remove characters to / from the front of the list?
***"Hello, World!"***
4. The producer and consumer both insert / remove characters to / from the rear of the list?
***"Hello, World!"***

### Activity 5: FIFO and queues
The sequence of values returned by the read operation when this sequence of operations is performed on an initially empty FIFO queue is:

E A S Y Q U E S T I O N

### Activity 6: Arrays, linked lists, and queues
| Operation | (dynamic) Array | (doubly) 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) |

The data structure (dynamic array or linked list) that is better suited to be used as a queue is the linked list because in a queue two of the most important operations is insertion/removal at the front and insertion/removal at the end and the linked list based on the table is less expensive in time complexity making it the best for the queue.

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

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

Due to the fact that the data member needs to contain an address that is dynamically allocated, version 1 is the correct initialization because it allocates memory to data using the malloc() function and then initializes the capacity based on whether or not the data was properly allocated.

### Activity 9: Clock arithmetic

size_t buffer_rear(const buffer_t *queue){
    if(queue){
        return (size_t)((queue->head + queue->count) % queue->capacity);
    }
    //In case the queue is empty
    else{
        printf("Queue is empty. Please try again or review the code");
        return NULL;
    }
}

### Activity 10: Writing into a circular buffer

void buffer_write(buffer_t * queue, char value){
    queue[buffer_rear(queue)].data=value;
    queue->count++;
}

### Activity 11: Reading from a circular buffer

char buffer_read(buffer_t * queue){
    size_t first_index = queue->head;
    char c = queue[first_index].data;
    queue->head=((first_index + 1) % queue->capacity);
    return c;
}

### Activity 12: Testing the queue

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

void buffer_destroy(buffer_t *queue);
void buffer_init(buffer_t *queue, size_t capacity);
size_t buffer_rear(const buffer_t *queue);
char buffer_read(buffer_t * queue);
void buffer_write(buffer_t * queue, char value);

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

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

size_t buffer_rear(const buffer_t *queue){
    if(queue){
        return (size_t)((queue->head + queue->count) % queue->capacity);
    }
        //In case the queue is empty
    else{
        printf("Queue is empty. Please try again or review the code");
        return 0;
    }
}
char buffer_read(buffer_t * queue){
    size_t first_index = queue->head;
    char c = queue[first_index].data;
    queue->head=((first_index +1) % queue->capacity);
    return c;
}

void buffer_write(buffer_t * queue, char value){
    queue[buffer_rear(queue)].data = value;
    queue->count++;
}

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){
    if(buffer_rear(queue) == queue->head) {
        printf("It is filled\n");
        return 1;
    }

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

## Looking back

### What we've learnt

* We understood basic principles of queues and stacks and how to perform basic operations on them.

* We learned the definitions of LIFO & FIFO and how to conceptually implement that in our week's exercises.

* We deepend our knowledge with regards to the time complexities.
### What were the surprises

* How relatively easy it was to understand queues and stacks, with limited previous knowledge.

### What problems we've encountered

* We did not encounter any problems since it was relatively easy to understand the concepts.

### What was or still is unclear

* Use of linked lists in stacks and queues? Benefits? Disadvantages?

### How did the group perform?
* Our team members worked a lot during the beginning of this week's assignment. This allowed us to concentrate more on the theory and general understanding of the queues and stacks, rather than trying to finish the exercises as soon as possible. We believe that this drastically contributed to the reduction of potential problems we could have encountered throughout the week's exercises.

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