DSA: Let’s Deep Dive Into the Stack

We use the stack concept in our office work.

A stack is a linear data structure used for storing the data. let’s consider the office work, a developer is working on a long-term project and the manager gives the developer to a new task which is the high priority. So the developer puts the long-term project aside and starts work on the new task. After some time the phone rings and the priority is changed as it must be answered immediately. The developer pushes the present task into the pending tray and answers the phone. after hanging up the phone the developer starts working on the priority start then starts on a long-term project.

Photo by Jeremy Bishop on Unsplash

What is a Stack: A stack is an ordered list in which insertion and deletion are done at one end, called top. The last element inserted is the first one to be deleted. Hence, it is called the Last In First Out (LIFO).

There are two things into a stack. When an element is inserting in a stack, the concept is called PUSH, and when an element is removed from the stack, called POP.

When we try to do pop from an empty stack is called underflow and when we push the data in a full stack is called overflow.

Implementation:

1. Simple array based implementation.
2. Dynamic array based implementation.
3. Linked list implementation.

• Simple array based implementation: We use static array and implementation of the basic operation.

• Dynamic Array Implementation: We face the problem in StaticArray that is Overflow because the size of the stack is fixed. So let’s make it with dynamic array, Here we will expend the size when the stack will overflow.

• Linked List Implementation: The other way of implementing stacks is by using Linked lists. Push operation is implemented by inserting element at the beginning of the list. Pop operation is implemented by deleting the node from the beginning.

So above three ways we can implement a stack. Let’s compare Array implementation and Linked List implementation

Array Implementation:

• Operations take constant time.
• Expensive doubling operating every once in a while

Linked List Implementation:

• Grows and shrinks gracefully.
• Every operation takes constant time O(1).
• Every operation uses extra space and time to deal with references.

That’s it. I hope it will help you to understand the Stack concept. Stay tuned for more topics in Data Structure.

I referenced the book of Data structure and algorithms (Narasimha Karumanchi).

Thank you for reading. Have a happy day. :)