Introduction to stack data structure

Stack is a non primitive and linear data structure. It is an abstract data type in which addition and deletion of elements are performed from one end. Each element is placed on top of the previous element. And the element on the top of the stack is known as Top of Stack (TOS). Because elements are added and deleted from top of stack, stacks are also called as Last In First Out (LIFO) data type. The base of the stack always remain fixed. When a new element is added, the top get increased and when the top most element is removed, the top decrements. Stack can be implemented using arrays and linked list.

A common real life example of a stack is stacked books. We can put book on top of the previous book. When we need to take a book from the stack, we take it one by one. Another example is a packet of biscuits or cookies. If you assume that only one side of the packet is torn, then the biscuits can be taken out one by one from that side only.

Operations on Stack data structure

There are four types of operations performed.

  • Push() – Adds element to the top
    When push operation is performed, the element is appended on to the stack and the top is incremented. The top value points to the index position of the stack.
  • Pop() – Deletes element from the top
    When pop operation is performed, the top most element is deleted and top is decremented
  • Top() – returns element on top
  • Empty() – returns True if the stack is empty

Applications of Stacks

One of the main application of stacks is in modern program compilers. When a function invocation occur, the compiler pushes the arguments, variables and return address in the stack. When function returns, the stored values are popped out of the stack.

Stacks are also used to reverse a string. All the characters in the string are pushed to a stack and then popped one by one. Thus the last character will be on top of the stack. Since stack follows LIFO, the last character is popped first.

Other applications of stack are calculating prefix and postfix expressions, balancing of symbols, graph algorithms and back tracking.

Implementing stack using arrays

To build stack using array, create an array with large size. Stacks using arrays are not dynamic. Stack has fixed size and does not decrease or increase in runtime.

/* Implementing stack using array */
class Stack {
    static final int MAX = 1000;
    int top;
    int stackArray[] = new int[MAX]; // Maximum size of Stack
    
    //Add Constructor
    public Stack()
    {
    	//Make Stack pointer to -1
        top = -1;
    }
 
    
    boolean Push(int x)
    {
    	//If stack is filled
        if (top >= (MAX - 1)) {
            System.out.println("Stack Overflow");
            return false;
        }
        //If stack is not filled, then append
        else {
            stackArray[++top] = x;
            System.out.println(x + " pushed into stack");
            return true;
        }
    }
 
    int Pop()
    {
        if (top < 0) {
            System.out.println("Stack Underflow");
            return 0;
        }
        else {
            int x = stackArray[top--];
            return x;
        }
    }
 
    boolean Empty()
    {
        return (top < 0);
    }

 
    //return element in top of stack
    int Top()
    {
        if (top < 0) {
            System.out.println("Stack Underflow");
            return 0;
        }
        else {
            int x = stackArray[top];
            return x;
        }
    }
}
 

To use the Stack data structure

public class test {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
	     Stack str = new Stack();
	     str.Push(10);
	     str.Push(20);
	     str.Push(30);
	     System.out.println(str.Pop() + " Popped from stack");
	     System.out.println(str.Pop() + " Popped from stack");
	     System.out.println("Is stack empty: : " + str.Empty() );
	     System.out.println(str.Pop() + " Popped from stack");
	     System.out.println(str.Top() + " is Top of stack");
	     System.out.println("Is stack empty: : " + str.Empty() );

	}

}

Implementing stack using linked list

Linked list is a data type in which elements are linked to one another using pointers or reference. Even though additional memory space is required to store the pointer/reference value, stacks using linked list are dynamic. They can grow and reduce during run time and no large space needs to be allocated for initializing the stack.

// Stack using Linked List Implementation
 
public class StackLL {
 
    Node root;
 
    //Create a linked list node
    static class Node {
        int data;
        Node next;
 
        Node(int data) { this.data = data; }
    }
 
    //Create a method that checks if stack is empty
    public boolean Empty()
    {
    	return (root == null) ? true : false;

    }
 
    //Method to push data to stack
    public void Push(int data)
    {
        Node newNode = new Node(data);
 
        //If stack is empty, push value to root
        if (root == null) {
            root = newNode;
        }
        
        else {
            Node temp = root;
            root = newNode;
            newNode.next = temp;
        }
        System.out.println(data + " pushed to stack");
    }
 
  //Method to pop data to stack
    public int Pop()
    {
        int popped_Value = Integer.MIN_VALUE;
        if (root == null) {
            System.out.println("Stack is Empty");
        }
        else {
            popped_Value = root.data;
            root = root.next;
        }
        return popped_Value;
    }
 
    public int Top()
    {
        if (root == null) {
            System.out.println("Stack is empty");
            return Integer.MIN_VALUE;
        }
        else {
            return root.data;
        }
    }
}

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.