Meeting #9 – (C++: Data Structures)

What are Data Structures?

Before we learn more about data structures, it’s important to first know what they are. In computer science, data structures are representations of data, and consist of functions that allows easy modification. For example, an array is a type of data structure. An array is a set of data, which can be modified (by changing values at indices) with a set of functions.

Image result for array
https://octoperf.com/img/blog/java-arrays/java-array.png

Pairs

Let’s start with a relatively simple, but extremely useful data structure. The pair is what the name implies: a pair of values.

Example:

#include <bits/stdc++.h>
using namespace std;

int main() {
pair<int, int> myPair; // creation of a pair; be sure to set the type in the angle brackets!
myPair.first = 10; // set first value of pair
myPair.second = 20; // set second value of pair
cout << myPair.first << " " << myPair.second << endl; // print contents of pair (10 20)
myPair = make_pair(10, 20); // creates a pair on the spot
}

It can be useful for representing pairs of items such as coordinates (x, y). It will also be necessary for our next data structure: the map.

Read the documentation: http://www.cplusplus.com/reference/utility/pair/

The Mighty Map

One of the most useful data structures in computer science is the map. A map allows for mapping keys to values. This can be useful for cases when you are storing data that is not numeric. This is similar to how you can access elements of an array with an index.

Image result for java key value map
Keys are mapped to values in maps.
Source: https://codingbat.com/doc/java-map1.png

For example, you might want to quickly access the phone number of a person. With a map, you can easily access the phone number by simply giving the name of the person to the map, similar to accessing an element of an array by index.

Example:

#include <bits/stdc++.h>
using namespace std;

int main() {
map<string, long long> m; // create map that maps strings to ints (names to phone numbers)
m.insert(make_pair("Devin", 6476476477)); // insert name to phone number pair into map (using pair)
cout << m["Devin"] << endl; // access phone number using name (Devin)

m["Police"] = 911; // alternatively, you can add entries to the map like this
cout << m["Police"] << endl; // access phone number using name (Police)

m["Police"] = 311; // change value in map
}

By default, maps are sorted at all times. If you do not need this feature, you can simply use unordered_map in place of a map, since it would be faster to not sort on every insert operation.

Checking if element exists and deleting it from map:

#include <bits/stdc++.h>
using namespace std;

int main() {
map<string, string> m; // create map
m.insert(make_pair("Devin", "sucks"); // add entry to map

if (m.find("Devin") != m.end()) { // check if key "Devin" is in map
cout << "Devin is in the map" << endl;
}
m.erase(m.find("Devin")); // erase element from map
}

Read the documentation: http://www.cplusplus.com/reference/map/map/

Queues & Stacks

The queue and the stack are two related data structures.

The queue is simply a list of values, where the first elements that are put in are the first elements to come out. This can be compared to a line at a store. The first customer that enters the line will be the first customer that reaches the counter.

The stack is also a list of values. However, the first elements that are put in are the last elements to come out. This can be compared to a stack of cards on a table. The first cards that you put on the stack will be the last cards to come out when pick up the cards one by one.

Image result for queue vs stack
Source: https://1.bp.blogspot.com/-nppEYjqxJJE/WNht0K_ULrI/AAAAAAAAIL4/BqFJbkzeA2475SZBV-bV-EUCD-NZ41T6gCEw/s1600/Difference%2Bbetween%2BStack%2Band%2BQueue%2Bin%2BJava.png

Example:

#include <bits/stdc++.h>
using namespace std;

int main() {
queue<int> q; // create queue
stack<int> s; // create stack

// add 1, 2, 3 to both
q.push(1);
q.push(2);
q.push(3);

  s.push(1);
s.push(2);
s.push(3);


// print out elements in queue (should show as 1, 2, 3)
while (!q.empty()) {
cout << q.front() << endl; // print front element
q.pop(); // remove front element
}

// print out elements in stack (should show as 3, 2, 1)
while (!s.empty()) {
cout << s.front() << endl; // print front element
s.pop(); // remove front element
}
}

You will notice that both have the same operations:

  • Push (add element)
  • Pop (remove the first element) (from the front)
  • Front (get the first element) (from the front)
  • Empty (check if the stack is empty)

Documentation (Queue): http://www.cplusplus.com/reference/queue/queue/

Documentation (Stack): http://www.cplusplus.com/reference/stack/stack/


Fun Fact: https://stackoverflow.com came from running out of memory (a Stack Overflow error). The RAM of computers works very similar to the Stack Data Structure, with functions such as push and pop. Hence when the stack of a computer is full, it crashes with Stack Overflow.

Real-life Applications of the Stack Data Structure

Worth looking at (double ended queue): http://www.cplusplus.com/reference/deque/deque/

Adjacency List

We will end here with a very important data structure. Adjacency Lists are a data structure that can be used to represent graphs.

Image result for graph computer science
An example of a graph.
Source: https://courses.cs.vt.edu/csonline/DataStructures/Lessons/Graphs/graph.gif

Seems complicated to represent in code, right? 

In reality, it is quite simple. We can use what we have previously learned to represent this! A map allows us to store keys and values. As an adjacency list, the key will be the name of the node (each value of the graph), and the value will be an array of nodes that the node is connected to.

Example (of above):

#include <bits/stdc++.h>
using namespace std;

int main() {
map<string, vector<string>> adjList; // create our adjacency list

vector<string> connectedA {"B", "C", "D"};
adjList.insert(make_pair("A", connectedA)); // a is connected to b, c and d

vector<string> connectedB {"A", "C"};
adjList.insert(make_pair("B", connectedB)); // b is connected to a and c

vector<string> connectedC {"A", "B"};
adjList.insert(make_pair("C", connectedC)); // c is connected to a and b

vector<string> connectedD {"A", "E", "F"};
adjList.insert(make_pair("D", connectedD)); // d is connected to a, e and f

vector<string> connectedE {"B", "D"};
adjList.insert(make_pair("E", connectedE)); // and so on...
}

If you are storing nodes that are purely numeric, you can also use a 2D array for faster results.

Want another explanation? Check this link out: https://www.geeksforgeeks.org/graph-and-its-representations/

Making your own with structs!

Of course, this is only the tip of the iceberg in terms of useful data structures. You can also make your own!

If you want to explore making your own data structures, check this link out: http://www.cplusplus.com/doc/tutorial/structures/

Challenge Problems:

Try some challenge problems (not necessarily related to data structures)!

https://dmoj.ca/problem/ccc10j3

https://dmoj.ca/problem/sandwich

https://dmoj.ca/problem/ccc07s1

Next meeting, we will be moving on to recursion!

Published by

Computer Club Executives

The account of the Computer Club Executives