Abstract data type – aside from primitive data types, there are more advanced ones, called abstract data types. Some abstract data types include linked lists, queues, and stacks. Abstract data types are sometimes referred to as ADTs.
Stack – a stack is an abstract data type. Think of a stack of plates – you can only put another one on top, and you can only access the top plate. You can’t put a plate in the middle, nor can you take one from anywhere that isn’t the top.
On a stack, you can push or pop items. To push means to add something to the stack. Pop means get something from the top. Pop will return the top and remove it. Peak is another function related to stacks, which means to look at the top without taking it off.
Stacks are called LIFO structures – Last In, First Out. That’s because the last thing you pushed to the stack is the first thing to be popped.
A stack overflow is a problem when there is too much stuff on the stack, which can lead to security or stability issues. Imagine if you stacked 500 plates on top of each other. It won’t end well. Stack Overflow is also the name of a very popular and useful website where people post questions and answers related to programming. Odds are that if you google something related to a programming problem, one of the top results will be on Stack Overflow. But that’s not related to the concept of a stack overflow, where a stack has too many items on it.
Tower of Hanoi is a topic that comes up with stacks quite often. Tower of Hanoi is a game involving stacking different-sized rings on three different rods (which can be treated as three separate stacks). For this reason, an excellent way to learn the stack abstract data type is to code your own Tower of Hanoi game.
Queue – a queue is a FIFO abstract data type, meaning First In, First Out. Think of a queue or line when you’re at a grocery store. You wait for your turn. A queue abstract data type is the same concept, but in code instead of in person. There are some variations though, such as a priority queue, where VIP stuff can go ahead of the lesser items in the queue, even if they’d been waiting there longer.
An example of a priority queue is an ambulance with flashing lights getting to drive while everyone else has to pull over and let them go first.
Linked list – recall that an array is a contiguous group of things. Using things sequentially in an array is very quick and easy, but inserting something between two elements is not. In an array, if you have 50 elements and want to put something in between the first and second ones, you will have to shift all of the remaining ones over by one first. This is a very time-consuming process. If you anticipate that you will need to do many insertions in between things, it’s best to use a linked list instead, specifically a doubly linked list.
A linked list is a group of items, much like an array, but each node within the linked list points to the previous and next item (with exceptions being for the first and last elements, which can’t point both ways). The benefit of a linked list is that it’s easy to add a new node in between other nodes, but the downside is that it’s slower to go through every item in a linked list because you have to go through each one and go to its next or previous node. A regular linked list will only have a next pointer, but a doubly linked list goes both ways – next and previous.
Set – a set is a collection of unique things. In an array, you could have duplicate entries if you wanted. There can be times when that’s useful, such as for histograms, though there are more efficient ways of doing it. But a set can be useful when something only needs to exist in the collection or not, and duplicates don’t matter. Sets are not in any particular order.