HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Stack using an array

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
arrayusingstack

Problem

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 implements StackADT
{
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);
}

//-------------------------------------------------

Solution

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.

Code Snippets

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

Context

StackExchange Code Review Q#102559, answer score: 3

Revisions (0)

No revisions yet.