Hello EZ,
Today we will study about a data structure called
Stack. But before proceeding with the tutorial I would like you to read the following 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.
- Finally, this topic I posted on another forum (you will understand which forum.) quite sometime back. I am posting it here without much modification. If you find any error reply to this topic and I will correct it.
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 Stack1. 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 datatypeStackADT {
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 happens above ?First 34 is pop'd and then 5 becomes the top element and then another element i.e. 5 is pop'd 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.javapackage com.psychocoder.stack;
/**
*
* @author Psycho_Coder
*/
public interface StackInterface {
/**
*
* @param item Inserts an element into the stack.
*/
public abstract void push(int item);
/**
*
* @return Returns the element removed from the stack
*/
public abstract int pop();
/**'
*
* @return Returns true is the stack is empty
*/
public abstract boolean isEmpty();
/**
*
* @return Returns true if the stack is full
*/
public abstract boolean isFull();
/**
*
* @return Returns the top element of the array
*/
public abstract int peek();
/**
*
* @return Returns the size of the array
*/
public abstract int size();
}
JStack.javapackage com.psychocoder.stack;
import java.util.Scanner;
/**
*
* @author Psycho_Coder
*/
public class JStack implements StackInterface {
private final static int DEFAULT_SIZE = 5;
private final int[] stack;
private int top;
private final int SIZE;
private static JStack st;
private static int NO_OF_ELEMENTS;
public JStack() {
SIZE = DEFAULT_SIZE;
stack = new int[SIZE];
top = -1;
NO_OF_ELEMENTS = 0;
}
public JStack(int SIZE) {
this.SIZE = SIZE;
stack = new int[SIZE];
top=-1;
NO_OF_ELEMENTS = 0;
}
@Override
public void push(int item) {
if (!isFull()) {
stack[++top] = item;
++NO_OF_ELEMENTS;
} else {
out("Stack Overflow! Please remove some elements from stack.");
}
}
@Override
public int pop() {
int k = -1;
if (!isEmpty()) {
k = stack[top];
--top;
--NO_OF_ELEMENTS;
}
return k;
}
@Override
public boolean isEmpty() {
return top == -1;
}
@Override
public boolean isFull() {
return top == SIZE;
}
@Override
public int size() {
return stack.length;
}
@Override
public int peek() {
return stack[top];
}
private void display() {
out("The elements in the stack are : ");
for (int i = NO_OF_ELEMENTS-1; i >= 0; i--) {
System.out.print(stack[i] + " ");
}
out("\n");
}
public static void out(String data) {
System.out.println(data);
}
public static void main(String[] args) {
int item, choice;
boolean conti = true;
Scanner sc = new Scanner(System.in);
if (args.length == 1) {
st = new JStack(Integer.parseInt(args[0]));
} else {
st = new JStack();
}
while (conti) {
out("\nMenu");
out("1. Push");
out("2. Pop");
out("3. Peek");
out("4. Size");
out("5. Display");
out("6. Exit");
out("Enter your choice : ");
choice = sc.nextInt();
switch (choice) {
case 1:
out("Enter the item :");
item = sc.nextInt();
st.push(item);
break;
case 2:
int k = st.pop();
out(k == -1 ? "Stack Underflow! Please insert some elements into stack." : ("Element Poped" + k));
break;
case 3:
out("Top element :" + st.peek());
break;
case 4:
out("Size of the Stack : " + st.size());
break;
case 5:
st.display();
break;
case 6:
conti = false;
break;
default:
out("Wrong Choice. Please try agian!");
}
}
}
}
Okay so now you have understood what do you mean by stack. What if you can see it for yourself visually. For your personal better understanding I have already created an applet showing the working of a stack.
Visual StackThis applet is very simple and shows the working of a stack.
Video DemonstrationAfter a few secs pause the video and see the instructions written properly. Read further for full reference.
Link: http://www.youtube.com/watch?v=MhA3GLfd7L4
DescriptionWe have a text area and you need to write certain commands for this to work.
We need to know about the stack ADT first. A stack does the following operations :-
1. Push ; Pushes an element to the top.
2. Pop: Removes the top element
3. peek: Returns the top element.
4. size: returns the size of the stack.
We have 5 keywords here, namely - push, pop, top, size, and delay.
push and delay work as the following syntax :- <instruction> <single-space> <data>
push :- Push the data into the stack. Example : push you, push 2, push IAmDull etc
delays : delay the update of the stack and its visualization.
pop, top, size are single instructions.
pop : pops the top element.
top : Shows the top element in logs.
size : Shows the size of the stack in logs.
CodeProject Link: https://github.com/AnimeshShaw/VisualStackNote: The Code is a old but for demonstration purpose it works. I will update it later.
Okay, We are now ready to study some applications of Stack. So lets begin.
Example of an Application of StackString 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
2. Insert 'i' into Stack. We have
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 :-
We get 'n'
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;
}
AlgorithmPROCEDURE 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
}
Stacks are very useful and they reduce your workload, but it solely depends on the programmer how efficiently he uses these concepts. If you are able to make it to this end then probably you have read the entire tutorial. I hope you enjoyed it. If you have any questions or doubts then feel free to ask. Feedback would be appreciated.
Thank you,
Sincerely,
Psycho_Coder.
