 |
| Simple representation of a stack (Photo credit: Wikipedia) |
Hello Everyone,
Today we will study about the data structure called Stack. But before roceeding with the tutorial I would like to read the following readers note.
Reader's Note :
Today we will study about the data structure called Stack. But before roceeding with the tutorial I would like to read the following readers note.
Reader's Note :
- You must not be a novice at programming.
- You have read this thread : A Brief Introduction to Data Structures.
- Have patience and read till the end of this paper.
Now we are good to start, So, Let's Begin.
Stack : A stack is a particular kind of abstract data type or collection in which the principal (or only) operations on the collection are the addition of an entity to the collection. The operations that are performed on the the stack are push which means to insert an element at the top of the stack and pop which means to remove the top element from the stack.
Stack follows LIFO (Last In First Out) Principle, that is the element which is inserted into a collection last is taken out first from the collection as well.
The concept of stack data structure is from from development point of view and it has found numerous applications, include system level design and making efficient processes.
Applications of Stack
1. Data Parsing
2. Compiler Designing.
3. Recursion
4. Solving numerous Classical problems like Tower of Hanoi.
5. System Memory Management.
6. Reversing String.
7. Mathematical Expression evaluation. (Converting them from infix to postfix and then manipulating evaluating them)
8. Backtracking.
etc...
Stack as an Abstract datatype
StackADT {
push(item) : insert the item into the stack
pop() : removes the top element.
size() : Returns the size of the stack.
isEmpty() : checks whether the stack is empty or not.
isFull() : checks whether the stack is full or not.
}
Now let us understand the concept of stack better by taking an example :-
Suppose we consider an array of the following elements :-
5 <--- Top element
6
7
8
9
Now we push another number onto the stack, say 34, then our stack has the following structure :-
34 <--- Top element.
5
6
7
8
9
So it is evident that the most recently inserted items are push onto the top of the stack following the LIFO principle. Again we push another number into the stack, say 2, just following the above concept we have the following :-
2 <--- Top element.
34
5
6
7
8
9
We have understood the push operation and so lets see how does pop works. Lets pop once from the above array and the array becomes :-
34 <--- Top element.
5
6
7
8
9
As you can see the top element was poped from the stack and the next element that is 34 becomes the top element. Okay so lets pop two more elements and then the stack has the following structure :-
6 <--- Top element.
7
8
9
What happened above ?
First 34 is poped and then 5 becomes the top element and then another element i.e. 5 is poped and 6 becomes the top element.
I hope you have understood the concept of stack. Since we have understood the concept of stack and so lets write some code now. I will use Java to write the code. We create an interface to understand the concept of our ADT.
StackInterface.java
JStackArray.java
You can find the Java Generic Implementation of Stack Here
A Visual or Animated Representation of Stack can be found here
Okay, We are now ready to study some applications of Stack. So lets begin.
Example of an Application of Stack
String Reverse.
A Stack can be used to reverse a list, integer, string etc. Lets Look at the following example to understand the concept better :-
Suppose we have a string variable NAME and a string value of "Firun" assigned to it.
String NAME = "Firun";
Now since Stack follows the LIFO principle so if we insert every character from NAME into the stack then we will have 'n' as the top element. Then we can pop the elements we will have our Strings reversed. Look at the following working :-
1. Insert 'F' into Stack. We have
Example of an Application of Stack
String Reverse.
A Stack can be used to reverse a list, integer, string etc. Lets Look at the following example to understand the concept better :-
Suppose we have a string variable NAME and a string value of "Firun" assigned to it.
String NAME = "Firun";
Now since Stack follows the LIFO principle so if we insert every character from NAME into the stack then we will have 'n' as the top element. Then we can pop the elements we will have our Strings reversed. Look at the following working :-
1. Insert 'F' into Stack. We have
'F' <--- Top
2. Insert 'i' into Stack. We have
'i' <--- Top
'F'
3. Subsequently we insert the remaining characters as well and we get the following Stack structure.
'n' <--- Top
'u'
'r'
'i'
'F'
Now we pop all the elements from the stack and we have the following sequence :-
'u' <--- Top
'r'
'i'
'F'
We get 'n'
'r' <--- Top
'i'
'F'
We get 'u'. Also initially we had 'n' and so now we add 'u' to it and we
get "nu". Proceeding in a similar way we get the final string as
"nuriF".
I hope you understood the logic. So lets peep at the function code :-
private String reverseString(){
String m="";
for(int i=0;i<str.length();i++){
stack.push(str.charAt(i));
}
for(int i=0;i<str.length();i++){
m=m+stack.pop();
}
return m;
}
Algorithm
PROCEDURE REVERSE_STRING(M) {
INITIALISE LEN = LENGTH(M)
FOR I TO LEN:
STACK.PUSH(M[I])
FOR I TO LEN:
N = N + STACK.POP()
RETURN N
}
If you are able to make it to this end then it probably means that you
have read the tutorial. I hope you enjoyed it. If you have any questions
or doubts then feel free to ask.
Stacks are very useful and they reduce your workload, but it solely
depends on the programmer how efficiently he uses these concepts. More
applications of Stack like Conversion to different notations and Tower
of Hanoi will be covered separately.
Feedback would be appreciated. Comment in the comment section below.
Thank you,
Sincerely,
Psycho_Coder.
0 comments :
Post a Comment