Stack | Data Structure
February 28, 2020 by Moe Chehade
What is Stack Data Structure?
Think of a stack as real physical pile of items, from a programming perspective you could say it is a repository of objects that are pushed or popped out. In order to prepend and delete items, such operations take place at the top of the stack in a particular order. we can use the Push() function to add elements and pop() function to remove elements. This behaviour works on the principle of Last-In-First-Out(LIFO) last item that was added is first item to be removed.
Stack Implementations
Stack is an Abstract Data Structure. Its implemented by using an array and it is supported by several programming languages such as C, C++, Java, C#, Python etc…
The following operations can be used in a stack:
Push() is used for adding elements on top of a stack. A helpful analogy would be to think about a stack of plates, would you be able to a plate from the middle? Not a good idea! You would want to add a plate from the top of the stack. in order to do that we need to check if there is a space to add items. What if it was full? the element would have to wait in a Queue.
As you can see the above snippet of code, we created a stack class which contains a constructor, then we set the elements equal to an array to implement stack.
A constructor is similar to a blueprint. One of my favourite analogies is the “blueprint” of a house. The constructor is a like a blueprint of a house. You can use the same blueprint to construct many houses. It is the same in classes and constructors, where you can call that constructor anytime and use the same instructions in it.
After having the constructor which has the empty array, we want to use the push function to push elements into the stack, we pass the push function the element we wanna push as an argument and push into the elements stack.
pop() is used to remove elements from top of stack, same as the plate analogy we mentioned above, you can not remove plates from the middle or bottom of the stack, you have to remove from the top. Before popping an item from the stack, you must check whether the stack is empty or still has items to be removed.
Stack Applications
There is a number of applications using Stack Data structure. Most common use of this data structure are:
1- Reverse Strings
2- Backtracking
3- Expression Conversion(Infix to Postfix, Postfix to Prefix conversion
Reverse strings: is one of stack’s applications which you reverse a string. You push a word to the stack letter by letter and then delete or pop letters from the stack.
Step1 : Create a stack
Step2 : Push all characters one by one
Step3: Pop all characters one by one and put them into an empty array
Step4: Finally convert them into a string
Backtracking: If you want to access the most recent element in a stack of data elements you need an algorithmic-technique for problem solving that uses recursions called Backtracking. It is implemented by building solutions incrementally, then start removing solutions which fail to satisfy the constraints of the problem at any point of time.
A great video explaining the algorithm of backtracking:
