Different Types Of Stack Implementation | Array | LinkedList | Queue

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 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.

[code lang=”java”]
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;
}

}

[/code]

 

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.

Stack using linkedlist

[code lang=”java”]

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;
}
}

[/code]

 

 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.

Stack with Queue

[code lang=”java”]

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");
}
}

[/code]

You Might Also Like

Finding Maximum Element In Stack in Constant Time

[wpdiscuz-feedback id=”sd4yfvbeff” question=”Please leave a feedback on this” opened=”0″]Let us know your thoughts in comments[/wpdiscuz-feedback]

Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.

Leave a Reply

Your email address will not be published. Required fields are marked *