What is a stack, and what does LIFO mean?

A stack is a linear data structure where elements are added and removed from the same end, called the top. LIFO means Last In, First Out: the element pushed most recently is the first one popped, like a stack of plates.

What are the main stack operations and their time complexity?

push(x): add x to the top, O(1). pop(): remove and return the top element, O(1). peek(): return the top element without removing it, O(1). isEmpty(): check whether the stack has no elements, O(1).

Write a stack implementation using an array in Java.

Java example: public class ArrayStack { private final int[] items; private int top = -1; public ArrayStack(int capacity) { items = new int[capacity]; } public void push(int value) { if (top == items.length - 1) { throw new IllegalStateException("Stack overflow"); } items[++top] = value; } public int pop() { if (isEmpty()) { throw new IllegalStateException("Stack underflow"); } return items[top--]; } public int peek() { if (isEmpty()) { throw new IllegalStateException("Stack is empty"); } return items[top]; } public boolean isEmpty() { return top == -1; } public static void main(String[] args)

What are stack overflow and stack underflow?

Overflow happens when you push onto a stack that is already full (in a fixed-size implementation). Underflow happens when you pop or peek from an empty stack. Both should be checked and reported, for example by throwing an exception.

Which class should you use for a stack in Java?

Use ArrayDeque through the Deque interface. The older java.util.Stack class extends Vector, whose methods are synchronized, which makes it slower, and it allows access by index, which breaks the stack idea:

Write a Java program to check whether brackets in an expression are balanced.

Java example: import java.util.ArrayDeque; import java.util.Deque; public class BalancedBrackets { static boolean isBalanced(String text) { Deque stack = new ArrayDeque<>(); for (char c : text.toCharArray()) { if (c == '(' || c == '[' || c == '{') { stack.push(c); } else if (c == ')' || c == ']' || c == '}') { if (stack.isEmpty()) { return false; } char open = stack.pop(); if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) { return false; } } } return stack.isEmpty(); } public static void main(String[] args) { System.out.println(isBalanced("{[()

How is a stack used in function calls?

The JVM keeps a call stack for each thread. When a method is called, a frame with its parameters and local variables is pushed; when it returns, the frame is popped. Very deep recursion fills this stack and causes a StackOverflowError.

Write a Java program to evaluate a postfix expression.

Java example: import java.util.ArrayDeque; import java.util.Deque; public class PostfixEvaluator { static int evaluate(String expression) { Deque stack = new ArrayDeque<>(); for (String token : expression.split(" ")) { switch (token) { case "+" -> stack.push(stack.pop() + stack.pop()); case "*" -> stack.push(stack.pop() * stack.pop()); case "-" -> { int b = stack.pop(), a = stack.pop(); stack.push(a - b); } case "/" -> { int b = stack.pop(), a = stack.pop(); stack.push(a / b); } default -> stack.push(Integer.parseInt(token)); } } return stack.pop(); } public static void main(String[]

How do you implement a stack that returns the minimum in O(1)?

Keep a second stack that stores the current minimum at each level:

What are common applications of stacks?

Undo in editors. Browser back navigation. Checking balanced brackets and parsing expressions. Depth-first search in graphs. Backtracking problems such as maze solving. The method call stack.

Stack Data Structure | JavaByTechie

A stack is a fundamental data structure in computer science used to store collection of elements that follows the Last In, First Out (LIFO) principle, meaning the last element added to the stack is the first one to be removed. Stack is commonly used in programming for tasks such as function call management, expression evaluation, and backtracking algorithms.

In this tutorial, we are going to explore about Stack data structures and their operations, implementation, uses, advantages and disadvantages etc. in details.

What is a Stack Data Structure ?

A stack is a linear (ordered) data structure used to store and manipulate a collection of data elements. Stack follows the LIFO (Last In First Out) principle, which means the last element added to the stack will be removed first from the stack.

In a stack, insertion and deletion of an element can be done from one end known as the top of the stack.

The stack data structure is commonly used in programming for tasks such as managing function calls, undo/redo functionality in applications, parsing expressions, backtracking algorithms, maintaining browser history, and many more.

Operations on Stack Data Structure

The following operations can be performed on a stack data structure:

push() - It performs an insert operation, meaning adding a new element to the top of the stack.
pop() - It performs a delete operation, meaning removing an existing element from the top of the stack.
peek() - It performs a retrieve operation, meaning it returns the element at the top of the stack.
isEmpty() - Checks if the stack is empty.
isFull() - Checks if the stack is full.

Let's understand each operation of the stack data structure in detail.

1. Push Operation in Stack

In Stack, the push operation means to add or insert a new element; if we are doing a push operation, that means we are adding a new element to the stack. Stack stores that new element at the top of the storage and increments the top index by 1.

If the stack is full, then it is said to be in an overflow condition and show the error message.

Algorithm for Push Operation:

Before inserting a new element into the stack, first we will check if the stack is full or not.
If the stack is full (top == capacity - 1), then the stack overflows, and we cannot insert the element into the stack.
else, the value of top will be increased by 1 (top = top + 1), and the new element will be inserted at the top position of the stack.
Once we reach the capacity of the stack, the elements can be inserted into the stack.

Example of push operation in Stack

Main.java

// push data on the top of the stack
public void push(int data) {
  if(!isFull()){
      // increment top by 1 and insert data
      intArray[++top] = data;
  }else{
      System.out.println("Stack is full.");
  }
}

2. Pop Operation in Stack

In Stack, the pop operation means deleting an existing element from the stack. The elements are popped (removed) in the reversed order in which they are pushed (inserted).

If the stack is empty, it is often referred to as an underflow condition.

Algorithm for Pop Operation:

Before performing the pop operation, we will check the stack is not empty.
If the stack is empty (top == -1), then the pop operation will be performed.
else, we store the element at the top; the value of top will be decreased by 1 (top = top - 1) and return the stored top element.

Example of pop operation in Stack

Main.java

// pop item from the top of the stack
public int pop() {
  // retrieve data and decrement the top by 1
  return intArray[top--];
}

3. Top or Peek Operation in Stack

The top or peek operation returns the element at the top of the stack.

Algorithm for Top or Peek Operation:

The top or peek operation cannot be performed on an empty stack, so first of all we will check the stack is not empty.
If the stack is empty (top == -1), we display the message “Stack is empty”.
Else, the element stored at index = top will be returned.

Example of peek or Top operation in Stack

Main.java

int peek() {
  if (top < 0) {
    System.out.println("Stack Underflow");
    return 0;
  } else {
    int x = array[top];
    return x;
  }
}

4. isEmpty Operation in Stack

The isEmpty operation is used to check whether the stack is empty or not and returns true if the stack is empty, else false.

Algorithm for isEmpty Operation:

Check for the value of top in the stack.
If (top == -1), that means the stack is empty, so return true.
Else, the stack is not empty, so return false.

Example of isEmpty operation in Stack

Main.java

// Checks static is empty or not
boolean isEmpty() {
  return (top < 0);
}

5. isFull Operation in Stack

The isFull operation is used to check whether the stack is full or not and, as a result, returns a boolean output; if the stack is full, then return true, else false.

Algorithm for isFull Operation:

Check for the value of top in the stack.
If (top == capacity - 1), then the stack is full, so return true.
Else, the stack is not full, so return false.

Main.java

// Checks stack is full or not
public boolean isFull() {
  return (top == size - 1);
}

Complexity Analysis of Operations on Stack

Operations	Time Complexity	Space Complexity
push()	O(1)	O(1)
pop()	O(1)	O(1)
top() or peek()	O(1)	O(1)
isEmpty()	O(1)	O(1)
isFull()	O(1)	O(1)

Stack implementation in Java

There are two ways to implement a stack data structure:

Using Array
Using Linked List

Stack implementation using an array

In an array-based stack implementation, the push operation is implemented by incrementing the index of the top element by 1 and storing the new element at that index. Whereas in the pop operation, the index of the top element will be decremented by 1 and return the value stored at that index. Read more...

Stack implementation using linked list

In a linked list-based stack implementation, the push operation is implemented by creating a new node with the new element and setting the next pointer of the current top node to the new node. The pop operation is implemented by setting the next pointer of the current top node to the next node and returning the value of the current top node. Read more...

Applications of Stack Data Structure

Function Call Management
Expression Evaluation
Backtracking Algorithms
Undo Mechanism in Editors
Page Navigation in Web Browsers
Syntax Checking in Compilers
Memory Management

Advantages of Stack Data Structure

Stacks follow the LIFO principle, ensuring that the last element added to the stack is the first one removed.
Stack implementation is simple and easy to understand.
Efficient Operations such as push, pop, and peek, typically running in O(1) time complexity.
Stacks can be used to evaluate expressions in postfix notation (Reverse Polish Notation).
Stack is used to manage browser history.
Efficient memory utilization.
Used in Compiler Design.
Enables undo/redo operations.

Diadvantages of Stack Data Structure

Limited access because elements can be accessed only from top of the stack.
Not suitable for random access operation.
Potential for Stack Overflow/Underflow.
Not suitable for such applications where accessing elements in the middle of the stack.
Recursive function calls limitations.

Help Us Improve

Stack Data Structure

What is a Stack Data Structure ?

Operations on Stack Data Structure

1. Push Operation in Stack

Example of push operation in Stack

2. Pop Operation in Stack

Example of pop operation in Stack

3. Top or Peek Operation in Stack

Example of peek or Top operation in Stack

4. isEmpty Operation in Stack

Example of isEmpty operation in Stack

5. isFull Operation in Stack

Complexity Analysis of Operations on Stack

Stack implementation in Java

Stack implementation using an array

Stack implementation using linked list

Applications of Stack Data Structure

Advantages of Stack Data Structure

Diadvantages of Stack Data Structure

Frequently Asked Questions (FAQ)