Stack API

Let us have a look at the methods we need to provide for a stack of strings.

1. StackOfStrings() — create empty stack
2. void push(String item) — insert new string onto the stack
3. String pop() — remove and return the string most recently added
4. boolean isEmpty() — Is Stack empty?
5. int size() — number of strings in the Stack

Linked List Implementation of Stack

Each stack has a Variable of type Node here named top, which holds the refernce to the top of the stack. Stack is made up of nodes and each node has two instance variables

1. String item — it stores the content of that node.
2. Node next —it has a reference to the node just below it.

public class LinkedStackOfStrings
{
     private Node top = null;
     private int size=0;
     private class Node
     {
          String item;
          Node next;
     }
     public boolean isEmpty()
     {
          return top==null;
     }
     public void push(String item)
     {
          Node oldTop=top;
          top=new Node();
          top.item=item;
          top.next=oldTop();
          size++;
     }
     public String pop()
     {
          String item=top.item;
          top=top.next;
          return top;
          size--;
     }
}

Performance

1. Time Analysis : Every operation takes constant time in worst case.
2. Space Analysis : Stack with N Nodes uses ~40N bytes.

Array Implementation of Stack

• Uses array s[] to store n items on stack.
• push(): Add new items at s[N]
• pop(): Remove items from s[N-1]

public class FixedCapacityStackOfStrings
{
     private String []s;
     private int size=0;
     public FixedCapacityStackOfStrings(int n)
     {     
          s=new String[n];
     }
     public boolean isEmpty()
     {
          return size==0;
     }
     public void push(String item)
     {
          s[size++]=item;
     }
     public String pop()
     {
          String item=s[--size];
          s[size]=null;   // To prevent Loitering
          return item;
     }
}

Loitering : Holding a reference to an object when it is no longer needed.

Garbage collector can reclaim memory only if no outstanding reference.

Defect or Problem : Stack Overflows when size exceeds capacity. So to overcome this problem lets have a look at resizing array implementation of Stack.

Resizing Array Implementation of Stack

Here if array is full, we create a new array of twice the size and copy items in new array.

public class ResizingArrayStackOfStrings
{
     private String []s;
     private int size=0;
     public ResizingArrayStackOfStrings()
     {     
          s=new String[1];
     }
     public boolean isEmpty()
     {
          return size==0;
     }
     public void push(String item)
     {    
          if(size==s.length)
               resize(2*s.length);
          s[size++]=item;
     }
     private void resize(int capacity)
     {
          String []copy=new String[capacity];
          for(int i=0;i<size;i++)
               copy[i]=s[i];
          s=copy;
     }

     public String pop()
     {
          String item=s[--size];
          s[size]=null;   // To prevent Loitering
          if((size>0)&&(size==s.length/4))
               resize(s.length/2);
          return item;
     }
}

Analysis : LinkedList Implementation Vs ResizingArray Implementation

Worst Case in Resizing Array Implementation is worst then the Linked List but overall faster. This is beacause Linked List Implementation uses extra space and time to deal with links. Every operation takes constant time in worst case in Linked List Implementation.

To understand the resizing array analysis better check out the given link Resizing Array Analysis

Clap if you enjoyed studying Stacks. Next up Queues!

Thank you!