Stack
package com.thealgorithms.datastructures.stacks;
/**
* A generic interface for Stack data structures.
*
* @param <T> the type of elements in this stack
*/
public interface Stack<T> {
/**
* Adds an element to the top of the stack.
*
* @param value The element to add.
*/
void push(T value);
/**
* Removes the element at the top of this stack and returns it.
*
* @return The element popped from the stack.
* @throws IllegalStateException if the stack is empty.
*/
T pop();
/**
* Returns the element at the top of this stack without removing it.
*
* @return The element at the top of this stack.
* @throws IllegalStateException if the stack is empty.
*/
T peek();
/**
* Tests if this stack is empty.
*
* @return {@code true} if this stack is empty; {@code false} otherwise.
*/
boolean isEmpty();
/**
* Returns the size of this stack.
*
* @return The number of elements in this stack.
*/
int size();
/**
* Removes all elements from this stack.
*/
void makeEmpty();
}
About this Algorithm
A stack is a basic linear data structure that follows an order in which objects are accessed. The order is called LIFO(Last In First Out)or FILO(First in Last Out). A perfect example of stacks would be plates in a canteen, a pile of books, or a box of Pringles,etc. Stacks are used to implement parsers and evaluation expressions and backtracking algorithms. basic operations are pushing an element into the stack and popping the element out of the stack. We can make use of linked lists or arrays of lists. The stack contains only one pointer "top pointer" which points to the topmost elements of the stack. Insertion and deletion only occurs at one end of the stack.
Standard Stack Operations
- push(): inserts the element at the top of the stack.
- pop(): When we delete the element at the top of the stack
- isEmpty(): It determines whether the stack is empty.
- isFull(): determines whether the stack is full or not
- peek(): Gets the value of the top element without removing it
Working with Stacks
A pointer called TOP is used to keep track of the top element in the stack. When initializing the stack, we set its value to -1 so that we can check if the stack is empty by comparing TOP == -1. On pushing an element, we increase the value of TOP and place the new element in the position pointed to by TOP. On popping an element, we return the element pointed to by TOP and reduce its value. Before pushing, we check if the stack is already full before popping, we check if the stack is already empty.
