---
# System prepended metadata

title: Week 4 - Stacks and Queues

---

# 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:
```c=
(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 
```c
// 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 
```c
size_t buffer_rear(const buffer_t * queue) {
    
}
```

Record your answer here

### Activity 10: Writing into a circular buffer
@orangedoh 
```c
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 
```c
char buffer_read(buffer_t * queue) {
    queue->count--;
    queue->head++;
    return queue->data[queue->head];
}
```

### Activity 12: Testing the queue
@yazantayeh 
```c
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 

```c=
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/).
