103: DATA STRUCTURES IMPLEMENTATION
Published: 2022-08-18 11:22:00

In my previous article, [102(a):Deep dive into data structures](https://dev.to/stephenkimoi/102a-deep-dive-into-data-structures-and-algorithms-1heb), I expounded more on the various types of data structures that are commonly used and theoretically explained how they are implemented.
In this article, we will get our hands a little bit dirty by practically implementing them.  
**Note:** 
*I’ve used python for implementation since it is human friendly thus can be understood by a vast number of people.*
*Link to the GitHub repository that contains the sample codes can be found in their respective sections* 

**1.Stack data structure:**
As we stated earlier, stack is a data structure that follows the LIFO principle, that is, elements that get in last come out first. Any time an element is added it goes onto the top of the stack and the only element that can be removed is the element on top of the stack. It is an example of a [linear data structure](https://www.tutorialspoint.com/difference-between-linear-and-non-linear-data-structures#:~:text=A%20Linear%20data%20structure%20have,level%20and%20in%20single%20run.)

**Types of stacks:**
There are two types of stacks:  
1. Register stack: It is a memory element present in the 
memory unit and can handle a small amount of data only. It is small compared to memory stack.    
2. Memory stack: It handles a large amount of memory data. It’s height is quite flexible as compared to register stack.  

**Applications of stack:** 
1. Reverse a word: you can push a given word to stack letter by letter then pop letters from the stack.  
2. Redo and undo features in places such as editors 
3. Backtracking algorithms, as it helps you come back from the previous state. This can be seen in games such as chess, finding your way through a maze e.t.c  
4. Forward and backward features in browsers  

**Implementation of stack:** 
Stacks can be implemented in two ways: 
1. Arrays
2. Linked lists 


**a)Implementing stacks using arrays:** 

![Implementing stacks using arrays in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s4w336pe4zfs2p07ztsh.png)

![Implementing stacks using arrays in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0guad5mlbsrxr8bayi2e.png)

![Implementing stacks using arrays in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/w3i61wmsymm051blhjiz.png)

**output**

![Implementing stacks using arrays in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/aj50pgg1402ld3lf7roo.png)

[Github link](https://github.com/Stephen-Kimoi/Data-Structures-and-Algorithims/blob/master/Data-structures/Stacks/array-stacks.py)

**b)Implementing stacks using linked lists:** 

![Implementing stacks using linked lists in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/v6ek9jum29tpw4891di6.png)

![Implementing stacks using linked lists in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9hesgy8zxbk3fkmgk7mr.png)

![Implementing stacks using linked lists in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/r3tmpu3dn6hxb3lgfjlc.png)

![Implementing stacks using linked lists in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zjbd2l65yr2vge93au2c.png)

Output: 

![Implementing stacks using linked lists in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/04blks7tzqv1klllv26q.png)
[Github link](https://github.com/Stephen-Kimoi/Data-Structures-and-Algorithims/blob/master/Data-structures/Stacks/linked-list-stack.py)

**2.Queue data structure:** 
This is also a type of linear data structure in which addition of an element takes place from one end called the rear(tail) and removal of an element takes place from the other end also called front(head).  
It follows the FIFO (first in first out) principle, meaning the first element to be inserted will be the first element to be removed.  
**Applications of queue:**
- Serving requests on a single shared resource e.g printer  
- In call center stations, queues are used to put callers on hold until a service representative is free  
**Implementation of queue:**
Queue can be implemented using:  
   - Arrays 
   - Linked lists  

**a)Implementing using arrays:**

![Implementing queue using arrays](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jlgejr4xin9aei2gn5x9.png)
![Implementing queue using arrays](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zkfwz3711z959vathfuo.png)
![Implementing queue using arrays](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8hofxtoxk8lwb3ufjzg8.png)

Output: 
![Implementing queue using arrays](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ccd02fu1d7hxa6lc49m8.png)
[Github link](https://github.com/Stephen-Kimoi/Data-Structures-and-Algorithims/blob/master/Data-structures/Queue/array-queue.py)

**b)Implementing using Queue from queue library:**

![Implmenting queue using queue library](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3tndn1v4qx5xix7vfr6e.png)

Output:
![Implmenting queue using queue library](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/unnszzzxl5fvi2d0t93t.png)

[Github link](https://github.com/Stephen-Kimoi/Data-Structures-and-Algorithims/blob/master/Data-structures/Queue/Queue-queue.py)

**3.HashMap data structure:**
As I stated in the previous article, a HashMap is a type of data structure that maps certain keys to certain values.  
**Implementation of HashMap:**
HashMaps are implemented in python using dictionaries

**Example 1:**
![Implementing hashmaps in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vy86olnorlddo9xdx0l4.png)

Output: 
![Implementing hashmaps in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zqh9icqlqm8nmnv7gmv0.png)

[Github link](https://github.com/Stephen-Kimoi/Data-Structures-and-Algorithims/blob/master/Data-structures/HashMap/hashmap1.py)

**Example 2:**
![Implementing hashmaps in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1ixfo4i6y5t4z0eksmpq.png)
![Implementing hashmaps in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/la77ymtillxdypdaf2c6.png)
![Implementing hashmaps in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bgqj4r30ps1qs25qsdpt.png)
![Implementing hashmaps in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/b8jfwfm76gutmshhs2fd.png)
Output: 
![Implementing hashmaps in python](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zauc4oyr6xtwyp05f98b.png)

[GitHub link](https://github.com/Stephen-Kimoi/Data-Structures-and-Algorithims/blob/master/Data-structures/HashMap/hashmap2.py)

**4.Graph data structure:**
Graphs are a type of non-linear data structure that arranges data as multiple nodes. They are connected together using edges. Nodes represent entities where data is stored and the relationship between nodes are expressed by edges.  
**Types of graphs:**
- Undirected: a type of graph where all the edges are bi-directional, the edges do not point at a specific direction.
- Directed graph: a type of graph where all edges are uni-directional, the edges point at a specific direction.  
- Weighted graph: a graph that has a value associated with every edge.  
- Unweighted graph: a type of graph that has no value or weight associated with the edge.  
**Applications of graph:**
- Used in social networks such as Facebook and LinkedIn 
- Used in blockchain technology, where the nodes are blocks that store many transactions while edges connect many subsequent blocks
- Google maps also uses graphs 
- It also helps define the flow of computational software programs.  
**Implementation of graphs:**
![Implementation of graphs:](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/p9vp82vs3j7f2ng8xwt1.png) 

Output:
![Implementation of graphs:](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/iwynmpqd0uxmbeowyqau.png)

[GitHub link](https://github.com/Stephen-Kimoi/Data-Structures-and-Algorithims/blob/master/Data-structures/Graphs/graphs-using-dict.py)

**5.Set data structure:**
This is a type of data structure that can store any unique values. It does not allow repeating of values 
**Applications of set data structures:**
- It is used in eliminating duplicates 
- It is used to sort, because it is ordered 
- It is also used for searching, checking whether a given 
  element is present in the in the set. 

**Implementations of set data structures:**
They can be implemented using the set() function in python 

![Implementations of set data structures](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jagtk284xdlyior5dl9m.png)

Output: 

![Implementations of set data structures](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/br3s8qlq1ylu5cadou0e.png)

[GitHub link](https://github.com/Stephen-Kimoi/Data-Structures-and-Algorithims/blob/master/Data-structures/Sets/set_function.py)

Thank you for reading this far!