Stack - data structures #4

21 Apr 2020 data structure on YouTube C#

In this article I’m going to show you how to create a self-made stack data structure – which is a fundamental part of programming – with an array (or list) representation in the inside.

Stack structure

Stack data structure is one of the most fundamental structures (alongside with queue) in programming. This is mainly because the functionality is very simple, you can only add/remove items and that’s all. Of course linked list is basically doing the same, so what is the difference?

The twist is how we add/remove items! If we insert a new item (which is called Push; pushing) it goes to the top of the stack. When you remove an item (which is called Pop; popping) you are also limited in terms of which item you can remove. Automatically only the top item can be removed. On this image below you can see this concept represented with an array.

It is important to highlight that queue uses LIFO concept, which is an acronym for Last In First Out princple. In the video #1 at the bottom you can better understand how LIFO works – if you are not familiar with it yet. More detailed explanation with examples can be seen in video #1 at the bottom, where I talk about the fundamentals of Stack and Queue structures.

Based on LIFO, if you push the items (in the order of apple, berry, peach) you can see how these will be stored inside the stack (green items). If you pop the items, you will receive the inverted order of the input items. This is important, because it can be good for us in many cases.

stack representation

Coding the stack

Creating the queue class

First thing to create the class itself, which will use generic types T (if you are not familiar with this, please read my previous articles in the “other readings” section down below, especially the linked list article). I also placed a TraversalHandler delegate in order to avoid hardcoded Console.WriteLine calls inside the data structure.

1
2
3
4
5
6
7
8
9
10
11
12
13
class MyStack <T>
{
    T[] items;
    int count;

    public delegate void TraversalHandler(T content);

    public MyStack(int size)
    {
        items = new T[size];
        count = -1;
    }
}

Please note that instead of array you can use the built-in List<T> as well (or even you can use your self-made linked list class), but in that case you do not need to specify the size with the paramter in the constructor.

Adding the methods

Basically there are way too simple methods, so I will write only a few words about them here:

Push: putting inside a new item
Pop: taking out the top (next) item
Peek: taking out the top (next) item without removing it (only checking what is at the top)
Traverse: it is just an extra helping method, to help us check what are the items inside; this uses the TraversalHandler delegate

Detailed explanation about the coding can be found in video #2 below.

Videos

Video #1 - Theory of the stack (and queue) data structure

Video #2 - Coding the stack

Downloadables

You can download the full solution by clicking here.

Or use CLI with these commands and then look for the 05-QUEUE-STACK folder:

1
2
cd Desktop && mkdir Downloaded_Project && cd Downloaded_Project
git clone https://github.com/siposm/data-structures.git

siposm / blog