Different Types Of Stack Implementation | Array | LinkedList | Queue

We are going to discuss the different types of Stack Implementation. Stack can be implemented using array, LinkedList and Queue.

Contents Of The Article

• Stack Implementation Using Array
• Stack Implementation Using LinkedList
• Stack Implementation Using Queue

Stack Using Array

• In this implementation, we declare an array and use that as a stack.
• Initially we declare array with size 10. When array is full, we increase the size of the array.
• We increment top pointer for each push and decrement top pointer for each pop operation.
• We use Arrays.copyOf() method to dynamically increase or decrease size of array.

  class MyStack
{
    int arr[];
    int size = 10;
    int top = -1;
    MyStack()
    {
        arr = new int[10];
    }
    public void push(int data)
    {
        if(top == size-1)
        {
            // Array is full, so doubling the array size and copying the array elements 
            arr = Arrays.copyOf(arr,size*2);
            size = size*2;
        }

        arr[++top] = data;
    }
    public int pop() throws Exception
    {
        if(isEmpty())
        {
            throw new Exception("Stack is empty");
        }
        if(top<size/2)
        {
           /* No. of elements is lesser than size/2, we won't need bigger array
            Hence we are reducing the array size by 2 and copying the array elements to new array
            */
            arr = Arrays.copyOf(arr,size/2);
            size = size/2;
        }

        int data = arr[top--];
        return data;
    }

     /* Find top element in stack*/
    public int peek() throws Exception
    {
        if(isEmpty())
        {
            throw new Exception("Stack is empty");
        }
        return arr[top];
    }

     /*Check if stack is empty*/
    public boolean isEmpty()
    {
        return top == -1;
    }

}

Stack Using LinkedList

• Each Push adds element at the front/head of the list
• Each Pop removes element from the front of the list.

Advantages

1. No Need to resize the array and copy the elements to new array.
2. Since the memory is dynamically allocated there is no wastage of memory.

Disadvantage

1. We need a extra memory in each node to store the link to the next node.

class Node
{
    int data;
    Node next;
    Node(int data)
    {
        this.data = data;
        next = null;
    }
}

class StackWithLinkedList
{
    Node head = null;

    public void push(int data)
    {
        /* addFront of Single LinkedList*/
        if(isEmpty())
        {
            head = new Node(data);
        }
        else
        {
            Node node = new Node(data);
            node.next = head;
            head = node;
        }   
    }
    public int pop () throws Exception
    {
        /* removeFront of Single LinkedList*/
        if(isEmpty())
        {
            throw new Exception("Stack is empty");
        }
        Node top = head;
        head = head.next;
        return top.data;
    }
    int peek() throws Exception
    {
        if(isEmpty())
        {
            throw new Exception("Stack is empty");
        }
        return head.data;
    }
    boolean isEmpty()
    {
        return head == null;
    }
}

 Stack using Queue

This is one of the different types of Stack implementation. Stack can be implemented using queue in two different ways. Either we can make push costly or pop costly.  We use two Queues. One is main queue and another temporary queue.  In both methods we use two queue. What is push costly?

In push costly, on each push operation we follow these steps

Step – 1 

We add the new element to the temporary queue.

Step – 2

Remove the remaining elements from main queue and add them to temporary queue

Step – 3

Change the temporary queue as main queue.

class StackUsingQueue
{
    Queue<Integer> mainQ;
    StackUsingQueue()
    {
        mainQ = new LinkedList<Integer>();
    }
    
    //Push costly Method
    void push(int data)
    {
        Queue<Integer> tempQ = new LinkedList<Integer>();

        tempQ.add(data);  //Push new element to temporary queue
        
        //Remove all the elements from main queue and add to temporary queue
        while(!mainQ.isEmpty())
            tempQ.add(q.remove());
        
        mainQ = tempQ; // Change the temporary queue as main queue
    }
    int pop() throws Exception
    {
        if(!mainQ.isEmpty())
             return mainQ.remove();
        else
            throw new Exception("Queue is empty");      
    }
}

You Might Also Like

Finding Maximum Element In Stack in Constant Time