CODEWITHSUNDEEP
javaarraysalgorithmperformancedata-structures
Sengngy Kouch
Sengngy Kouch

Reputation: 115

Implement Stack Using Array in Java

I am trying to implement stack using array as its core in Java. This is just the purpose of learning and understanding how stack works.

My idea was to use Array (not ArrayList) and tried to mimic the Stack structure. This implementation will have a static size. There is a pointer that starts with -1 to indicate empty stack. The pointer will increment as we add element, and we don't have to worry about deleting the element because we will override the value once we need that space (index).

The following will be my source code and follow by some questions:

import java.util.*;

public class stackUsingArray{

   private int[] myStack;
   private int pointer;

   /**
    -Constructor
   */
   public stackUsingArray()
   {
       myStack = new int[10];
       pointer = -1;//keep track of where the top element is on the stack.
   }

   /**
    -Pop method
   */
   public int pop()
  {      
      if(pointer==-1)
      {
          //throw exception here
      }
      return myStack[pointer--];
  }

  /**
  -Push when the stack is not empty.
  */

   public void push(int num)
   {
       if(pointer== myStack.size()-1)
       {
           //throw exception here
       }
       else
       {
            myStack[++pointer] = num;//add to the stack           
        }       
   }

/**
-return the top element of the stack
*/
   public void peek()
   {
       return pointer;
   }

/**
-return false if there is not more element on the stack
*/
   public boolean isEmpty()
   {
       return (pointer == -1)? true : false;
   }

   public static void main(String [] arg)
   {
       stackUsingArray newStack = new stackUsingArray();
       newStack.push(1);
       newStack.push(2);
       newStack.push(3);

       System.out.println(newStack.pop());
   }
}

At the part where I comment as throw exception:

public int pop()
      {      
          if(pointer==-1)
          {
              //throw exception here
          }
          return myStack[pointer--];
      }

What kind of exception do you think will the most logical? Most of the time, I just printout on the screen. However, I would love to learn how to throw exception.

This part: 

 public void push(int num)
   {
       if(pointer== myStack.size()-1)
       {
           //throw exception here
       }
       else
       {
            myStack[++pointer] = num;//add to the stack           
        }       
   }

The program itself has to do the operation of myStack.size() -1 . I wonder if it is better to have a private member in the class to hold the size -1? I mean in turn of efficiency.

Also, if we were to use ArrayList to implement this Stack. Will it run more efficiently? I mean, ArrayList has a lot of overhead such as internal call of methods.

Lastly, I know my code is not great, so please give me some advice to make it better!

Upvotes: 3

Views: 5287

Answers (2)

Slavcho
Slavcho

Reputation: 373

I would throw custom StackEmptyException / StackFullException derived from RuntimeException so they are unchecked. If unchecked, your users do not have to surround every pop() within try / catch. If you throw a checked exception, they will have to either try / catch every pop, or declare their own methods as throwing the exception. See this discussion for more info: Java: checked vs unchecked exception explanation

The program itself has to do the operation of myStack.size() -1 . I wonder if it is better to have a private member in the class to hold the size -1? I mean in turn of efficiency.

It won't be noticeable at all, do not do optimizations that will only spare you a processor cycle or two, but ones that reduce algorithm complexity or the number of I/O operations.

Also, if we were to use ArrayList to implement this Stack. Will it run more efficiently? I mean, ArrayList has a lot of overhead such as internal call of methods.

It will run the same as your own implementation if you start growing the array internally.

Lastly, I know my code is not great, so please give me some advice to make it better! Thank you so much!

It is pretty good for a learning project, keep up the good work ;)

Upvotes: 1

jvalli
jvalli

Reputation: 721

The most logical exception to throw when the stack is empty is debatable, but I'd go with IllegalStateException.

throw new IllegalStateException("An empty stack cannot be popped.");

I would also use ArrayList rather than an array directly. With arrays you have to take care of index overflows yourself, whereas ArrayList handles that for you internally quite efficiently. Every time you would append something to an ArrayList and it would run out of array size it copies the data to a new array that's twice the size of the old one. This still gives you an amortised addition time of O(1), due to the relative rarity of the event.

If you do use ArrayList then you could potentially get rid of your stack counter as you could check the ArrayList's size. You might lose the benefit of not having to delete entries from popping the stack (I don't recall if ArrayList optimises that by itself).

As a code style issues, It's Java convention to use capitalised classnames so you should rename your class to conform to the convention.

Your peek method is declared as void, and should return myStack[pointer]. Also in the push method you call myStack.size() which isn't correct for arrays. Use myStack.length if you don't switch to using ArrayList.

Upvotes: 1

Related Questions