Week #5 - Data Types #1
Welcome back. Only one more week until Python!
Abstract Data Types
Queues are first in, first out (FIFO) data types. They work in the same way as they do in the real world. The first person in line is also the first person out.
There are enqueues and dequeues: the first, when something is assigned to enter the queue and is put last, whereas something dequeued is the first chunk of data addressed and processed.
Stack
This has the opposite property, like a stack of cafeteria trays—you don’t go for the first one added, but rather the last. This is called last in, last out (LIFO).
The operations for adding something into a stack is called pushing (adding something to the top of a stack) and popping (removing something from the top of the stack.)
Resizing Arrays
Say you’re writing a program and you want to deal with a shifting/dynamic amount of data, so you don’t want to hardcode in a number smaller than the potential required amount of bytes, but you also don’t want to hardcode something that so grossly overestimates the number of bytes needed to properly store the desired data in the computer’s memory. What’s the big idea? Too little allocated memory won’t be enough, and too much would be too inefficient and could cause performance issues.
The solution, then, is to dynamically allocate and free up data using malloc and free; at the designated areas within the given function.
#include <stdio.h>
#include <stdlib.h>
#include <cs50.h>
int main(void)
{
int *list = malloc(3 *sizeof(int));
if (list == NULL)
{
return 1;
}
list[0] = 1;
list[1] = 2;
list[2] = 3;
// ...
int *tmp = malloc(4 * sizeof(int));
if (tmp == NULL)
{
free(list);
return 1;
}
for (int i = 0; i < 3; i++)
{
tmp[i] = list[i];
}
tmp[3] = 4;
free(list);
list = tmp;
for (int i = 0; i < 3; i++)
{
printf("%i\n", list[i]);
}
}
This program designates a pointer as an integer in an array with a data block allocation of 3. It then checks if malloc was successful, then returns NULL if it was correct. Then, int *tmp = malloc(4 * sizeof(int)); creates a new pointer and designates it to a block of memory large enough for four integers. The program loops again, checks if malloc was successful, and returns NULL.
Next, tmp[3] = [4]; copies the contents of list into tmp, and the subsequent free; line frees up the previously allocated data because the contents have already been copied.
List = tmp; effectively designates tmp as the new array which contains the four integers, and the printf line prints respectfully that which was to be printed.
x—x