Stack – Data Structure

Damith

24.3K views

GitHub

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

Introduction

Stack is a LIFO (Last in first out) data structure.

Operations

pop() – adds an element in the stack.
push() – removes an element from the stack.
peek() – get the top element without removing it.
isEmpty() – checks whether stack is empty or not.
isFull() – checks whether stack is full or not.

Implementation

There are 2 ways to implement a stack.

Array-based Stack
Linked List based Stack

Array-based Stack

class Stack {
    private int top;
    private int capacity;
    private int[] array;
    public Stack(int capacity){
        this.capacity = capacity;
        this.array = new int[capacity];
        this.top = -1;
    }
    public boolean isFull(){
        return this.top == this.capacity - 1;
    }
    public boolean isEmpty(){
        return this.top == -1;
    }
    public void push(int value){
        if (this.isFull()) {
            return;
        }
        this.array[++this.top] = value;
        System.out.println(String.format("%d pushed.", value));
    }
    public int pop(){
        if (this.isEmpty()) {
            return Integer.MIN_VALUE;
        }
        return this.array[this.top--];
    }
    public int peek(){
        if (this.isEmpty()) {
            return Integer.MIN_VALUE;
        }
        return this.array[this.top];
    }
}
public class Main {
  public static void main(String[] args) {
      //capacity
      Stack stack = new Stack(5);
      stack.push(1);
      stack.push(2);

Pros:-

Easier to use.
Less memory allocation because no need to track the next node.

Cons:-

Fixed size – can not increase or decrease the array.

Link List based Stack

class StackNode {
    int data;
    StackNode next;
}
class Stack {
    private StackNode root;
    public boolean isEmpty(){
        return this.root == null;
    }
    public void push(int data){
        StackNode stackNode = new StackNode();
        stackNode.data = data;
        stackNode.next = root;
        this.root = stackNode;
        System.out.println(String.format("%d pushed.", data));
    }
    public int pop(){
        if (isEmpty()) {
            return Integer.MIN_VALUE;
        }
        StackNode tempNode = this.root;
        this.root = tempNode.next;
        return tempNode.data;
    }
    public int peek(){
        if (isEmpty()) {
            return Integer.MIN_VALUE;
        }
        return this.root.data;
    }
}
public class Main {
  
  public static void main(String[] args) {
      Stack stack = new Stack();
      stack.push(1);
      stack.push(2);
      stack.push(3);
      System.out.println(String.format("%d popped.", stack.pop()));
      System.out.println(String.format("%d peeked.", stack.peek()));
  }

Pros:-

Easily increase or decrease the Stack size.

Cons:-

Requires extra memory to keep details about next node.

Original post : - http://mydevgeek.com/stack-data-strurcture/

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content

Open Source Your Knowledge, Become a Contributor

Introduction

Operations

Implementation

Array-based Stack

Link List based Stack

6 ways to iterate or loop a Map in Java

Linked List – Insertion at Nth position

Beginner Java Concepts

Java Behavior Driven Development