Stack - implementation in Java

Question

I implemented a stack data structure without using any libraries or Java API code.

@SuppressWarnings("unchecked")
public class Stack<E> {
 // Properties
 private E[] data;
 private E[] buffer;
 private int bufferSize;
 
 // Constructor
 public Stack() {
 this.bufferSize = 0;
 this.buffer = (E[]) new Object[this.bufferSize];
 this.data = (E[]) new Object[this.bufferSize];
 }
 
 // Main methods
 public boolean empty() {
 return (bufferSize == 0);
 }
 
 public E peek() {
 if (bufferSize == 0)
 throw new ArrayIndexOutOfBoundsException("The stack is empty");
 
 return this.data[this.bufferSize - 1];
 }
 
 public E pop() {
 if (bufferSize == 0)
 throw new ArrayIndexOutOfBoundsException("The stack is empty");
 
 this.buffer = (E[]) new Object[this.bufferSize];
 for (int i = 0; i < this.bufferSize; i++)
 this.buffer[i] = this.data[i];
 
 this.bufferSize--;
 this.data = (E[]) new Object[this.bufferSize];
 
 for (int i = 0; i < this.bufferSize; i++)
 this.data[i] = this.buffer[i];
 
 E object = buffer[this.bufferSize];
 this.buffer = null;
 
 return object;
 }
 
 public E push(E item) {
 this.buffer = (E[]) new Object[this.bufferSize];
 for (int i = 0; i < this.bufferSize; i++)
 this.buffer[i] = this.data[i];
 
 this.bufferSize++;
 this.data = (E[]) new Object[this.bufferSize];
 for (int i = 0; i < this.bufferSize - 1; i++) {
 this.data[i] = this.buffer[i];
 }
 
 this.data[this.bufferSize - 1] = item;
 this.buffer = null;
 
 return item;
 }
 
 public int search(Object o) {
 for (int i = this.bufferSize - 1; i >= 0; i--) {
 if (this.data[i].equals(o))
 return (this.bufferSize - i);
 }
 
 return -1;
 }
 
 public int size() {
 return this.bufferSize;
 }
}

You can tell me if the code is good or if it is in need of some improvement.

• J_H: I don't see a test suite. How do you propose to convince me, or any other skeptical reviewer, that this code does what it claims it does?
• Mardson Diego: I am sorry. I tested my code on my pc, so i did not wrote a test suit. If you want, only if you want, you can build the code on your machine and test it.
• J_H: I understand that you believe the code works. I am even willing to go out on a limb and say that I believe there is a possibility that it works. But, having seen lots of code in the wild, I believe there is also a possibility that it doesn't work, for some cases. I am inviting you to convince me, to present overwhelming evidence so that not even a skeptic would have a shadow of a doubt. This is not complex code. It's not that hard to test. Show us that you have put in the effort. // This is not an unusual thing to require of code that goes through PR and is about to be merged down to main.
• U. Windl: At a first glace the code looks way too complicated, and most of all there should at least be a comment for each method specifying the semantics of it. Maybe also see academia.edu/55170476/The_Design_of_Data_Type_Specifications
• infinitezero: Am I the only one who finds it weird that a stack is implemented as an array?

Answer 1

private E[] data;
private E[] buffer;

Things start off a bit mysterious, a stack containing two arrays instead of just one. In principle that's fine I suppose but you just dropped this out of the blue with no explanation of what the arrays are for, which is not immediately clear since there is normally only one array in a stack.

 this.buffer = (E[]) new Object[this.bufferSize];
 for (int i = 0; i < this.bufferSize; i++)
 this.buffer[i] = this.data[i];
 
 this.bufferSize--;
 this.data = (E[]) new Object[this.bufferSize];
 
 for (int i = 0; i < this.bufferSize; i++)
 this.data[i] = this.buffer[i];
 
 E object = buffer[this.bufferSize];
 this.buffer = null;

So that's what the buffer is for, but this doesn't explain why it's a field. Looks like it should be a local variable.

Additionally, you don't need to create a new array to temporarily hold the data. If you're going to create a new array for data, you can use the old array to copy the elements from, into the new data. Just temporarily hold onto the old array:

