Implement Stack Using Array in Java

Question

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!

Are you aware that Java already has a Stack class ? http://www.tutorialspoint.com/java/java_stack_class.htm — SPlatten, Jul 18 '16 at 12:29
@SPlatten He is just trying to better understand how it works. — indjev99, Jul 18 '16 at 12:34
@SPlatten U should have read what I wrote first before asking. Anyway, thanks for the link. — Sengngy Kouch, Jul 18 '16 at 16:41

score 1 · Accepted Answer · edited May 23 '17 at 12:32

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

score 1 · Answer 2 · answered Jul 18 '16 at 12:39

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.

A personal preference to make the code clearer would be to give "pointer" a clearer name as to what it means. If probably call it something like nextFreeElement and initialise it to 0. — matt helliwell, Jul 18 '16 at 16:44
@jvalli +1 for the time complexity of ArrayList! +2 more for naming convention and errors!! Thank you very much for your help! — Sengngy Kouch, Jul 18 '16 at 16:56
@matthelliwell I agree with you with the naming! I will keep that in mind next time. One thing I want to point out is that because I used Array, and the index start at 0 (zero), so I can't use 0 as the starting value. — Sengngy Kouch, Jul 18 '16 at 16:58
Initialising it to 0 would work if it points to the next free slot rather than the highest used slot. Anyway, it's a minor point. — matt helliwell, Jul 18 '16 at 20:52

Implement Stack Using Array in Java

2 Answers2