# Week 4 - Stacks and Queues

## Team

Team name:Lazy Technologies
Date:22-03-2022

Members
Nafizul Habib Redwan
Rimma Davletova
Naomi Verschuur
Yazan Tayeh

| Role | Name |
|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|------|
| **Facilitator** keeps track of time, assigns tasks and makes sure all the group members are heard and that decisions are agreed upon. | Yazan Tayeh |
| **Spokesperson** communicates group’s questions and problems to the teacher and talks to other teams; presents the group’s findings. | Nafizul Habib Redwan |
| **Reflector** observes and assesses the interactions and performance among team members. Provides positive feedback and intervenes with suggestions to improve groups’ processes. | Rimma Davletova 508350 |
| **Recorder** guides consensus building in the group by recording answers to questions. Collects important information and data. | Naomi Verschuur |

## 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
FIFO - “First-In, First-Out” - oldest unit of queue is the goes out first.
LIFO - “Last-In, First-Out” - newest unit of queue is the goes out first.
The order in which elements come off a stack gives rise to its alternative name, LIFO (last in, first out).

### Activity 2: Stacks and LIFO

E A S * Y * Q U E * * * S T* * * I O * N * * *
Result: nothing

### Activity 3: Pushes and pops

@yazantayeh
The sequence that cannot accure is:

(b)- 4 6 8 7 5 3 2 9 0 1

### Activity 4: Communication through a linked list
@Nafiz
Record your answer here
!dlrow,olleH
!dlro,olleH
Hello,world
Hello,world

### Activity 5: FIFO and queues
@NaomiVerschuur
SYEUQTSAONIE

### Activity 6: Arrays, linked lists, and queues
@Nafiz
| 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)|

Record your answer here
O(n+1) , O(1)
O(1), O(1)
O(1),O(1)
Overall, we think that linked list are better used for queue because you can more easily add elements at the front of the array.

### Activity 7: Time complexities, once again
@yazantayeh
| Operation | Time complexity |
| ----------------------------- | --------------- |
| Insert / remove first element | O(1) |
| Insert / remove last element | O(n) |
| Peek first / last element | O(1) |

### Activity 8: Buffer initialization
@orangedoh

// 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 1 is right because it uses malloc function for data
### Activity 9: Clock arithmetic
@NaomiVerschuur

size_t buffer_rear(const buffer_t * queue) {
    
}

Record your answer here

### Activity 10: Writing into a circular buffer
@orangedoh

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

### Activity 11: Reading from a circular buffer
@yazantayeh

char buffer_read(buffer_t * queue) {
    queue->count--;
    queue->head++;
    return queue->data[queue->head];
}

### Activity 12: Testing the queue
@yazantayeh

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

The functions ``buffer_write`` and ``buffer_read`` were implemented correctly

### Activity 13: Fullness and emptiness
@Nafiz

int buffer_full(const buffer_t * queue)
{
    if(queue->count == queue->capacity-1)
    {
        return 1;
    }
    else return 0 ;
}
int buffer_empty(const buffer_t * queue)
{
    if(queue->head == 0 && queue->count == 0 )
    {
        return 1;
    }
    else return 0;
}

## Looking back

### What we've learnt

Difference between stacks and queues.

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