Stack

A stack is a linear dynamic data structure that follows the Last-In/First-Out (LIFO) principle. In stack, the addition of a new element and deletion of an element occurs at the same end which implies that the element which is added last in the stack will be the first to be removed from the stack.  

Java Stack Class

java.util.Stack package provides a stack class that models and implements stack data structure.

The java.util.Stack class has several methods which are listed below: 

• boolean empty() - Returns true if the stack is empty, else returns false. 

• E peek() - Returns the top element of the stack (the last item of the stack). 

• E pop() - Deletes the top element of the stack. 

• E push (E element) - Adds a new element at the top of the stack. 

• int search(Object obj) - Returns the 1-based position where an object is on the stack. 

Methods inherited from java.util.Vector

• boolean add(E element) - Adds a new element at the top of the stack. 

• void add(int index, E element) - Inserts the specified element at the specified position in the stack. 

• boolean addAll(Collection<? extends E> c) - Appends all elements of the specified collection at the top of the stack. 

• boolean addAll(int index, Collection<? extends E> c) - Inserts all elements of the specified collection at the specified position in the stack. 

• void addElement (E element) - Adds a new element at the top of the stack. 

• int capacity() - Returns the current capacity of the stack. 

• void clear() - Clears all elements of the stack. 

• E elementAt(int index) - Returns element at the specified index in the stack. 

• E firstElement() - Returns the first element (bottom element) of the stack. 

• E get(int index) - Returns the element at the specified index of the stack. 

• int indexOf(Object o) - Returns the index of the first occurrence of the specified element in the stack, or -1 if the element is not present in the stack. 

• int indexOf(Object o, int index) - Returns the index of the first occurrence of the specified element in the stack, searching forward from the specified index, or -1 if the element is not present in the stack. 

• boolean isEmpty() - Returns true if the stack is empty, else returns false. 

• E lastElement() - Returns the last element (top element) of the stack. 

• int lastIndexOf(Object o) - Returns the index of the last occurrence of the specified element in the stack, or -1 if the element is not present in the stack. 

• int lastIndexOf(Object o, int index) - Returns the index of the last occurrence of the specified element in the stack, searching backward from the specified index, or -1 if the element is not present in the stack. 

• E set(int index, E element) - Replaces the element at the specified index in the stack with the specified element. 

• void setElementAt(E obj, int index) - Sets the component at the specified index of the stack to be the specified object.

• void setSize(int newSize) - Sets the size of the stack. 

• int size() - Returns the number of elements in the stack .

Applications of Stack

• To reverse a word. Push a given word to stack letter by letter and then pop letters from the stack.

Example: 

Input: reverse 

Output:  esrever

• An "undo" mechanism in text editors; this operation is accomplished by keeping all text changes in a stack. Undo/Redo stacks in Excel or Word.

• Language processing: space for parameters and local variables is created internally using a stack. The compiler's syntax check for matching braces is implemented by using stack.

• Wearing/Removing Bangles.

• Converting an Infix to Postfix

Example:

Infix: A+B 

Postfix: AB+ 

• Scheduling Algorithms

Stack Class in Java

Java Collection Framework provides a class named “Stack”. This Stack class extends the Vector class and implements the functionality of the Stack data structure. 

The Stack class is a part of java.util package. To include Stack class in the program, we can use the import statement as follows.

import java.util.*;

or

import java.util.Stack;

Create A Stack

Once we import the Stack class, we can create a Stack object as shown below:

Stack mystack = new Stack();

We can also create a generic type of Stack class object as follows:

Stack<data_type> myStack = new Stack<data_type>;

Here data_type can be any valid data type in Java.

For example, we can create the following Stack class objects.

Stack<Integer> stack_obj = new Stack<>();

or;

Stack<String> str_stack = new Stack<>();

The Stack class provides methods to add, remove, and search data in the Stack. It also provides a method to check if the stack is empty. 

Push Operation

The push operation is used to push or add elements into the stack. Once we create a stack instance, we can use the push operation to add the elements of the stack object type to the stack.

Example:

Stack<Integer> myStack = new Stack<>();

myStack.push(10);

myStack.push(15);

myStack.push(20);

Pop Operation

We can remove the element from the stack using the “pop” operation. The element pointed by the Top at present is popped off the stack.

Example:

Stack<Integer> intStack = new Stack<>();

intStack.push(100);

intStack.push(200);

int val = intStack.pop();

Peek Operation

The peek operation returns the Top of the stack without removing the element.  

