Stack class in java.util a violation of Liskov substitution principle?

From the documentation of https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

public class Stack<E> extends Vector<E>

Isn't this a violation of the Liskov substitution principle? The LSP in simple terms states that objects of the same superclass should be able to be swapped with each other without breaking anything.

For example: Let us say that I have a function that takes a Vector as an input. If while calling a function I start passing it a Stack then it might break because Stack prevents random access of elements.

import java.util.*;

class Book {}

class TextBook extends Book {}

public class Sample {
    public static void process(Vector<Book> books) {
        # This should not be allowed for Stack, Stack is FILO
        System.out.println(books.get(1));
    }

    public static void main(String[] args) {
        Vector<Book> books = new Vector<>();
        books.add(new Book());
        books.add(new Book());
        books.add(new Book());
        process(books);
        System.out.println("ok");

        Stack<Book> bookz = new Stack();
        bookz.add(new Book());
        bookz.add(new Book());
        bookz.add(new Book());
        process(bookz);
        System.out.println("ok");
    }
}

3 answers

  • answered 2020-02-16 15:22 John Kugelman

    Yes, it is.

    A stack should only allow for pushing and popping, but because Stack extends Vector it's possible to call the full set of Vector methods. Items can be inserted and removed anywhere in the stack, not just at the top. Conceptually, one should only call push() and pop(), but that's not enforced at the language level due to the backwards inheritance relationship.

    Stack's code doesn't violate the LSP, but its contract does: "The Stack class represents a last-in-first-out (LIFO) stack of objects." The fact that it doesn't enforce its own contract doesn't mean that it adheres to the LSP. Documentation matters, too.

    A better hierarchy would have a Stack interface with a concrete implementation that is backed by a Vector but does not provide access to the full set of Vector methods.

    public interface Stack<E> {
        E push(E item);
        E pop();
    }
    
    public class VectorStack<E> implements Stack<E> {
        private Vector<E> backingVector = new Vector<>();
    
        ...
    }
    
    Stack<E> stack = new VectorStack<>();
    

    Stack and Vector date back to the very first 1.0 version of Java. Java 1.2 introduced a much better set of collection classes in the form of the Collection and List interfaces and their various concrete implementations.

    Stack and co. are effectively deprecated and should not be used in modern code. The Stack API documentation recommends using Deque instead:

    A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:

    Deque<Integer> stack = new ArrayDeque<Integer>();
    

  • answered 2020-02-16 15:29 Maroun

    Having Stack extends Vector implies that it inherits all of the Vector's methods. This violates the principle. Why?

    The Stack abstract data type is a LIFO (last in, first out), and it usually supports operations like: pop, push, peek, top, isEmpty, ...

    Java's stack supports operations that are not "stack operations", that are inherited from the Vector's class, like insertElementAt, removeElementAt and more.

  • answered 2020-02-16 15:39 SDJ

    The JDK's implementation of Stack is strictly additive: it only adds a handful of methods to Vector's implementation without taking anything away. For this reason, it is always possible to assign (substitute) a Stack to a variable of type Vector without restricting what the client code can do. It is thus not a violation of the Liskov Substitution principle.

    However, its design is acknowledged to be flawed, but according to a different principle: Inheritance is appropriate only in circumstances where the subclass really is a subtype of the superclass.. From Effective Java:

    There are a number of obvious violations of this principle in the Java platform libraries. For example, a stack is not a vector, so Stack should not extend Vector.