Stack

Stack is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack and the only element that can be removed is the element that is at the top of the stack, just like a pile of objects.

A stack, under the hood, is an ordered list in which insertion and deletion are done only at the top. The last element inserted is the first one to be deleted. Hence, it is called the Last in First out (LIFO) or First in Last out (FILO) list.

A pile of plates in a cafeteria is a good example of a stack. The plates are added to the stack as they are cleaned and they are placed on the top. When a plate, is required it is taken from the top of the stack. The first plate placed on the stack is the last one to be used.

Special names are given to the two changes that can be made to a stack. When an element is inserted in a stack, the concept is called push, and when an element is removed from the stack, the concept is called pop. Trying to pop out an empty stack is called underflow and trying to push an element in a full stack is called overflow.

There are some basic operations that allow us to perform different actions on a stack.

  • Push: Add an element to the top of a stack
  • Pop: Remove an element from the top of a stack
  • IsEmpty: Check if the stack is empty
  • Peek: Get the value of the top element without removing it

Basic features of Stack

  1. Stack is an ordered list of similar data type.
  2. Stack is a LIFO(Last in First out) structure or we can say FILO(First in Last out).
  3. push() function is used to insert new elements into the Stack and pop() function is used to remove an element from the stack. Both insertion and removal are allowed at only one end of Stack called Top.
  4. Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.

Applications of Stack

  1. Expression Evaluation. Stack is used to evaluate prefix, postfix and infix expressions.
  2. Expression Conversion. An expression can be represented in prefix, postfix or infix notation. Stack can be used to convert one form of expression to another.
  3. Syntax Parsing. Many compilers use a stack for parsing the syntax of expressions, program blocks etc. before translating into low level code.As many of the Programming Languages are context-free languages. So, Stack is also heavily used for Syntax Parsing by most of the Compilers.
  4. Backtracking. Suppose we are finding a path for solving maze problem. We choose a path and after following it we realize that it is wrong. Now we need to go back to the beginning of the path to start with new path. This can be done with the help of stack.Backtracking is a recursive algorithm which is used for solving the optimization problem.So, In order to find the optimized solution of a problem with Backtracking, we have to find each and every possible solution of the problem, doesn’t matter if it is correct or not.In Backtracking, while finding the every possible solution of a problem, we store the solution of a previously calculated problem in Stack and use that solution to solve the upcoming problems.
  5. Parenthesis Checking. Stack is used to check the proper opening and closing of parenthesis.In Programming, we make use of different type of parenthesis, like – (, ), {, }, which are used for opening and closing a block of code.So, these parenthesis get stored in Stack and control the flow of our program.
  6. Function call. Stack is used to keep information about the active functions or subroutines.In Programming, whenever you make a call from one function to the another function. The address of the calling function gets stored in the Stack.So, when the called function gets terminated. The program control move back to the calling function with the help of the address which was stored in the Stack.So, Stack plays the main role when it comes to Calling a Function from other Function.

  7. String reversal. Stack is used to reverse a string. We push the characters of string one by one into stack and then pop character from stack.String Reversal is another amazing Application of Stack. Here, one by one each character of the Stack get inserted into the Stack.So, the first character of the Stack is on the bottom of the Stack and the last character of the String is on the Top of the Stack.After performing the pop operation in Stack, we get the String in Reverse order.
  8. Memory management. Memory Management is the important function of the Operating System. Stack also plays the main role when it comes to Memory Management.
@Data
@NoArgsConstructor
public class MyStack<E> {

    private LinkedList<E> list = new LinkedList<>();

    public E push(E item) {
        list.addFirst(item);
        return item;
    }

    public E pop() {
        if (list.size() <= 0) {
            throw new EmptyStackException();
        }
        return list.remove();
    }

    public int getSize() {
        return list.size();
    }

    public E peek() {
        if (list.size() <= 0) {
            throw new EmptyStackException();
        }
        return list.getFirst();
    }

    public void print() {

        int size = getSize();
        int count = 1;
        
        if (count >= size) {
            return;
        }

        E item = list.getFirst();

        while (item != null) {

            System.out.println(item.toString());

            if (count >= size) {
                break;
            }

            item = list.get(count);

            count++;
        }
    }
}

Source code on Github




Subscribe To Our Newsletter
You will receive our latest post and tutorial.
Thank you for subscribing!

required
required


Leave a Reply

Your email address will not be published.