Skip to content

ArrayStack looks bogus #97

@Ducasse

Description

@Ducasse

I started the book and the first datastructure feels strange and it gave a strange view on the rest of the book.
See
https://github.com/Ducasse/Containers-XP/blob/master/Containers-XP/CTArrayStack.class.st

and copied here.

Started to implement ArrayStack from this book https://opendatastructures.org/
But the first datastructure feels strange and it gave a strange view on the rest of the book.
The book defines the state of ArrayStack as an array and a number representing the number of elements.

T[] a;
int n; 
int size() {
   return n; }

For example add is defined as follows:

void add(int i, T x) {
   if (n + 1 > a.length) resize();
   for (int j = n; j > i; j--)
     a[j] = a[j-1];
   a[i] = x;
   n++;
}

Set is defined as follows:

 T set(int i, T x) {
   T y = a[i];
   a[i] = x;
   return y;
}

To me these definition are bogus.
Indeed

  • first set does not update the number of elements, so using set break the invariant that n is the number of elements stored.
  • second set should not return the previous value because it propagates null value
  • third why set and get are needed (I renamed them as at: at:put:) but they are not needed in a Stack API.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions