Stack is a linear Data Structure. Stack is a LIFO (Last in First out) or FILO (First in Last Out). Operations of Push & Pop Occur only on One End.
Usage:
Infix to Postfix conversion
Undo the Mechanism to store commands or Instructions
Stack Complexity
- Push(): Array-based Stack push function complexity is O(1). This can be O(N) in case the element is pushed at the beginning of the Array. Otherwise, if pushed at the end of the Array the complexity is O(1)
- Pop(): Array-based Stack pop function complexity is O(1). This complexity will be O(N) (shift elements) in case the element is removed from the beginning of the Array. In case removed from the end of the array, complexity will be O(1)
- Peek(): Array-based Stack peek function complexity is O(1).
- Space complexity: O(N) N is the number of elements in the Array.
/**
* Implementation of Array Stack
*
* @author Programmer
*/
public class ArrayStack {
// Max Capacity
private final int MAX_SIZE = 100;
// array storage
private int stack [];
// current index
private int index;
// Initialize Empty Stack with this Constructor
public ArrayStack() {
// allocate memory
this.stack = new int[MAX_SIZE];
// index to zero
index = 0;
}
// Push an element on top of the Stack
public void push(int val) {
if(!isFull()) {
stack[index++] = val;
return; // function exits
}
throw new IllegalArgumentException("ERROR: Stack is Full");
}
// Pop an element from top of the Stack
public int pop() {
// we only pop, if there is an element,
if(!this.isEmpty()) {
int element = stack[index-1];
// reduce index
index--;
return element;
}
throw new IllegalArgumentException("ERROR: Stack is empty");
}
// Peak Top element of the Stack.
public int peek()
throws IllegalArgumentException{
if(!isEmpty()) {
return stack[index-1];
}
throw new IllegalArgumentException("ERROR: Stack is empty");
}
// Check if Stack is empty
public boolean isEmpty() {
return index == 0;
}
// Check if Stack is Full
public boolean isFull() {
return index == MAX_SIZE;
}
// Get the Size of Stack
public int size() {
return index;
}
// Print the Stack to the Standard output
public void print() {
if(this.isEmpty()) {
System.out.println("Stack is Empty");
}
for(int i=0; i<index; i++) {
System.out.printf("%-10d", stack[i]);
}
System.out.println("");
}
}
import java.util.Random;
/**
* Test the Stack Implementation.
*
* @author Programmer
*/
public class ArrayStackTest {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// Create Stack
ArrayStack stack = new ArrayStack();
// Random object
Random random = new Random();
// add new Elements
System.out.println("Testing push Function:");
for(int i=0; i<5; i++) {
int x = random.nextInt(100);
System.out.printf("Pushing %d on top of Stack%n", x);
stack.push(x);
System.out.printf("Stack Size is: %d%n", stack.size());
System.out.printf("Top element of Stack: %d%n", stack.peek());
System.out.println("Current Stack is:");
stack.print();
System.out.println("\n");
}
// Pop Elements from stack
System.out.println("Testing Pop Function: ");
while(!stack.isEmpty()) {
System.out.printf("Stack Size is: %d%n", stack.size());
System.out.printf("Top element of Stack: %d%n", stack.peek());
int x = stack.pop();
System.out.printf("%d removed from top of Stack%n", x);
System.out.println("Current Stack is:");
stack.print();
System.out.println("\n");
}
}
}
Views: 3