Stack is a linear Data Structure that follow data insert and remove operations in LIFO (Last In First Out) order. Stack only allows access to one data element called top. In the Stack both data insertion and removal only can happen in top end.
To track the state in a Stack top variable is use as a pointer. When a new element added to the stack value of the top is incremented by (+1) and when element getting removed top is decrement by (-1). Stack can be implemented using a Linked List or an Array. In this article we are going to implement stack using array data structure.
Why Stack Over Array
The implementation of stack class is useful to special scenarios. Compared to an array stack has more data privacy restriction and specific purpose which is follow the last in first out order. In a define array we can access data elements using indexes but in stack we can only use the pre-define interface methods like push and pop to access data elements. So user can’t remove or assign new values to the stack positions like in the array.
Real World Scenario Example
Plates of Stack
Think you’re at a local restaurant buffet. You can see stack of plates are placed at front corner. Now you are going to get plate from that. Think which plate you are going to take. You may have different thoughts on this. However, if you follow the order you have to take the top plate from the stack. Likewise, everyone behind you have to follow same order.
Methods
- push() – push method is use to insert new elements to the stack
- pop() – pop method is use to remove top element from the stack
- peek() – peek method is use to return top element of the stack without removing it
- isFull() – isFull will return true if stack is reach to its max capcity
- isEmpty() – isEmpty will return true if the stack have 0 data elements
Stack Class
Stack Class include three properties which are maxSize, stackArray[] and top. Array is the data structure use to store data in the stack.
class Stack {
private int maxSize;
private int[] stackArray;
private int top;
//overloaded constructor
Stack(int size) {
maxSize = size;
stackArray = new int[maxSize];
top = -1;
}
//methods are going here
}push()
Push method use to insert new element into the stack array. To insert element in to stack push method include one passing argument.
public void push(int j) {
top++;
stackArray[top] = j;
}Although above function can use to insert new data element into the Stack Array it is vulnerable to an array boundary error. In a stack array full scenario (top == maxSize) this function will throw an ArrayIndexOutOfBoundsException error. To avoid this situation we need to pre check the stack is full or not before insert new data into the stack.
public void push(double j) {
if (top == (maxSize - 1)) {
System.out.println("Stack isFull");
}
else {
//long way
top++;
stackArray[top] = j;
}
}Top value variable use to orderly insert data into stack array position. Before each data insertion top value need to be increment by 1. Without using two code lines to achieve this using pre-increment we can write this in one line.
public void push(double j) {
if (top == (maxSize - 1)) {
System.out.println("Stack isFull");
}
else {
//short way
stackArray[++top] = j;
}
}pop()
Pop method use to return last inserted inserted data element and to delete that data element from the stack array. Like we check the boundary condition in push method in the pop method we need to make sure stack array is not empty before returning the last inserted value from the stack. Also, in pop method after each return top value gets decrement by 1.
public double pop() {
if (top == -1) {
System.out.println("Stack isEmpty");
return -99;
}
else {
return stackArray[top--];
}
}peek()
Someway peek method is similar to the pop method but like in the pop method peek method doesn’t delete last data element from the stack. It’s only functionality is return the last inserted data element from the stack.
public double peek() {
if (top == -1) {
System.out.println("Stack isEmpty");
return -99;
}
else {
return stackArray[top];
}
}isFull() and isEmpty()
These two methods can be use to verify the stack status is full or empty. If the stack is full isFull method will return true and if the stack is empty isEmpty method will return true.
//check stack is empty
public Boolean isEmpty() {
return (top == -1);
}
//check stack is full
public Boolean isFull() {
return (top == (maxSize-1));
}Using isEmpty() and isFull() we can replace if conditions in the push(), pop() and peek().
Addition to above methods we can implement methods return current data position and no of data elements in the stack array.
public class Stack {
private int maxSize;
private double[] stackArray;
private int top;
public Stack(int maxSize) {
this.maxSize = maxSize;
stackArray = new double[maxSize];
top = -1;
}
public void push(double j) {
if (top == (maxSize - 1)) {
System.out.println("Stack isFull");
}
else {
stackArray[++top] = j;
}
}
public double pop() {
if (top == -1) {
System.out.println("Stack isEmpty");
return -99;
}
else {
return stackArray[top--];
}
}
public double peek() {
if (top == -1) {
System.out.println("Stack isEmpty");
return -99;
}
else {
return stackArray[top];
}
}
public Boolean isEmpty() {
return (top == -1);
}
public Boolean isFull() {
return (top == (maxSize-1));
}
}Example Problems Solves Using Stack
- Reversing a String
- Coding syntax error checking
- Parenthesis Checker
- Prefix Postfix notation validator