Stack


Stack is an abstract data type with a bounded (predefined) capacity. It 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, the only element that can be removed is the element that was at the top of the stack, just like a pile of objects.


Basic features of Stack

Stack is an ordered list of similar data type.
Stack is a LIFO structure. (Last in First out).
push() function is used to insert new elements into the Stack and pop() is used to delete an element from the stack. Both insertion and deletion are allowed at only one end of Stack called Top.
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.


Java program to create Stack using array:

Implement stack using array. Define the size of array and declare an in pointer top
Initialize the top with -1, when you push an element increment the top with 1 so top will always point the latest inserted element.
When we pop the top element decrement the top by 1.
package com.mk.ds.stack;

public class Stack {
   
private int size;
   
private int top;
   
private int[] stackArr;

   
public Stack(int size){
       
stackArr = new int[size];
       
this.size = size;
       
top = -1;
    }

   
public void push(int value){
       
if(size == top) {
           
throw new RuntimeException("stack is full");
        }
       
stackArr[++top] = value;
    }

   
public int pop(){
       
if(top < 0) {
           
throw new RuntimeException("stack is empty");
        }
       
int topValue = stackArr[top--];
       
return topValue;
    }

   
public boolean isEmpty(){
       
if(top < 0) {
           
return true;
        }
       
return false;
    }
   
   
public int size(){
       
return size;
    }
   
   
public static void main(String[] args){
        Stack stack =
new Stack(10);
       
for(int val = 11 ; val < 21 ; val++) {
            stack.push(val);
        }
// insertion order 11 12 13 14 15 16 17 18 19 20

       
while (!stack.isEmpty()) {
            System.
out.print(stack.pop());
        }
// pop from top first
          // 20 19 18 17 16 15 14 13 12 11
   
}
}


Java program to create Stack using Linkedlist:

Implement stack using linked List, refer below code snippet-
package com.mk.ds.stack;

public class StackUsingLinkedList {
   
private Node top;

   
private static class Node {
        
int data;    // integer data
       
Node next;    // pointer to the next node
   
}

   
public StackUsingLinkedList() {
       
this.top = null;
    }

   
public void push(int x) {
        Node node =
new Node();
       
if (node == null) {
            
throw new RuntimeException("Overflow");
        }
        node.
data = x;
        node.
next = top;
       
top = node;
    }

   
public boolean isEmpty(){
       
if(top == null) {
           
return true;
        }
       
return false;
    }

   
public int pop() {
       
if (top == null) {
           
throw new RuntimeException("underflow");
        }
       
int data = top.data;
       
top = top.next;
       
return data;
    }
}

class StackImpl {
   
public static void main(String[] args) {
        StackUsingLinkedList stack =
new StackUsingLinkedList();
       
for(int val = 11 ; val < 21 ; val++) {
            stack.push(val);
        }
// insertion order 11 12 13 14 15 16 17 18 19 20

       
while (!stack.isEmpty()) {
            System.
out.print(stack.pop()+ " ");
        }
// pop from top first
        // 20 19 18 17 16 15 14 13 12 11
   
}
}


Check if an expression is a balanced expression

If current braces is ( or { or [ than push it into stack.
If current braces is closing ) or } or ] than pop from stack, if braces is not available in stack than expression in not balanced. Please refer below code snippet-
package com.mk.ds.stack;

public class StackUsingLinkedList {
   
private Node top;

   
private static class Node {
       
char data;    // integer data
       
Node next;    // pointer to the next node
   
}

   
public StackUsingLinkedList() {
       
this.top = null;
    }

   
public void push(char value) {
        Node node =
new Node();
       
if (node == null) {
           
throw new RuntimeException("Overflow");
        }
        node.
data = value;
        node.
next = top;
       
top = node;
    }

   
public boolean isEmpty(){
       
if(top == null) {
           
return true;
        }
       
return false;
    }

   
public char pop() {
       
if (top == null) {
           
throw new RuntimeException("underflow");
        }
       
char data = top.data;
       
top = top.next;
       
return data;
    }
}

class StackImpl {
   
public static void main(String[] args) {
        StackImpl stackImpl =
new StackImpl();
       
char[] balArr = {'{','[',']','}'};
       
char[] unBalArr = {'{','[','}'};
        System.
out.println("Balanced expression : "+stackImpl.checkBalanced(balArr));
        System.
out.println("Balanced expression : "+stackImpl.checkBalanced(unBalArr));
    }

   
public boolean checkBalanced(char[] array){
        StackUsingLinkedList stack =
new StackUsingLinkedList();
       
for(int count = 0; count < array.length; count++) {
           
if(array[count] == '(' || array[count] == '{' || array[count] == '[' ) {
                stack.push(array[count]);
            }
           
else if (array[count] == ')' || array[count] == '}' || array[count] == ']' ) {
               
if(stack.isEmpty())
                   
return false;

               
char top = stack.pop();
               
if(top == '(' && array[count] != ')'
                   
|| top == '{' && array[count] != '}'
                   
|| top == '[' && array[count] != ']' ) {
                   
return false;
                }
            }
        }
       
return stack.isEmpty();
    }
}
Outout-
Balanced expression : true
Balanced expression : false


Reverse a stack

To reverse a stack we can use a temporary stack and push all element into this temporary stack, now all the element into this new stack are in reversed order.

2 comments: