Introduction
- This series is going to be dedicated to learning and understanding data structures and algorithms in Java. All the information I am using is coming from the book,
Data Structures and Algorithms in Java by Michael T. Goodrich and Roberto Tamassia
and the California State Polytechnic University course, which is free and can be found HERE,shout out professor Tang
. Please do not buy the book it is expensive and can be found online for MUCH cheaper.
YouTube version:
- YouTube version of this code can be found HERE
GitHub code
- GitHub for the code can be found HERE
What is a abstract data type?
- Before we can talk about stacks we need to understand what an abstract data type is. Also, I should point out that a stack is considered an
Abstract Data Type
(ADT), what is an abstract data type? Good question, an abstract data type is a purely theoretical entity that we as programmers use to simplify our understanding of algorithms and data structures. AADT
allows us to understandwhat
something does without actually understandinghow
it does it. For example, when we say a stack is an ADT it lets us understand what methods it has and what principles it follows without having to go into implementation details. Later in this post we will implement an array based stack and in the next blog post we will implement a linked list based stack.
What is a Stack?
- A stack is a collection of objects that are inserted and removed according to the
last in first out
(LIFO) principle. A user may insert objects into a stack at any time, but may only access or remove the most recently inserted object. The most recently inserted object is said to be at thetop
of the stack. A common mental model to have is a stack of books, where the books can only be removed or added from the top and to get to the bottom book, one has to remove all other books. The fundamental operations that the stack is most known for arepush
andpop
. To add something to the stack wepush
it and to remove something from the stack wepop
it. Stacks are some of the simplest of all the data structures but they are among the most important, as they are used in many different applications and as a tool for many different data structures and algorithms.
Methods of the stack
- Formally a stack supports 2 update methods:
1) push(e): Adds element e to the top of the stack
2)pop(): Removes and returns the top element from the stack
- A stack also supports 3 accessor methods:
3)top(): returns the top element of the stack, without removing it
4)size(): returns the number of elements in the stack
5)isEmpty(): Returns a boolean indicating weather the stack is empty
Stack Interface
- To be able to formalize our abstraction of a stack, we define what is known as an application programming interface (API) in the form of a Java interface, which will describe the names of the methods that the ADT supports. With our interface we will also rely on Java's generics framework which will allow the elements stored on the stack to belong to any type we define. Just a quick reminder that interfaces can not be directly instantiated and that we have to implement them.
public interface Stack <E>{
int size();
boolean isEmpty();
void push(E e);
E top();
E pop();
}
- With the interface defined we can now finally create a proper implementation of a stack
Array Based Stack implementation
In this stack implementation, we store elements in an array, named
data
. We will orientate the stack so that the bottom element of the stack is always stored in celldata[0]
, and the top element of the stack in celldata[t]
. For indexing,t
will initially be equal to -1.In order to create our stack based implementation we will follow 4 steps:
1) Create the class and instance variables
2) Create the constructors
3) Implement the interface
4) Implement the methods
1) Create the class and instance variables
- The first thing we have to do is to create the class and the instance variables for the class.
public class ArrayStack<E> {
public static final int CAPACITY = 1000;
private E[] data;
private int t =-1;
}
- From the code above, first notice that we are using generics with
E
. The variabledata
is what is going to hold the actual array instance andt
is going to be used for indexing. -1 will represent an empty array. Finally we deal withCAPACITY
, which technically is not an instance variable due to thestatic
modifier. This modifier means thatCAPACITY
is a class variable and it is shared across all the instances of theArrayStack
class. Thefinal
modifier indicates that value of this field can not be changed. The size ofCAPACITY
is arbitrary and 1000 is chosen simply because the book tells me to choose it.
2) Create the constructors
public class ArrayStack<E> {
// rest of the code is above
public ArrayStack(){
this(CAPACITY);
}
public ArrayStack(int capacity){
data = (E[]) new Object[capacity];
}
}
- We create two constructors which gives the user of our ArrayStack the flexibility to determine their own capacity of the array. However, if they do not choose a size for the array, then we create the array with the default
CAPACITY
. In the default constructor there isthis(CAPACITY);
which is just a way to call a constructor from within a constructor. The other constructor that takes in a integer parameter and does something a little hacky, which is(E[]) new Object[capacity];
. First the new operator allocates an array of type object with enough memory for the specified capacity of type object (not hacky). Then casts back to an array of type E(E[])
(hacky). If you try to switch Object out withE
you will get an error that states,Type parameter 'E' cannot be instantiated directly
. Which is actually a nice error message but why does it happen? Well there are actually two versions of the answer, we can call them the simple answer and the less simple answer.
The simple answer : Simply put, one of the restrictions on Generics, which can be found HERE, is that we cannot create instances of type parameters (E is a type parameter).
The less simple answer : Generics were retrofitted into the Java language in release 5. In order to maintain backwards compatibility with existing code bases, type erasures
were created. What is type erasures
? At compile time the Java compiler applies type erasure to replace all type parameters in generic types with their bounds or Object if the type parameters are unbounded( our E is unbound). This means that the produced bytecode contains only ordinary classes, interfaces and methods. So if we were to put new E[capacity]
due to type erasure E would be replaced with Object, which would negate all of the benefits of generics and at runtime our code would be unable to tell what type we are using.
- The topic of type erasure is still not 100% clear to me, HERE, is the stack overflow question I consulted for this answer. If anyone has a better understanding of type erasures please comment down below.
3) Implement the interface
- In this step we will implement the interface that we defined earlier:
public class ArrayStack<E> implements Stack<E> {
}
- Notice that we also use Generics on the interface. Once we have implemented the interface we will be asked to implement the methods.
4) Implement the methods
- In this step we can implement the all of the methods that we have formalized through the interface:
public class ArrayStack<E> implements Stack<E> {
@Override
public int size() {
return (t+1);
}
@Override
public boolean isEmpty() {
return t==-1;
}
@Override
public void push(E e) throws IllegalStateException{
if(size() == data.length) throw new IllegalStateException("Stack is full");
data[++t] = e;
}
@Override
public E top() {
if(isEmpty()) return null;
return data[t];
}
@Override
public E pop() {
if(isEmpty()) return null;
E answer = data[t];
data[t] = null;
t--;
return answer;
}
}
- With that, we now have a full working implementation of a Array based stack implementation. You can end this tutorial now. However, if you want to read a little more about the time and space complexities scroll down to the bottom.
Full Array based implementation
public class ArrayStack<E> implements Stack<E> {
public static final int CAPACITY = 1000; //default array capacity
private E[] data; //generic array used for storage
private int t =-1; //index of the top element in the stack, -1 indicates empty
public ArrayStack(){
this(CAPACITY);
}
public ArrayStack(int capacity){
data = (E[]) new Object[capacity];
}
@Override
public int size() {
return (t+1);
}
@Override
public boolean isEmpty() {
return t==-1;
}
@Override
public void push(E e) throws IllegalStateException{
if(size() == data.length) throw new IllegalStateException("Stack is full");
data[++t] = e;
}
@Override
public E top() {
if(isEmpty()) return null;
return data[t];
}
@Override
public E pop() {
if(isEmpty()) return null;
E answer = data[t];
data[t] = null;
t--;
return answer;
}
}
Drawbacks of the Array based implementation
- Our Array implementation is simple and efficient, However, it has one major drawback. The drawback being the fixed capacity of the array. If we do not know the length of our array before hand, we could end up wasting a lot of space or get a illegal state exception when we exceed its limits. We will see in the next implementation how a linked list provides a solution to this problem.
Analyzing our implementation
Now I know we have not talked about time and space complexities or big O notation and that has been deliberate(I will make tutorials eventually). However, If you want a quick overview, checkout Professor Tang's lecture notes, HERE.
shout out Professor Tang
. Now lets get to analyzing.All the methods inside of our array implementation operate in constant time
O(1)
, because each method has a fixed number of operations. Which is good because it is a general rule of thumb that we want constant or logarithmic time for data structure operations and linear or n-log-n time for algorithms. For space complexity, our implementation isO(N)
with N being the size of the array. O(N) is also called linear.
Conclusion
- Thank you for taking the time out of your day to read this blog post of mine. If you have any questions or concerns please comment below or reach out to me on Twitter.
Top comments (0)