Well, its a list with a difference! When I call it a List, it has to hold data of same type only; meaning, you can have a stack of either books or coins or anything which can be possibly stacked but you can't have a stack having books and coins both in it. You know what will happen! The stack will get imbalanced and its elements will fall down but that's not the desirable situation.
We are talking about the most idle case when we are dealing with computers, in which you can add an element from the TOP and take off and element from the TOP only. You can keep on adding elements to the stack till the time the stack is not imbalanced (i.e starts overflowing) and you can remove elements from the stack till the time its not empty.
In a list, you can add or delete elements at any position, but in a Stack you'll have to follow the LIFO (Last In First Out) principle. The last element added to the Stack can be the only one to be deleted first. Follow the example -
I have the following elements with me - 14, 23, 1, 4, 45(all integers) and I have a Stack with the upper limit set to 5. So, as you can see, I can accommodate all my elements in that stack.
 | Initially, the STACK is empty and the TOP of the STACK is pointing to the BOTTOM of the STACK. Stage [A]: We added 14 and TOP now points to it. Stage [B]: 23 is PUSHed and TOP is incremented by 1. Stage [C]: The STACK is FULL, as the upper limit was set to 5. Stage [D]: The TOPmost element has been POPed. The TOP gets decremented by 1. Stage [E]: 45, 4, 1 and 23 have been POPed and TOP is now pointing to the bottom most element. |
Every time you Push() an element inside the Stack, the TOP of the Stack gets incremented by 1 and vice-versa. When the STACK is empty, the BOTTOM and TOP of the STACK are same and pointing to the empty STACK. If you try to PUSH more elements than the upper limit of the STACK, it will cause in an overflow of data and vice-versa.
OK, why do we need such a data structure? Well, Stacks help computer in unfolding the recursive jobs; used in converting an expression to its postfix form; used in Graphs to find their traversals (we have seen that); helps in non-recursive traversal of binary trees (we'll see this) and so on....
0 comments:
Post a Comment