Stack Basics
In computer science, a stack is an abstract data type, which supports two main operations: push(Element e) and pop().
push(Element e) – Adds the element e at the top of the stack.
pop() – removes the element at the top of the stack.
All operations takes place at the top of the stack. And based on the operations the top of the stack changes. If we push() an element e onto the stack, the index of the element e becomes the top of the stack. If we pop() the element from the stack, then the index of the element below it becomes the top of the stack.
A stack can be imagined as a pole fixed to the ground.
The operations can be imagined as –
push(Disc c) – add Disc c to the pole from the top.
pop() – remove one Disc, which is at the top, from the pole.
Below figure shows the basic stack operations in the context of pole and disc.
Implementation
A stack may be implemented to have a fixed capacity or variable capacity.
We will see how to implement a fix sized stack for storing Integers using an Array in Java. Though the code is in Java, the same code can be used in c/c++ with minor modifications.
First we will have a variable ‘maxSize’ which will store the max size of the stack.
We will declare an Integer Array of size ‘maxSize’.
We will also have a variable ‘top’ which will maintain the index of the top of the stack.
static int maxSize = 100; //max size of the stack static int[] stack = new int[maxSize]; // stack static int top = 0; //top of the stack
Lets define the Push operation on the stack:-
static void push(Integer val) {
if (top >= maxSize) {
System.out.println("Stack is Full. Can not add element " + val);
} else {
stack[top] = val; // Add the element to the stack top
top++; // increment the top
}
}
Let us now define the Pop operation on the stack:-
static Integer pop(){
if(top<=0){
System.out.println("Stack is Empty. No element to Pop. Returning null");
return null;
}else{
top--; //decrement the stack top
return stack[top]; //return the top element
}
}
Lets call the operations on the stack from our main function :-
public static void main(String[] args) {
System.out.println(pop()); // pop() method is called on the empty stack
push(1);
System.out.println(pop()); // Returns 1
for(int i=0; i<=99; i++){ // add 100 elements, this is max size of our stack
push(i);
}
push(100); // This addition will fail due to overflow
System.out.println(pop()); // Returns 99
System.out.println(pop()); // Returns 98
}
OUTPUT :-
Stack is Empty. No element to Pop. Returning null
null
1
Stack is Full. Can not add element 100
99
98
Note:- All the fields and functions are declared static in order to avoid creating a class. The basic idea is to show the working of a stack. As far as Java is concerned, it is always better to encapsulate the data and functionality into a class and provide abstraction to the user to use this class.
Uses
Expression evaluation and syntax parsing
Backtracking
Practice problems based on stack
http://www.spoj.com/problems/ONP/
https://www.hackerearth.com/problem/algorithm/monks-love-for-food/