Stacks

A stack is a linear data structure that works based on a rule called Last In First Out(LIFO) or First In Last Out(FILO). It follows a particular order in which operations are performed. This means that the element which is inserted last is removed first.

For example, when CDs are placed in a CD stand, then the last CD which is placed in the stand is the first one that comes out.

stacks-java-data-structures

Here, CD 1 is inserted first, followed by 2,3,4, and 5. But CD 5 is the first one to be removed from the memory.

Initially, every stack must have a particular amount of memory block, which we can call it as a capacity of the stack. So, what is the capacity and how will we decide?

We can decide it either by dynamic memory allocation or by static memory allocation. Static memory allocation is nothing but a constant memory allocation. In static memory allocation, we are simply using the concept of an array.

There are mainly three basic operations performed in the stack:

  • push(): Adds an item in the stack. If the stack is full, it is said to be an Overflow condition.
  • pop(): Removes an item from the stack.
  • peek(): Returns top element of stack.
  • isEmpty(): Return true if stack is empty, else false.

Time Complexities of operations:

push(), pop(), peek(), and isEmpty() all take O(1) time as we do not run any loop in any of these operations.

Java stack is LIFO object that extends Vector class. It has only one constructor which is empty or default constructor. So, when we create a Stack, initially it contains no items that means Stack is empty.

Stack has s TOP pointer that points to the top of the Stack element. If Stack is empty, TOP refers to the before first element location.

Applications of Stack:

  • Sentiment analysis based on reviews- latest review gives most recent scenario, so it should be given more importance to decide further action.
  • Evaluating an expression.
  • Stack is used in some scheduling algorithms.
  • Stack is used during Depth First Search(DFS).
  • Forward and backward feature in web browser.
  • Converting an infix to postfix.
  • Used in many graph algorithms like topological sorting
  • Redo-undo features in many editors like photoshop.
Example:

import java.util.Stack;
public class StackBasicExample {
    public static void main(String a[]){
        Stack<Integer> stack = new Stack<>();
        System.out.println("Empty stack : "  + stack);
        System.out.println("Empty stack : "  + stack.isEmpty());
        // Exception in thread "main" java.util.EmptyStackException
        // System.out.println("Empty stack : Pop Operation : "  + stack.pop());
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println("Non-Empty stack : "  + stack);
        System.out.println("Non-Empty stack: Pop Operation : "  + stack.pop());
        System.out.println("Non-Empty stack : After Pop Operation : "  + stack);
        System.out.println("Non-Empty stack : search() Operation : "  + stack.search(2));
        System.out.println("Non-Empty stack : "  + stack.isEmpty());
    }
}

Output:


Empty stack : []
Empty stack : true
Non-Empty stack : [1, 2, 3, 4]
Non-Empty stack: Pop Operation : 4
Non-Empty stack : After Pop Operation : [1, 2, 3]
Non-Empty stack : search() Operation : 2
Non-Empty stack : false

How push() and pop() operations work?:

As already stated, Stack data structure has TOP pointer to refer the top element of the Stack. If Stack is empty, this refers to the before first element as shown below: empty-stack-java-ds Now, Stack’s Push operation always inserts a new element at the top of the Stack. stack-push-java-data-structures Stack’s Pop operation always removes an element from the top of the Stack. pop-operation-stack-java-ds

Java Stack Methods:

  • Boolean empty(): Checks if the Stack is empty.
  • E push(E item): Pushes an element onto the top of the stack.
  • E pop(): Removes an object at the top of the stack an returns that object as the value of the function.
  • E peek(): Looks at the object at the top of the stack without removing it from the stack.
  • Int search(Object o): Returns the 1-based position where an object is on the stack.
Example:

import java.util.Stack;
public class StackExample {
    public static void main(String[] args) {
        // Creating a Stack
        Stack<String> stackOfCards = new Stack<>();
        // Pushing new items to the Stack
        stackOfCards.push("Jack");
        stackOfCards.push("Queen");
        stackOfCards.push("King");
        stackOfCards.push("Ace");
        System.out.println("Stack => " + stackOfCards);
        System.out.println();
        // Popping items from the Stack
        String cardAtTop = stackOfCards.pop();  // Throws EmptyStackException if the stack is empty
        System.out.println("Stack.pop() => " + cardAtTop);
        System.out.println("Current Stack => " + stackOfCards);
        System.out.println();

        // Get the item at the top of the stack without removing it
        cardAtTop = stackOfCards.peek();
        System.out.println("Stack.peek() => " + cardAtTop);
        System.out.println("Current Stack => " + stackOfCards);
    }
}


Output:
Stack => [Jack, Queen, King, Ace]
Stack.pop() => Ace
Current Stack => [Jack, Queen, King]
Stack.peek() => King
Current Stack => [Jack, Queen, King]

Now let us take another example and check if the stack is empty, find the size of the stack, and search for an element in the stack.


import java.util.Stack;

public class StackSizeSearchExample {
    public static void main(String[] args) {
        Stack<String> stackOfCards = new Stack<>();
        stackOfCards.push("Jack");
        stackOfCards.push("Queen");
        stackOfCards.push("King");
        stackOfCards.push("Ace");
        System.out.println("Stack : " + stackOfCards);
        // Check if the Stack is empty
        System.out.println("Is Stack empty? : " + stackOfCards.isEmpty());
        // Find the size of Stack
        System.out.println("Size of Stack : " + stackOfCards.size());
        // Search for an element
        // The search() method returns the 1-based position of the element from the top of the stack
        // It returns -1 if the element was not found in the stack
        int position = stackOfCards.search("Queen");
        if(position != -1) {
            System.out.println("Found the element \"Queen\" at position : " + position);
        } else {
            System.out.println("Element not found");
        }

    }
}