E[] oldData = this.data;
this.bufferSize--;
this.data = (E[]) new Object[this.bufferSize];
// now copy from oldData to this.data

That saves a whole array and a full array-copy. There are still two arrays, but originally there were (briefly) 3: the temporary this.buffer, the old this.data, and the new Object[this.bufferSize] that is about to be assigned to this.data.

If you did allow Java APIs, you could use Arrays.copyOf to grow or shrink an array while copying the existing data.

This way of popping an element (and also the similar way of pushing an element) is fairly expensive, O(n) every time. An alternative that's generally regarded as better, is to keep track of two integers, a buffer size and a buffer capacity, so that you can keep part of the buffer as "unused" temporarily until you need it. That way, similar to an ArrayList, you can grow the stack capacity by a multiplicative factor instead of by adding 1, which means if you push n elements to the stack the amortized cost of pushing an element is O(1).

public int search(Object o) {
 for (int i = this.bufferSize - 1; i >= 0; i--) {
 if (this.data[i].equals(o))
 return (this.bufferSize - i);
 }
 
 return -1;
}

It is not clear to me why this.bufferSize - i is returned when a match is found. It's not the index of the element, it's also not the "index, but from the top of the stack" of the element (top of the stack would have an index of zero, but this expression would return 1). I don't really see the point of returning any sort of index since this stack is not indexable anyway, makes more sense to have a boolean contains(Object o).

• Mardson Diego: Thank you for the review. I'll write a better version of the code.

Answer 2

Methods

Idiomatic methods of the Stack data structure include trio performing operations with the last element push, pop and peek, and methods for checking the stack size, which are usually size and isEmpty.

Method search returning an int is completely alien to stack. This data structure has no notion of indices. The fact you're using an array under the hood is an implementation detail and should not be exposed to the outside world.

If java.util.Stack was your source of inspiration as @mdfst13 suggested in their comment, then you need to know that it is not the best example of the stack implementation. This class is a legacy collection, a hastily designed mixture of stack and list, which is discouraged to be used by the documentation. It's still there only for backward compatibility reasons. The class was criticized since the very early days of its existence (for instance, by Joshua Bloch, the author of Collection API), and method search was one of the moot points. This method introduces indexing, which is not characteristic of LIFO data structures, furthermore, this indexing is 1-based which is confusing and inconsistent with indexOf inherited from Vector (extending Vector is a bizarre decision to begin with).

Method push is traditionally void. If the implementation is resizable and there are no conditions under which a new element might be rejected (which seems to be the case), there's no point in returning anything.

Method name empty() - might serve as a name for some sort of factory method which produces an empty container of data.

Name isEmpty() - suggests that it returns a boolean value, indicating whether a container of data is empty or not.

More descriptive exception

When the stack is empty, a more intuitive exception to be thrown on invocation of pop or peek would be NoSuchElementException, not ArrayIndexOutOfBoundsException.

As I mentioned earlier, the fact that this stack backed by an array (hm, by two arrays) is an implementation detail, for instance, a stack can be implemented as a linked list as well.

Two arrays

This idea of using two arrays is puzzling.

Basically you promoted an intermediate local variable to an instance field, which doesn't give benefits, only makes the code more convoluted.

Performance

Time complexity operations in this implementation:

• peek - O(1)
• push - O(n)
• pop - O(n)

All three methods usually perform in O(1). Decision to resize the storage on every push and pop is costly.

If your goal was to design a space-efficient stack, then you should consider making use of a Singly-linked list data structure for that purpose. This way you can achieve constant time complexity for push, pop and peek, and the number of nodes would exactly the same as the number of elements.

If you want to utilize an array as a data store, then to improve performance, it needs to be expended to accommodate much more than only one new element and reused later. It gives amortized O(1) time complexity. A common approach is to increase capacity by 50% when there's no space for a new element (some implementations grow faster, for instance java.util.ArrayDeque initially increases capacity by 100%).

Also note, that operations removing elements usually don't trigger resizing of the internal storage (for example, take a look at classes from the Java Collection API). Because it might cause collection to constantly alternate between growing and shrinking, which would result in a poor performance.

Use System.arraycopy and Arrays.copyOf

