# Week 4 - Stacks and Queues

## Team

>Members:
>
>- Member one
>- Member two
>
> Date: *day* *month* 2023

## Provided code

The `zip` file on Blackboard contains the C code for this week.
The project contains three *targets*: `stacks`, `queues` and `circular-buffer`.

Also, the project uses a static library that provides an array and a linked list.
If you're on Windows, then run your code on WSL.

## Activities

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

### Activity 1: LIFO vs FIFO


-LIFO stands for “last-in-first-out”. It is a method of handling linear data in which the newest added element is removed.

-FIFO stands for “first-in-first-out”. This method would remove the oldest (or first) added element instead.

-A stack follows the rule of LIFO as in a stack, the most recent memory is removed.

### Activity 2: Stacks and LIFO


Sequence over time:

EAS
EA
EAY
EA
EAQ
EAQU
EAQUE
EAQU
EAQ
EA
EAS
EAST
EAS
EA
E
EI
EIO
EI
EIN
EI
E

What is printed:

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

### Activity 3: Pushes and pops

Sequence B, 4 6 8 7 5 3 2 9 0 1, is not possible.

At the end of the sequence, somehow 0 is poped before 1 although 0 is the element at the most bottom (because 4 elements are pushed at the beginning of the sequence)

### Activity 4: Communication through a linked list

#include "deque.h"
#include "stdio.h"
#include <week4lib/list_of_char.h>

bool try_read_deque(list_t *list, char *value) {

    if (list_try_remove(list, FRONT, value)){

        return true;
    }

    else {

        return false;
    }



}


void  write_deque(list_t *list, char value) {

    list_append(list, value);

}

### Activity 5: FIFO and queues


E
EA
EAS
AS
ASY
SY
SYQ
SYQU
SYQUE
YQUE
QUE
UE
UES
UEST
EST
ST
T
TI
TIO
IO
ION
ON
N

-----------
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(n) | O(1) |
| Insert / remove **last** element | O(1) | O(1) |
| Peek first / last element | O(1) | O(1) |

A linked list is better suited to be a queque. As you can see from the chart above, array performs worse than linked list at insert/remove the first element. All other operations have the same performance.

### 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: Clock arithmetic

Record your answer here

### Activity 9: Writing into a circular buffer

bool buffer_try_write(buffer_t *buffer, char character) {

    if (buffer->count == buffer->capacity){

        return false;
    }

    buffer->data[buffer_get_rear_idx(buffer)] = character;
    buffer->count = buffer->count + 1;

    return true;
}

### Activity 10: Reading from a circular buffer

bool buffer_try_read(buffer_t *buffer, char *character) {

    if (buffer->count == 0){

        return false;
    }

    *character = buffer->data[buffer->head];
    buffer->head = (buffer->head + 1) % buffer->capacity;
    buffer->count = buffer->count - 1;

    return true;
}

### Activity 11: Testing the queue

Since all of the three functions passed the test, the program should be able to copy the file contents of output.txt to input.txt. Upon testing it, the program succeeds in copying the content. The functionality in circular-buffer.c demonstrate the usage of the concept of queque. The one end of the queque in the program reads the characters from the input and the other end records the characters to the output.

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