what is a stack and its implementation of it in java

push and pop example in a stack

Tags: java, stack, data-structure, data, structure, programming

A stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out), we will implement it in java with various of its method like (push, pop, print all, clear all, indexOf).

Stack implementation in Java

let's start with a class [ "MyStack" ] and add the basic properties and methods that we will need.

1public class MyStack { 2 int maxSize; 3 int stackTop; 4 int[] myArr; 5 int numberOfElements; 6 7 public MyStack(int maxSize) { 8 this.maxSize = maxSize; 9 this.myArr = new int[maxSize]; 10 this.stackTop = -1; 11 this.numberOfElements = 0; 12 } 13 14 public boolean isFull() { 15 return this.maxSize == this.numberOfElements; 16 } 17 18 public boolean isEmpty() { 19 return this.numberOfElements == 0; 20 } 21}
  • [ "maxSize" ]: A variable we will use to Know the maximum size allowed of the stack.
  • [ "stackTop" ]: A variable that will point the last element of the stack.
  • [ "myArr" ]: An array where we will store the values.
  • [ "numberOfElements" ]: A variable that we will use to keep track of the number of elements.
  • [ "isFull" ]: A method that will return true if the stack is empty.
  • [ "isEmpty" ]: A method that will return true if the stack is full.

Push an element to Stack in Java

Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.

1public int push(int element) { 2 if (this.isFull()) { 3 // throw new Exception("Stack Overflow!"); 4 System.err.println("Stack Overflow!"); 5 System.exit(-1); 6 } 7 8 this.myArr[this.numberOfElements] = element; 9 this.stackTop++; 10 this.numberOfElements++; 11 12 return element; 13}
  • firstly, We will check if the stack is full, and if true we exit or you can throw an exception return from the method.
  • Else we will add it to the end of [ "myArr" ] and increase both [ "stackTop" ] and [ "numberOfElements" ] values by 1.
  • Finally return the element.

Pop an element to Stack in Java

Removes an item from the stack. The items are popped in the reversed order in which they are pushed.

1public int pop() { 2 if (this.isEmpty()) { 3 // throw new Exception("Stack is empty!"); 4 System.err.println("Stack is empty!"); 5 System.exit(-1); 6 } 7 8 int element = this.myArr[this.stackTop]; 9 10 this.stackTop--; 11 this.numberOfElements--; 12 13 return element; 14}
  • firstly, We will check if the stack is empty, and if true we exit or you can throw an exception return from the method.
  • Else we will store the last element in a variable [ "element" ].
  • Then decrease both [ "stackTop" ] and [ "numberOfElements" ] values by 1.
  • Finally return the poped [ "element" ].

Print all elements on the Stack in Java

1public void printAll() { 2 int i; 3 for (i = this.stackTop; i >= 0; i--) { 4 System.out.println(this.myArr[i]); 5 } 6}

We will loop throw all the elements in [ "myArr" ] in descendant from [ "stackTop" ] (Which points at the last element of the array) to 0.

Clear all elements on the Stack in Java

1public void clearAll() { 2 this.stackTop = -1; 3 this.numberOfElements = 0; 4 5 int i; 6 for (i = this.stackTop; i > 0; i--) { 7 this.myArr[i] = 0; 8 } 9}
  • Firstly, we will just change the values of [ "stackTop" ] to -1 and [ "numberOfElements" ] to 0.
  • And then we will loop all over elements in [ "myArr" ] and assign them to 0.

Retrieve an element by its index from Stack in Java

1public int indexOf(int index) { 2 if (index > this.stackTop) { 3 // throw new Exception("Inedx is out of the Stack size!"); 4 System.err.println("Inedx is out of the Stack size!"); 5 System.exit(-1); 6 } 7 8 return this.myArr[index]; 9}
  • firstly, We will check if the index is bigger than the [ "stackTop" ] variable which holds the last element index, and if true we exit or you can throw an exception return from the method.
  • Else we will return the element with the specified index.

Coming Soon

  • Peek or Top: Returns the top element of the stack.
  • Duplicate: Copy the top item's value into a variable and push it back into the stack.
  • Swap: Swap the two topmost items in the stack.
  • Rotate: Move the topmost elements in the stack as specified by a number or move in a rotating fashion.

Full implementation of the stack algorithm in Java

1 2public class MyStack { 3 int maxSize; 4 int stackTop; 5 int[] myArr; 6 int numberOfElements; 7 8 public MyStack(int maxSize) { 9 this.maxSize = maxSize; 10 this.myArr = new int[maxSize]; 11 this.stackTop = -1; 12 this.numberOfElements = 0; 13 } 14 15 public boolean isFull() { 16 return this.maxSize == this.numberOfElements; 17 } 18 19 public boolean isEmpty() { 20 return this.numberOfElements == 0; 21 } 22 23 public int push(int element) { 24 if (this.isFull()) { 25 // throw new Exception("Stack Overflow!"); 26 System.err.println("Stack Overflow!"); 27 System.exit(-1); 28 } 29 30 this.myArr[this.numberOfElements] = element; 31 this.stackTop++; 32 this.numberOfElements++; 33 34 return element; 35 } 36 37 public int pop() { 38 if (this.isEmpty()) { 39 // throw new Exception("Stack is empty!"); 40 System.err.println("Stack is empty!"); 41 System.exit(-1); 42 } 43 44 int element = this.myArr[this.stackTop]; 45 46 this.stackTop--; 47 this.numberOfElements--; 48 49 return element; 50 } 51 52 public void printAll() { 53 int i; 54 for (i = this.stackTop; i >= 0; i--) { 55 System.out.println(this.myArr[i]); 56 } 57 } 58 59 public void clearAll() { 60 this.stackTop = -1; 61 this.numberOfElements = 0; 62 63 int i; 64 for (i = this.stackTop; i > 0; i--) { 65 this.myArr[i] = 0; 66 } 67 } 68 69 public int indexOf(int index) { 70 if (index > this.stackTop) { 71 // throw new Exception("Inedx is out of the Stack size!"); 72 System.err.println("Inedx is out of the Stack size!"); 73 System.exit(-1); 74 } 75 76 return this.myArr[index]; 77 } 78} 79

example:

1public class Main { 2 public static void main(String[] args) { 3 MyStack stack = new MyStack(5); 4 5 stack.push(1); 6 stack.push(2); 7 stack.pop(); 8 stack.push(3); 9 stack.push(4); 10 stack.pop(); 11 stack.push(4); 12 stack.push(6); 13 stack.pop(); 14 stack.push(4); 15 stack.pop(); 16 stack.push(5); 17 18 System.out.println("printAll 1 starts:"); 19 stack.printAll(); 20 System.out.println("printAll 1 ends."); 21 22 stack.clearAll(); 23 24 System.out.println(); 25 26 System.out.println("printAll 2 starts:"); 27 stack.printAll(); 28 System.out.println("printAll 2 ends."); 29 } 30}
1printAll 1 starts: 25 34 43 51 6printAll 1 ends. 7 8printAll 2 starts: 9printAll 2 ends.