A warm Hello to all the readers!
There is another data structure in computer science. This is the Stack data structure. To understand a stack, it is easy to relate to the stack of plates racked in the kitchen.
A plate is put on top of other plates. See the image below.
Similarly talking in terms of data structure, each element is put on top of another element like this.
A stack data structure is also known as Last in First Out structure. In short it is termed as LIFO. In LIFO, the element that is inserted in the last is removed first. Just like stack of plates, the bottom most plate cannot be removed unless all the above plates are removed first.
What are Stack Operations?
In a stack there are two operations that can be performed. Pushing and Popping of elements in the stack.
Pushing an element means inserting it on top of the stack. And popping an element means removing it from top of the stack. Relate it to the stack of plates example described above.
When stack if full and no more element can be inserted, then pushing results in overflow. That’s stackoverflow.com 🙂 . And when stack is empty and no element can be removed, then popping results in underflow.
What is the Time Complexity of Stack Operations?
- Inserting an element – O(1) since element is inserted on the top
- Removing an element – O(1) since element is removed from the top
- Searching an element – O(n) since entire stack has to be traversed to find the matching element
- Accessing an element – O(n) Again stack has to be traversed to access it. There is no indexing like array.
What are the Real World Practical Examples of Stack?
The very basic practical implementation is to maintain the history of web pages in the web browser. We open one website, then go to next website and so on. Each website is pushed into the stack. If we want to go backward, then last website is popped from the stack.
Similarly in the text editor, when we type, it keeps on pushing in the stack. And when we do Undo, then last change is popped from the stack.