7
\$\begingroup\$

I designed a simple drop-out stack a while back. Basically, I just want to get a few opinions on whether or not this is a good implementation and whether I am understanding the concept of a drop-out stack correctly. I know there are other / better ways to implement a stack, but I'm interested specifically in doing it with an array.

Basically, my idea is to allow elements to be pushed in until limit of array is reached, then an int representing the top of the stack is reset to 0, so the bottom elements are replaced by new ones pushed in. This is as opposed to making a copy of the array in a new array...but then it wouldn't be a drop-out stack.

The pop method does something similar, only in reverse. If the marker for the top reaches 0, it is set to size of array-1 so elements can still be popped in correct order.

The output I'm getting looks fine to me. No null references or objects in the wrong place, etc. I've tested it pushing in Character and Integer objects.

package CAStack;


import java.util.Arrays;
//********************************************************************
//  CircularArrayStack.java       
//
//  Represents an array implementation of a dropout stack. The bottom of
//  the stack drops out each time a new element is pushed in, after
//  size limit is reached. 
//
//  Based on ArrayStack.java
//
//
//********************************************************************






    public class CircularArrayStack<T> implements StackADT<T>
    {
       private static final int DEFAULT_CAPACITY = 100;

       private int top;
       private int bottomElem = 0;
       private T[] stack;


       //-----------------------------------------------------------------
       //  Creates an empty stack using the default capacity.
       // 
       //-----------------------------------------------------------------

        public CircularArrayStack()
       {

          this(DEFAULT_CAPACITY);
       }

       //-----------------------------------------------------------------
       //  Creates an empty stack using the specified capacity.
       // Note top is now initialized at -1 so that when first
       // element is added an top is decremented, top will equal 0
       // corresponding to the array index of the first element.
       //
       //-----------------------------------------------------------------
       public CircularArrayStack(int initialCapacity)
       {  
          top = -1;
          stack = (T[])(new Object[initialCapacity]);
       }





       //-----------------------------------------------------------------
       //  Adds the specified element to the top of this stack, expanding
       //  the capacity of the stack array if necessary.
       // Top is now incremented BEFORE element is added, so that element
       // is still successfully added to top of array; makes sure
       // element at value of top before increment is not overwritten.
       //
       // If new element is pushed in after size = CUTOFF, bottom element
       // or lowest stack element remaining is removed.
       // 
       // Instead of expanding capacity, elements are added to bottom of 
       // stack if it becomes full.
       //-----------------------------------------------------------------
       public void push (T element)
       {

         if (top == size()-1)
             top = -1;

         top++;
         stack[top] = element;


       }

    //-----------------------------------------------------------------
       //  Removes the element at the top of this stack and returns a reference to it.
       // Top is now decremented AFTER element is popped and value is changed
       // to null, as top now represents position of element, not position
       // above element.
       //-----------------------------------------------------------------

       public T pop () throws EmptyCollectionException
       {
          if (isEmpty())
             throw new EmptyCollectionException("stack");


          T result = stack[top];
          stack[top] = null;

          if (top == 0)
            top = size();
          top--;

          return result;
       }

    //-----------------------------------------------------------------
       //  Returns a reference to the element at the top of this stack.
       // Returns element at top rather than top -1 since top now
       // corresponds to position of element.
       //-----------------------------------------------------------------

       public T peek () throws EmptyCollectionException 
       {
          if (isEmpty())
             throw new EmptyCollectionException("stack");

          return stack[top];
       }



       //-----------------------------------------------------------------
       //  Returns a string representation of this stack.
       //-----------------------------------------------------------------
       public String toString()
       {
          String result = "<top of stack>\n";


          for (int index = top; index >= 0; index--)
             result += stack[index] + "\n";

          return result + "<bottom of stack>";
       }


    //-----------------------------------------------------------------
        // Returns true if the stack is empty.
        // Changed so that method returns true if top < 0 rather 
        // than top < 1 since top < 0 now represents empty condition.
    //-----------------------------------------------------------------
        public boolean isEmpty() 
        {
            return top < 0;
        }

    //-----------------------------------------------------------------
        // Returns the number of elements on the stack.
    //-----------------------------------------------------------------
        public int size() 
        {       
            return stack.length;
        }


    }

Interface Used:

    package CAStack;
    /**
     * Defines the interface to a stack collection.
     *
     * @author Java Foundations
     * @version 4.0
     */
    public interface StackADT<T>
    {
        /**  
         * Adds the specified element to the top of this stack. 
         * @param element element to be pushed onto the stack
         */
        public void push(T element);

        /**  
         * Removes and returns the top element from this stack. 
         * @return the element removed from the stack
         */
        public T pop();

        /**  
         * Returns without removing the top element of this stack. 
         * @return the element on top of the stack
         */
        public T peek();

        /**  
         * Returns true if this stack contains no elements. 
         * @return true if the stack is empty
         */
        public boolean isEmpty();

        /** 
         * Returns the number of elements in this stack. 
         * @return the number of elements in the stack
         */
        public int size();

        /**  
         * Returns a string representation of this stack. 
         * @return a string representation of the stack
         */
        public String toString();
    }
\$\endgroup\$
3
\$\begingroup\$

Terminology

This is going to be confusing. What you call size() is conventionally called the "capacity". You got the terminology mostly right in the parameter to the constructor. There's no point in calling it initialCapacity instead of just capacity, though, since the data structure's capacity cannot be changed once it is created.

You don't offer a way for users to fetch the size (i.e. the number of pushes minus the number of pops). That's what the size() method should be for. In addition, there should be a way to find out how many elements are available to be popped (that haven't been discarded).

I don't know what you mean by bottomElem — it is never used.

Style

Your block comments would be much more valuable if you wrote them as standard JavaDoc, like in the interface file.

The DEFAULT_CAPACITY is only discoverable by reading the source code or by decompiling the bytecode. Furthermore, I don't see any obvious reason for picking 100. You should either explain what the default constructor does in JavaDoc or drop the default constructor altogether.

Omitting braces is a filthy habit. You will contribute to a future coding accident, and it will be squarely your fault.

Code should compile without warnings. You should write @SuppressWarnings("unchecked") to suppress this warning:

CircularArrayStack.java:50: warning: [unchecked] unchecked cast
          stack = (T[])(new Object[initialCapacity]);
                       ^
  required: T[]
  found:    Object[]
  where T is a type-variable:
    T extends Object declared in class CircularArrayStack
1 warning

Behaviour

This is a weird data structure. I can't imagine any practical application for it. Note the following undesirable properties:

  • Once you push() one element, you can call pop() as many times as you want, and it will never be empty.
  • If you push() more elements than the capacity, it will silently overwrite earlier entries.
  • If you push() more elements than the capacity, toString() won't show all of the stored entries.
\$\endgroup\$
  • \$\begingroup\$ Thanks for your input. This wasn't really supposed to have a practical application, only a theory I was messing around with. For your second point about the push() method overwriting earlier entries, this IS exactly what I want...so this is actually a good thing. If top is reached then older entries are overwritten. \$\endgroup\$ – Oloff Biermann Sep 2 '15 at 22:38
  • \$\begingroup\$ But I can see changing the toString a bit so all elements are shown and making sure pop() throws an exception if you try to pop element that holds null. \$\endgroup\$ – Oloff Biermann Sep 2 '15 at 22:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.