Recently I learnt about a data structure called Stack. Summarising my learnings here.
What is Stack?
Stack is a linear data structure that follows the LIFO(last in first out) or FILO(first in last out) pattern of storing data.
Just like the name suggests, imagine it like a real-life stack of wooden blocks. All these blocks are stacked on top of each other, inside a container that has only one opening. The height of this container decides how many wooden blocks can be stacked on top of each other. If we want to take the blocks out, it can only be taken out one by one(the container is open from one side only). The last block that was put in the container would be the first one to come out(LIFO), and similarly, the first block would be the last one to come out(FILO).
Stack is an ADT(Abstract data type) and has a bounded memory. If you want to read about what ADTs are, click here.
Some standard Stack operations:
Stack has some standard operations we can implement to manage our data stored in a stack. These operations are as follows:
push() : Place a new item on the stack. If there is no place for a new item, the stack is in overflow state and no new item can be placed.
pop() : Return the item at the top of the stack and then remove it. If the stack is empty, it is in underflow state.
isEmpty() : Check if the stack is empty or not.
isFull() : Check if the stack is full or not.
peek() : Access an item stored at "i" position in the stack.
change() : Change the item stored at "i" position in the stack.
count() : return the number of items stored in the stack.
display() : Display all items of the stack.
Applications of stack
Stacks can be used to store user's activity and thus use it to create an undo-redo feature. since it is a LIFO system, the last change done by the user would be the first one to get reverted. Similarly, the back-forward buttons on a web page can be made with the same concept.
Stacks can be used to reorder strings and do infix to prefix/postfix conversions. Stacks are also used for backtracking and to balance symbols in an IDE(when you open a "{", the IDE automatically adds a "}"), every time a curly bracket is opened, we push some value in stack. for every closed curly bracket that follows it, we can pop the value from stack. if the stack does not return true for isEmpty() or enters "stack underflow" state, it means that we have missed some brackets and compiler can thus throw a syntax error.
There are various other applications of stack.
Implementing Stack data structure
I have used C++ programming language to implement the stack data structure. You can see it in this GitHub repository here.
Thank you for reading. :)