Stack Based Programs : Need to prepare before an interview

                           Stack Data Structure – Introduction and Implementation

What is Stack??

Stack is an abstract data type (ADT) and very useful in programming.
In computer science, a stack is an abstract data type that serves as a collection of elements.
Majorly all the operations are done at only one end of the stack which is top of the stack.
The order in which elements in stack are stored is with LIFO (Last-in-First-Out) manner. Means the element inserted last will be removed first.

See the diagram below for more understanding.

Operations on Stack and How to Implement:

Java already has a built-in class for Stack. Click here to read about it.

Ways to implement Stack

>  Implement stack using Array (discussed Just below)
>  Implement stack using LinkedList (discussed at last)

Operations:

Initialize a topIndex = -1;

For push() operation- increment topIndex by 1 and add element at this index in array. Time- O(1)
For pop() operation- remove element from the topIndex, decrement topIndex by. Time- O(1)
For peek() operation- return the element from the topIndex. Time- O(1)
For isEmpty() operation- check if topIndex<0 then return true else false. Time- O(1)
For getSize() operation- return the topindex+1. Time- O(1)


PROGRAM:


public class StackUsingArray {
    int size;
    int topIndex = -1;
    int [] stack;

    public StackUsingArray(int size){
        this.size = size;
        stack = new int[size];
    }
    public void push(int num){
        if(topIndex==size-1) {
            System.out.println("Stack overflow, ...cannot insert new element");
            return;
        }
        System.out.println("Inserting " + num +  " into Stack.");
        topIndex = topIndex + 1;
        stack[topIndex] = num;
    }
    public Integer pop(){
        if(topIndex<0) {
            System.out.println("Stack is empty, nothing to pop");
            return null;
        }
        System.out.println("Popping from Stack.");
        Integer x =  stack[topIndex];
        topIndex--;
        return x;
    }
    public Object peek(){
        if(topIndex<0) {
            System.out.println("Stack is empty, nothing to pop");
            return null;
        }
        System.out.println("Popping from Stack.");
        return stack[topIndex];
    }

    public boolean isEmpty(){
        return (topIndex<0);
    }
    public int getSize(){
        return topIndex+1;
    }
    public void displayStack(){
        System.out.print("Stack (top-->bottom): ");
        for (int i = topIndex; i >=0 ; i--) {
            System.out.print(stack[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int size = 4;
        StackUsingArray stack = new StackUsingArray(size);
        System.out.println("Is Stack Empty: " + stack.isEmpty());
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.displayStack();
        System.out.println("Popped Element: " + stack.pop());
        System.out.println("Popped Element: " + stack.pop());
        stack.displayStack();
        stack.push(6);
        System.out.println("Peeking Element: " + stack.peek());
        stack.displayStack();
        System.out.println("Is Stack Empty: " + stack.isEmpty());
        System.out.println("Stack Size: " + stack.getSize());
    }
}

OUTPUT:

Is Stack Empty: true
Inserting 1 into Stack.
Inserting 2 into Stack.
Inserting 3 into Stack.
Inserting 4 into Stack.
Stack overflow, ...cannot insert new element
Stack (top-->bottom): 4 3 2 1
Popping from Stack.
Popped Element: 4
Popping from Stack.
Popped Element: 3
Stack (top-->bottom): 2 1
Inserting 6 into Stack.
Popping from Stack.
Peeking Element: 6
Stack (top-->bottom): 6 2 1
Is Stack Empty: false
Stack Size: 3


                                            Implement Stack Using Linked List


Objective: Write an algorithm to implement Stack using Linked List.

If you do not know about then for starters its abstract data type in which follows the principle of LIFO (Last-In-First-Out) which means the data goes in last comes out

Approach:

Solution is quite simple, Earlier we have seen an article  “Linked List Implementation“, we need to make some changes to make it work as Stack.

Stack Operations:

Push() : Insert the element into linked list at the beginning and increase the size of the list. O(1) operation.

Pop() : Return the element first node from the linked list and move the head pointer to the second node. Decrease the size of the list. O(1) operation.

getSize(): Return the size of linked list.

displayStack(): Print the linked list.


PROGRAM:


public class StackUsingLinkedList {
    Node head= null;
    int size =0;

    public void push(int data){
        Node x = new Node(data);
        if(getSize()==0){
            head = x;
        }else{
            //add the Node at the start of a Linked List
            Node temp = head;
            x.next = temp;
            head = x;
        }
        System.out.println("Element "+ data + " is pushed into Stack");
        size++;
    }

    public int pop(){
        if(getSize()==0){
            System.out.println("Stack is Empty");
            return -1;
        }else{
            Node temp = head;
            head = head.next;
            size--;
            return temp.data;
        }

    }

    public void printStack(){
        Node curr = head;
        while(curr!=null){
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
        System.out.println();
    }
    public int getSize(){
        return size;
    }

    public static void main(String[] args) {
        StackUsingLinkedList stck = new StackUsingLinkedList();
        stck.push(1);
        stck.push(2);
        stck.push(4);
        stck.printStack();
        System.out.println("Pop out element " + stck.pop());
        stck.printStack();
    }
}
class Node{
    int data;
    Node next;
    public Node(int data){
        this.data = data;
    }
}


Output:

Element 1 is pushed into Stack
Element 2 is pushed into Stack
Element 4 is pushed into Stack
4 2 1
Pop out element 4
2 1