Stack

One of the most recurring basic types is the stack; a pseudolanguage specification is given below.

type: Stack
data: a sequence S of n elements
operations
isEmpty() -> result , result=true $\iff$ S=\emptyset, false otherwise
push(elem e) adds e as the last element of S
pop()-> elem , removes the last element from S and returns it
top()-> elem returns the last element of S (without removing it from S)

In Java we could render the specification as an interface

public interface Stack<E> {
    public boolean isEmpty();
    public void push(E e);
    public E pop();
    public E top();
}

The use of generics allows me not to define the interface for a specific type.

Again, we can implement this in various ways, either by using indexed or linked structures.

However, the JDK provides a very respectable implementation of both Stack and Queue, and does so with a single interface Deque<E> from which derive the concrete classes ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

Deque defines methods for making both a Stack and a Queue, I refer you to the javadoc for a more comprehensive discussion and will just list them here.

For the push(e) method we have addFirst(e).
For the pop() we have removeFirst().
For peek() or top() instead peekFirst().

Deque<E> implements the Queue<E> interface, an interface also implemented by the classes: AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue.

The easiest way is to use the old Stack class from java.util, but you won’t get much benefit from it; it is derived from the Vector class and has been available since version 1.0 of the JDK

Stack<Integer> lifo = new Stack<>();
for (int i = 1; i <= 10; i++) {
    lifo.push(i);
}
while (!lifo.isEmpty()) {
    System.out.print(lifo.pop());
    System.out.print(',');
}

The recommended class is ArrayDeque<E>; a simple use case is as follows:

Deque<Integer> stack = new ArrayDeque<Integer>();
stack.push(1);
Integer value = stack.pop();
boolean isEmpty = stack.isEmpty();
value = stack.peek();

Stack

Categories

Tags