Code Pumpkin

Stack Implementation Using Array

March 31, 2017
Posted by Pumpkin
Subscribe

stack

A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. A stack is a limited access data structure – elements can be added and removed from the stack only at the top.

push operation adds an item to the top of the stack.

pop removes the item from the top.

Additionally, a peek operation may give access to the top without modifying the stack.

A helpful analogy is to think of a stack of books. you can remove only the top book, also you can add a new book on the top.

Applications

  1. The simplest application of a stack is to reverse a word. You push a given word to stack – letter by letter – and then pop letters from the stack.

  2. Another application is an "undo" mechanism in text editors; this operation is accomplished by keeping all text changes in a stack.

maze

  1. Java Virtual Machine(JVM) uses stack in method calls and recursion.

  2. compiler's syntax check for matching braces is implemented by using stack.

  3. space for parameters and local variables is created internally using a stack.

  4. space for parameters and local variables is created internally using a stack.

  5. In backtracking algorithms can be implemented using stack.


Implementation

In the standard library of classes, the data type stack is an adapter class, meaning that a stack is built on top of other data structures. The underlying structure for a stack could be an array, a vector, an ArrayList, a linked list, or any other collection. Regardless of the type of the underlying data structure, a Stack must implement the same functionality. This is achieved by providing a unique interface:


interface StackInterface<AnyType>
{
  
   public boolean isEmpty();
 
   public AnyType pop() throws StackException;
 
   public AnyType peek() throws StackException;
 
   public void push(AnyType e) throws StackException;
 
   public void clear();
}

Userdefined Stack Exception class
 


class StackException extends RuntimeException
{
   public StackException(String name)
   {
      super(name);
   }
 
   public StackException()
   {
      super();
   }
}

Array Based Implementation

array stack

In an array-based implementation we maintain the following fields:

  • an array A of a default size (>= 1),
  • the variable top that refers to the top element in the stack and
  • the capacity that refers to the array size.

The variable top changes from -1 to (capacity-1). We say that a stack is empty when top = -1, and the stack is full when top = (capacity-1).

In a fixed-size stack abstraction, the capacity stays unchanged, therefore when top reaches capacity, the stack object throws an exception.



public class ArrayStack<AnyType> implements StackInterface<AnyType>
{
   private static final int DEFAULT_CAPACITY = 15;
   private int top;       // reference to the top element
   private AnyType[] A;
 
 /**
   * Creates a Stack of the size initialCapacity
   */
   public ArrayStack(int initialCapacity)
   {
      if (initialCapacity <= 0)
         A = (AnyType[]) new Object[DEFAULT_CAPACITY];
      else
         A = (AnyType[]) new Object[initialCapacity];
 
      top = -1;   //stack is empty
   }
 
 /**
   * Creates a Stack with the default capacity
   */
   public ArrayStack()
   {
      this(DEFAULT_CAPACITY);
   }
 
 /**
   * Tests if the stack is empty.
   */
   public boolean isEmpty()
   {
      return top==-1;
   }
 
 /**
   * Returns the top item without its removal.
   */
   public AnyType peek()
   {
      if (isEmpty())  throw new StackException("Stack is empty");
      return A[top];
   }
 
 /**
   * Removes and returns the item at the top of this stack.
   */
   public AnyType pop()
   {
      AnyType x = peek();
      A[top] = null;    //make sure the object is destroyed
      top--;
      return x;
   }
 
 /**
   * Inserts an item onto the top of the stack.
   */
   public void push(AnyType e)
   {
      if (top == A.length) throw new StackException("Stack has overflowed");
        top++;
      A[top] = e;
   }
 
 /**
   * Removes all items from the Stack.
   */
   public void clear()
   {
      for(int i = 0; i <= top; i++)
         A[i] = null;
 
      top = -1;
   }
 
 /**
   * Returns a string representation of the Stack.
   */
   public String toString()
   {
      if(isEmpty()) return "[ ]";
 
      StringBuffer out = new StringBuffer("[");
      for(int i = 0; i < top; i++)
         out.append(A[i] + ", ");
 
      out.append(A[top] + "]");
      return out.toString();
   }
 
   public static void main(String[] args)
   {
      ArrayStack<Integer> s = new ArrayStack<Integer>(6);
 
      try
      {
 
         for(int i = 0; i < 6; i++) s.push(i);
 
         //s.clear();
         System.out.println(s);
 
         for(int i = 0; i < 5; i++) s.pop();
 
         System.out.println(s);
 
      }
      catch (StackException e)
      {
         System.err.println(e);
      }
   }
}

Download Complete Java Program »

Tags: , ,


Comments and Queries

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
<pre><code class="java"> 
String foo = "bar";
</code></pre>
For more information on supported HTML tags in disqus comment, click here.

Total Post : 80
Subscribe
Contribute Your Articles

Interview Experiences

Related Books

Like Us On Facebook

Alexa Page Rank