Use static method Arrays.copyOf() to create a copy of an existing array, and System.arraycopy() to copy elements between two arrays.

These methods are implemented natively and would perform way better than a plain for-loop (until it gets optimized by the JIT-compiler), and also Arrays.copyOf() is more convenient and concise.

Conclusion

I would advise starting fresh by first implementing a clean and simple fixed size stack and then added logic for expanding the internal storage.

And I highly recommend having unit test, that would allow changing the implementation without warring that you broke something.

• mdfst13: Note that search returning an int comes from the Java definition of a Stack.

Answer 3

There's two good reviews already, I'm trying not to repeat them.

Edit: As mdfst13 noted, you seem to be replicating the java.util.Stack class without subclassing Vector. This is probably not a very good starting point as Stack is an outdated legacy class. Vector-based data structures haven't been recommended since 1998 when Java 1.2 and the List interface was released. Vector suffers from all the drawbacks of a synchronized data structure while providing very little of the benefits. A contemporary stack implementation should be based on the java.util.Deque interface.

// Properties

Comments like this are 100% useless. You spent valuable time writing them but they offer no additional information to the reader. You should write JavaDoc-formatted comments that explain why each property exists. Knowing what needs to be documented and what doesn't (and in what detail) is one of the hardest part of programming as it requires the skill of looking at the code through everyone else's point of view.

private E[] data;
private E[] buffer;

Data and buffer are extremely generic terms and they are usually really bad variable names. This is such a common anti-pattern that I would say as a rule of thumb, whenever you feel like using "data" as a name, it means that you haven't spent enough time thinking about a proper name and should stop to think. For example, OpenJDK uses elementData for the same purpose. Names should describe purpose. The code would have been much easier to understand if buffer suggested in it's name that it was a "temporary copy". That "temporary" word might have also pointed you to thinking whether it needed to be a class member at all instead of being a local variable in a method (because class members in general shouldn't contain temporary data).

public boolean empty() {

The de-facto naming convention in Java is to use "is" prefix for methods that return boolean value. If you used isEmpty the code would be consistent with the standard Java libraries and learning how to use your class would be easier for other people.

public int search(Object o) {

"Search" is again a fairly generic term and does not describe the method accurately. A search method usually implies that there are different ways to search (like pattern matching etc). The Collection interface defines a contains(Object) method to check if the collection contains the value using object equality.

Returning an integer relies on "magic numbers" which should be documented. If you returned a boolean it would be immediately clear that "true means the value exists". If you really wanted to expose the index of the element inside the hidden implementation, there is an indexOf method in the standard libraries, but for a stack, knowing the index of an element is somewhat meaningless.

throw new ArrayIndexOutOfBoundsException("The stack is empty");

Java standard library provides an EmptyStackException, which would be better suited than AIOOBE. AIOOBE implies that there was an array backing the stack, which, if taken into production, would restrict changing the internal implementation later. And, as those both are RuntimeExceptions, they should always be documented with JavaDoc @throws annotation.

• mdfst13: Note that the names search (and the result) and empty come from the Java definition of a Stack.
• TorbenPutkonen: @mdfst13 Good point, I will edit my answer.

Answer 4

You have 39 occurrences of this. in your code. I've heard it said that Java is verbose, but you're taking verbosity to a whole new level! I would delete every one of those this. qualifiers; they are just noise.

If you intention is to draw the reader to the fact that you're accessing a member of the object, you've failed to do this in several places. For instance you don't use this.bufferSize here:

 public boolean empty() {
 return (bufferSize == 0);
 }

So now a reader may have to do a double take to determine why this one was special. Or here:

 public E peek() {
 if (bufferSize == 0)
 throw new ArrayIndexOutOfBoundsException("The stack is empty");
 
 return this.data[this.bufferSize - 1];
 }

you are using both bufferSize and this.bufferSize. The reader's immediate implication is that these are somehow different; one might be an argument or a local variable where as the other is a member of the object. Of course, these two functions are small enough for the reader to see this isn't the case. The pop() function is somewhat larger, and also has both bufferSize and this.bufferSize usages.

Don't use this. unless it is actually necessary.

• psaxton: And then don't make using this. necessary.