Stack

A stack is a very commonly used ADT. It is so named because it resembles a stack of plates used in a restaurant. In such a stack, a plate that has been washed and put last would stay on top. This would be the first plate to be picked up when a plate is needed. The plate that went in first would be at the bottom of the stack and would be picked last. So, the last plate to be placed in the stack is the first plate to get out, we can also call this last in first out (LIFO).

Similarly, a stack ADT has a protocol where the last value that is put in it must be returned on the first attempt to get a value out, and the value that went in first must come out last. The following figure will make it more clear:

The operation of putting a new value in a stack is called push, and the operation of retrieving a value from a stack is called pop. The element that was pushed last must be popped first. The operation that allows one to see what the next pop will return is called peek. The peek operation returns the top element without modifying the stack. We expect all stack implementations to have all operations implemented in the time complexity of O(1). This is also part of our stack protocol.

The stack ADT has the following operations:

• Push: This adds an element at the top of the stack
• Pop: This removes the element at the top of the stack
• Peek: This checks the next value to be popped

Since we know that ADTs are to data structures what interfaces are to classes, we will code an ADT as an interface. The following is our interface for a stack:

public interface Stack<E> {
  void push(E value);
  E pop();
  E peek();
}

Of course, we will not leave it at this. We will see how a stack can actually be implemented. To this end, we will see both a fixed-sized stack using an array to store it's data, and a growing stack using a linked list for storing data. We will start with the first.

Fixed-sized stack using an array

A fixed-sized stack uses a pre-allocated array to store values, that is when this stack has used up the entire array, it can no longer accept new values until the old ones are popped. This is not very different from an actual stack of plates, which most certainly has a maximum height that it can handle.

As always, we start with the basic structure of the class, as follows:

public class StackImplArray<E> implements Stack<E> {

We need an array to store the elements, and we need to remember where the top of the stack is in that array. The top always marks the index of the element that will be popped next. When there are no more elements to be popped, it is set to -1. Why -1? Because this is the natural choice as it does not require any special handling when the first element is inserted:

protected E[] array;
  int top=-1;

  public StackImplArray(int size){
    array = (E[])new Object[size];
  }
}

The push operation in a stack can be to simply put the value in the array right next to the current top and then set the top to the new position, as illustrated in the following code:

@Override
public void push(E value) {

We first check whether the stack is already full or the current top is equal to the maximum index possible, like this:

  if(top == array.length-1){
    throw new NoSpaceException("No more space in stack");
  }

Now, we set the top to the new position and put the value we need to store in there as follows:

  top++;
  array[top] = value;
}

The exception we used is a custom exception for this purpose. The code of the exception is simple as shown in the following code:

public class NoSpaceException extends RuntimeException{
  public NoSpaceException(String message) {
    super(message);
  }
}

The pop operation is just the opposite. We need to first take the value of the current top and then update the top to the new position, which is one less than the current position, as shown in the following code:

@Override
public E pop() {

We first check whether the stack is already empty, in which case we return a special value, null. This is shown in the following code:

  if(top==-1){
    return null;
  }

Then we update the top and return the value at the current top as follows:

  top--;
  return array[top+1];
}

The peek operation does not change the state of the stack, and hence is even simpler:

@Override
public E peek() {

Just like the pop operation, we return null if the stack is empty:

  if(top==-1){
    return null;
  }

Otherwise, we return the top element, as follows:

  return array[top];
}

It is in fact possible to have a stack without an upper limit backed up by an array. What we really need to do is that whenever we run out of space, we can resize the array. Array actually cannot be resized, so the operation would be to create a new array with a higher size (maybe twice as much as the original size), and copy all the old elements into this array. Since this involves copying all the n elements to the new array one by one, the complexity of this operation is O(n).

Variable-sized stack using a linked list

The problem with an array-based implementation is that since arrays are fixed in size, the stacks cannot grow beyond a fixed-size. To resolve this, we have to do what we did to fix the same problem for an array, that is, use a linked list instead. We start such an implementation with the following bare bone class. The linked list will store the values. Instead of assigning a new linked list to it, we do so using an overridable method getNewLinkedList(). This will be useful in the class that extends from this one:

public class StackImplLinkedList<E> implements Stack<E> {
  protected LinkedList<E> list = getNewLinkedList();

  protected LinkedList<E> getNewLinkedList(){
    return new LinkedList<>();
  }
}

To see which end of the linked list must be used as the top of the stack, we need to remember that our stack protocol expects the operations to be O(1), so we must choose an end that allows both insertion and removal in O(1) time. That end is of course the front of the list as we saw in the last chapter. This makes the following code for the push operation self-explanatory:

@Override
public void push(E value) {
  list.appendFirst(value);
}

Note that this time, we did not check whether the stack is full because this implementation of the stack is never full, it grows as it needs and the underlying linked list takes care of that.

The pop operation, however, does need to check whether the stack is empty and return null at that point. The following code for the pop operation is also quite self-explanatory:

@Override
public E pop() {
  if(list.getLength()==0){
    return null;
  }
  E value = list.getFirst();
  list.removeFirst();
  return value;
}

The peek operation is, of course, the same, except it does not remove the top element:

@Override
public E peek() {
  if(list.getLength()==0){
    return null;
  }
  return list.getFirst();
}

This concludes our linked list-based implementation of a stack. In the next section, we will check out another ADT called a queue.