My Journey to Learning Data Structures from Scratch — Stacks

This is Day 1 of #100DaysOfDSA — Stack Data Structure

Source

Stacks are literally what the word “stack” means — a Pile of something or something put on top of one another. So, how will you get something that is at the bottom of the pile? You will have to remove all the above elements and then access it, right? The same is the idea with Stack Data Structures. Something that is put last on the pile, will be accessed first. It is called a Last-In-First-Out property. For example, Undo/Redo operations on MS word (let’s say), Function calls in any code are some of the many places that implement stack at the back-end.

Common operations used to play around with this data structure are —

• Push — Alias for Insertion of an element in the stack.
• Pop — Alias for Deletion of an element from the stack.
• Peek — Alias for fetching top-most element from the stack.
• isEmpty — Checks if the stack is empty of not.
• Size — Returns the size(number of elements) of the stack.

Let’s take an example and visually understand the working of all the above-mentioned operations —

Pictorial View of Stack Operation

Stacks can be implemented as Array, Linked List, Strings, etc, anything where you can implement and have a control on the LIFO property, is essentially a Stack.

Since, i will be writing all the practice problem codes in Python. So the list aliases are,

• Push == L.append()
• Pop == L.pop()
• isEmpty == len(L)==0
• Peek == L[-1]
• Size == len(L)

All the operations mentioned above are of O(1) time complexity because all movement happens at one side-end only.

So, some of the edge cases that must be part of the implementation are to check for Underflow and Overflow issue. Underflow is when you try to pop or access in the situations where the stack is already empty. Overflow happens when you try to insert in an already full-stack. Overflow is relatively unlikely to happen because most of the library implementations have dynamic allocation already implemented as part of the package. But, if you are writing Stack class, on your own, then beware.

When representing Stack using Singly Linked List then perform all the operations at head instead of tail to avoid any kind of traversal on the list and maintaining O(1) complexity. If you are not aware of what Linked List are then ignore this for now. We will again see it in future blogs.

Points to Remember

1. Last In First Out in nature.
2. Handle Underflow and Overflow.
3. Always delete the dangling node in Linked-list implementation for space management.

Practice Problems

Please star and clone my GitHub Repository — “Learning Data Structures from Scratch” to get notified on whenever I update the repository next.

prakhar21/Learning-Data-Structures-from-Scratch

P.S. As of now, i have added 2 practice problems. For next 3 days i will just do problems related to Stack and update them in the GitHub Repository and as a part of blog, I will publish the problem statements.

Also, if you are also into Machine Learning/Natural Language Processing, etc domain, just like me. Make sure to check out detailed Research Paper Walkthroughs on my YT channel.

Cheers!