# Week 4 - Stacks and Queues

## Team

Team name: E
Date:05/04/2022
Members: Casian Ionescu, Nikola Zahariev, Attila Poldan, Alexandra Melei

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

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

1) Table representing the differences between FIFO and LIFO

| FIFO | LIFO |
| ----------------------------- | --------------- |
| It stands for First-In-First-Out approach in programming. | It stands for Last-In-First-Out approach in programming. |
| In this, the new element is inserted below the existing element, So that the oldest element can be at the top and taken out first. | In this, the new element is inserted above the existing element, So that the newest element can be at the top and taken out first. |
| Therefore, the first element to be entered in this approach, gets out First. | Therefore, the first element to be entered in this approach, gets out Last. |
|In computing, FIFO approach is used as an operating system algorithm, which gives every process CPU time in the order they arrive.|In computing, LIFO approach is used as a queuing theory that refers to the way items are stored in types of data structures.|
|The data structure that implements FIFO is Queue.|The data structure that implements LIFO is Stack.|

2) Stack is also known as LIFO because only most recently inserted object can be removed from the container or data str. at a time.

### Activity 2: Stacks and LIFO

A letter means push (i.e., of that letter) and an asterisk means pop in the following sequence. Give the sequence of values returned by the pop operations when this sequence of operations is performed, from left to right, on an initially empty stack.
E A S * Y* Q U E * * * S T * * * I O * N * * *

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

### Activity 3: Pushes and pops

Check if theese are possible.
A number means push (i.e., of that letter) and an asterisk(*) means pop in the following 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 * (can't pop the 0 before the 1)

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 * 6 * 9 *

### Activity 4: Communication through a linked list

1: The consumer recives the "Hello world!" string.
2: The consumer recives the "Hello world!" string in this case too.
In these two cases due to the consumer and producer inserting/removing letters from opposit ends of the list, the order of the letters remain the same.

3: The consumer recives the string "!dlrow olleH"
4: The consumer recives the same string as in the 3rd example. "!dlrow olleH"
Because both the consumer and the producer inserts/removes from the same side of the list the order of the letters flip. The message recived will be backwards compared to the message sent.

### Activity 5: FIFO and queues

Record your answer here:
A letter means push (i.e., of that letter) and an asterisk means pop in the following sequence.
Give the sequence of values returned by the pop operations when this sequence of operations is
performed, from left to right, on an initially empty stack.

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

|E|A|S|Y|Q|U|E|S|T|I|O|N|
-------------------------
FIFO means that we pop the elements of the queue in the order they were pushed in.

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

Record your answer here
Linked list is much better for this use. On average the time complexity of adding for the array is O(1), unless for the worst case scenario where insetion is only possible after resizing.
In conclusion, the linked list does not offer any disadvantages or worst cases, whereas the array can prove to be slower in some cases.
### Activity 7: Time complexities, once again
Circular array:
| 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;
}

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

### Activity 9: Clock arithmetic

size_t buffer_rear(const buffer_t * queue) 
{
    return (queue->head + queue->count) % queue->capacity;
}

Record your answer here

### Activity 10: Writing into a circular buffer

size_t buffer_write(buffer_t *queue, char value)
{


    size_t after_rear = buffer_rear_to_append(queue);

    if(queue->count < queue->capacity)
    {
        queue->data[after_rear] = value;
        queue->count++;
    }
	
    for(int i = 0; i < queue->capacity;++i)
    {
		printf("Character: %c at index: %d\n",queue->data[i],i);

    }
}

### Activity 11: Reading from a circular buffer

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

Record your answer here

### Activity 12: Testing the queue

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

Record your answer here

### Activity 13: Fullness and emptiness

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

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

All of the code implimentation:

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

size_t buffer_rear(const buffer_t * queue)
{
    size_t rear =  (queue->head + queue->count) % queue->capacity;
    return rear;
}

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

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

size_t buffer_write(buffer_t *queue, char value)
{


	size_t after_rear = buffer_rear_to_append(queue);

	if(queue->count < queue->capacity)
	{
		queue->data[after_rear] = value;
		queue->count++;
	}
    
	for(int i = 0; i < queue->capacity;++i)
	{
		printf("Character: %c at index: %d\n",queue->data[i],i);
	}
}

char buffer_read(buffer_t * queue)
{
		char value = queue->data[queue->head];

		 if (queue->head != queue->capacity)
		 {
			 queue->head++;
			 queue->count--;
		 }
		 else
		 {
			 queue->head = 0;
			 queue->count--;
		 }
		 return value;

}

 int main(void)
 {
	 buffer_t buffer;
	 buffer_init(&buffer, 10);
	 char c = getchar();
	 while (c != '#')
	 {
		 if (c == '*')
		 {
			 if(buffer_empty(&buffer))
			 {
				 printf("\nBuffer is full! PLease insert values first, before trying to read from the circular buffer!\n");
			 }
			 else
			 {
				 printf("Read: '%c'\n", buffer_read(&buffer));
			 }
		 }
		 else if (c != '\n')
		 {
			 if(buffer_full(&buffer))
			 {
				 printf("\nThe buffer is full! Try again next time!\n");
			 }
			 buffer_write(&buffer, c);
		 }
		 c = getchar();
	 }
	 buffer_destroy(&buffer);
	 return 0;
 }

Record your answer here

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