Output:


Stack : [Jack, Queen, King, Ace]
Is Stack empty? : false
Size of Stack : 4
Found the element "Queen" at position : 3

Implementing Stacks

Now there are two ways to implement a stack:

  • Using array
  • Using Linked List

Implementing Stack using Arrays:

Example:


public class StackCustom {
	int size;
	int arr[];
	int top;

	StackCustom(int size) {
		this.size = size;
		this.arr = new int[size];
		this.top = -1;
		}
	 
	public void push(int pushedElement) {
		if (!isFull()) {
			top++;
			arr[top] = pushedElement;
			System.out.println("Pushed element:" + pushedElement);
		} else {
			System.out.println("Stack is full !");
		}
	}
	 
	public int pop() {
		if (!isEmpty()) {
			int returnedTop = top;
			top--;
			System.out.println("Popped element :" + arr[returnedTop]);
			return arr[returnedTop];
	 
		} else {
			System.out.println("Stack is empty !");
			return -1;
		}
	}
	 
	public int peek() {
		return arr[top];
	}
	 
	public boolean isEmpty() {
		return (top == -1);
	}
	 
	public boolean isFull() {
		return (size - 1 == top);
	}
	 
	public static void main(String[] args) {
		StackCustom StackCustom = new StackCustom(10);
		StackCustom.pop();
		System.out.println("=================");
		StackCustom.push(10);
		StackCustom.push(30);
		StackCustom.push(50);
		StackCustom.push(40);
		System.out.println("=================");
		StackCustom.pop();
		StackCustom.pop();
		StackCustom.pop();
		System.out.println("=================");
	}
}


Stack is empty !
=================
Pushed element:10
Pushed element:30
Pushed element:50
Pushed element:40
=================
Popped element :40
Popped element :50
Popped element :30

Implementing Stack Using Linked List:

The linked list implementation of stack is dynamic. It can grow and shrink according to the needs at runtime. But, this implementation requires extra memory due to involvement of pointers.


public class LinkedListStack {
	private Node head; // the first node
	// nest class to define linkedlist node
	private class Node {
		int value;
		Node next;
	}
 
	public LinkedListStack() {
		head = null;
	}
 
	// Remove value from the beginning of the list for demonstrating behaviour of stack
	public int pop() throws LinkedListEmptyException {
		if (head == null) {
			throw new LinkedListEmptyException();
		}
		int value = head.value;
		head = head.next;
		return value;
	} 
	// Add value to the beginning of the list for demonstrating behaviour of stack
	public void push(int value) {
		Node oldHead = head;
		head = new Node();
		head.value = value;
		head.next = oldHead;
	}
 
	public static void main(String args[]) 
	{
		LinkedListStack lls=new LinkedListStack();
		lls.push(20);
		lls.push(50);
		lls.push(80);
		lls.push(40);
		lls.push(60);
		lls.push(75);
		System.out.println("Element removed from LinkedList: "+lls.pop());
		System.out.println("Element removed from LinkedList: "+lls.pop());
		lls.push(10);
		System.out.println("Element removed from LinkedList: "+lls.pop());
		printList(lls.head);
	}
	public static void printList(Node head) {
		Node temp = head;
		while (temp != null) {
			System.out.format("%d ", temp.value);
			temp = temp.next;
		}
		System.out.println();
	}
}
 
/**
 * 
 * Exception to indicate that LinkedList is empty.
 */
 
class LinkedListEmptyException extends RuntimeException {
	private static final long serialVersionUID = 1L;
 
	public LinkedListEmptyException() {
		super();
	}
 
	public LinkedListEmptyException(String message) {
		super(message);
	}
}

Output:


Element removed from LinkedList: 75
Element removed from LinkedList: 60
Element removed from LinkedList: 10
40 80 50 20

Converting to Stack:

Converting Array to Stack:


import java.util.Stack;

public class ArrayToStackExample {
    public static void main(String a[]){
        Integer[] intArr = { 1,2,3,4};
        Stack<Integer> stack = new Stack<>();
        for(Integer i : intArr){
            stack.push(i);
        }
        System.out.println("Non-Empty stack : "  + stack);
    }
}



//*****
Output:
Non-Empty stack : [1, 2, 3, 4]

Converting Linked List To Stack:


import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class ListToStackExample {
    public static void main(String a[]){
        Stack<Integer> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        System.out.println("Non-Empty stack addAll Operation : "  + stack.addAll(list));
        System.out.println("Non-Empty stack : "  + stack);
    }
}

/****
Output:
Non-Empty stack addAll Operation : true
Non-Empty stack : [1, 2, 3]

About Author

Myself KarthiQ, I am the author of this blog, I know ways to write a good article but some how I donot have the skills to make it to reach people, would you like help me to reach more people By sharing this Article in the social media.

Share this Article Facebook
Comment / Suggestion Section
Point our Mistakes and Post Your Suggestions

Recent Addition

new tutorial Selenium Online Training : Our next online training course for Selenium with Java starts from 17th December 2018.

You can attend first 3 classes for free, the total course fee is INR 10,000

The course time would be 8.00 PM(IST) for the first three classes

If you are interested to learn, then you can join the course by sending email to chercher.tech@gmail.com

or Register below


 
Join My Facebook Group
Join Group