isEmpty Operation

The isEmpty () operation of the Stack class checks if the stack object is empty. It returns true if the Stack has no elements in it else returns false.

Search Operation

We can search for an element on the stack using the search () operation. The search () operation returns the index of the element being searched for. This index is counted from the top of the stack.

Example:

Stack<Integer> intStack = new Stack<> ();

intStack.push (100);

intStack.push (200);

int index = inStack.search(100); //index will have the value 2.

Stack Size

The size of the Stack object is given by the java.util.Stack.size () method. It returns the total number of elements in the stack.

Print / Iterate Stack Elements

We can declare an iterator for the Stack and then traverse through the entire Stack using this iterator. This way we can visit and print each stack element one by one.

Example:

import java.util.*;

public class StackCoffee {

public static void main(String[] args) {

//declare and initialize a stack object

Stack<String> stack = new Stack<String>();

stack.push("Cappuccino");

stack.push("Latte");

stack.push("Americano");

// Displaying the Stack

System.out.println("Stack elements:" + stack);

// Displaying the last element

System.out.println("The last element is: " + stack.lastElement());

}

}

The output will be:

Stack elements:[Cappuccino, Latte, Americano]

The last element is: Americano

Example:

Let's push 20, 13, 89, 90, 11, 45, 18, respectively into the stack.

Let's remove (pop) 18, 45, 11, and 90 from the stack. 

import java.util.Stack;

public class StackNum {

public static void main(String[] args) {

//declare and initialize a stack object

Stack<Integer> stack = new Stack<Integer>();

stack.push(20);

stack.push(13);

stack.push(89);

stack.push(90);

stack.push(11);

stack.push(45);

stack.push(18);

// Displaying the Stack

System.out.println("Stack elements:" + stack);

// Displaying the first and last element

System.out.println("The first element is: " + stack.firstElement());

System.out.println("The last element is: " + stack.lastElement());

stack.pop(); // pop 18

stack.pop(); // pop 45

stack.pop(); // pop 11

stack.pop(); // pop 90

System.out.println("After pop: ");

// Displaying the first and last element

System.out.println("The first element is: " + stack.firstElement());

System.out.println("The last element is: " + stack.lastElement());

}

}

The output will be:

Stack elements:[20, 13, 89, 90, 11, 45, 18]

The first element is: 20

The last element is: 18

After pop:

The first element is: 20

The last element is: 89

Example: Reverse String

Write a Java program to reverse a string that a user inputs.  For example, if the input is:

to be or not to be that is

then, the output should be:

is that be to not or be to 

import java.util.Scanner;

import java.util.Stack;

public class StackReverse {

private static Scanner sc;

public static void main(String[] args) {

sc = new Scanner(System.in);

String str = sc.nextLine();

reverseString(str);

}

public static void reverseString (String string) {

Stack<String> stack = new Stack<String>();

Scanner input = new Scanner(string);

while (input.hasNext()) {

stack.push(input.next());

}

while (!stack.isEmpty())

System.out.print(stack.pop() + " ");

System.out.println();

}

}

Let say the input is:   to be or not to be that is

Then the output will be:

is that be to not or be to 

Example: Postfix machine (Simple Calculator)

The algorithm:

• When you see an operand, push it onto the stack.

• When you see an operator:

  • pop the last two operands off of the stack.

  • apply the operator to them.

  • push the result onto the stack.

• When you're done, the one remaining stack element is the result.

Example:   5 2 4 * + 7 -

import java.util.Scanner;

public class PostfixMachine {  

public static void main(String[] args)   {  

Scanner sc = new Scanner(System.in);

    String str = sc.nextLine();

    System.out.println(postfixEvaluate(str));

}

public static int postfixEvaluate (String expression) {

Stack<Integer> s = new Stack<Integer>();

Scanner input = new Scanner(expression);

while (input.hasNext()) {

if (input.hasNextInt()) {    // an operand (integer)

s.push(input.nextInt());

} else {                     // an operator

  String operator = input.next();

  int operand2 = s.pop();

  int operand1 = s.pop();

  if (operator.equals("+")) {

      s.push(operand1 + operand2);

  } else if (operator.equals("-")) {

      s.push(operand1 - operand2);

  } else if (operator.equals("*")) {

      s.push(operand1 * operand2);

  } else {

      s.push(operand1 / operand2);

  }

}

}

return s.pop();

}

}

If the input is 

5 2 4 * + 7 -

Then the output will be:

6