Stack

In our last Episode 5 (https://www.garudax.id/pulse/linked-list-osman-mohammed/?trackingId=qFJRRqe1W0KV8OfeMY6tYg%3D%3D) we learned about Linked List. In this episode, we are going to learn about the below things on Stack data structure.

1) What is Stack?

2) Architecture and Characteristics?

3) Operations and their Run Time Complexity?

4) Run Time Complexity Summary?

5) Examples of Real Word Scenarios where you can use stack?

So, let's get started.

1) What is a Stack?

The stack is a linear data structure that follows a certain way to perform operations on data.

What is this certain way called?

• Last In First Out(LIFO)
• or
• First In Last Out(FIFO)

2) Architecture and Characteristics?

The reason we call stack data structure as a stack because it behaves exactly like a stack of real-world objects as shown in the below pic.

For example, let's say if we have a bunch of ironed shirts(left from above pic) which we want to organize in our clothing shelf, generally what we do is, we stack them on each other, the first shirt stays at bottom of the stack and the last shirt stays on top of stack likewise with trays, pennies, and boxes.

And if you want to remove the first shirt which is at the bottom of the stack, you have to remove all the top shirts until you have reached the bottom one.

This is where the LIFO or FILO methods come into the picture like last in the stack goes first out and first in the stack goes last out. 

If you are thinking I can just lift the top two shirts and safely remove the bottom one, then what if our stack of shirts has hundred, thousand or ten thousands shirts in it, this shows you haven't read my article (https://www.garudax.id/pulse/introduction-algorithms-osman-mohammed/) which talks about Time complexity in the worst-case scenario, go read it, how can you have such a question in your mind :P:P. I was just kidding, you should always foster these types of questions in mind, that's what makes us human, our curiosity.

3) Operations and their Run Time Complexity?

• We have basic 4 operations in Stack, as shown in the below pic.

i) Push Operation: - Adding data on top of the stack. Time complexity is O(1).

ii) Pop Operation: - Removes data on top of the stack. Time complexity is O(1).

iii) Peek Operation: - Removes data on top of the stack without deleting it.

Time complexity is O(1).

iv) Empty Operation: - Check whether the stack is empty or not.

Time complexity is O(1).

• Other important points to note, if you trying to push data on to an already full stack, you will get stack overflow exception. And if you are trying to remove data from an empty stack you will get stack underflow exception.

4) Run Time Complexity Summary?

5) Examples of Real Word Scenarios where you can use stack?

In life, if you ever have to build the features listed below in your software, Give stack a thought

• Navigation(front/back)
• History of visited websites
• Undo
• And many more where the thought process involves LIFO and FIFO.

I would like to conclude episode 6 of our Season 1 here, stay tuned for episode 7.

References

• https://www.udacity.com/course/data-structures-and-algorithms-nanodegree--nd256
• Data Structures and Algorithms Made Easy in Java - Narasimha Karumanchi
• https://codewithmosh.com/p/data-structures-algorithms
• https://www.bigocheatsheet.com/

Disclaimer

This article is governed by the "Fair Use" doctrine and is only for the purpose such as criticism, comment & teaching.

Note:- This is a living article.