Java stack vs arraydeque

Java Stack vs Deque

Java has long had a badly written implementation of a stack. The stack is a great example of single responsibility; it’s supposed to implement LIFO and only LIFO behaviour. Java ignores this principle with the default implementation of Stack . It extends Vector and so is implemented in terms of inheritance rather than aggregation. It’s both a Stack and a Vector . They haven’t made the situation any better when recently deprecating Stack in favour of Deque .

Don’t Use Deque

I can understand that Sun/Oracle never corrected the mistake given Java’s principle of backwards compatibility but I was surprised when I noticed they recommend 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.

Oracle Documentation for Stack docs.oracle.com/javase/7/docs/…

A deque is a double ended queue, by definition it is not a stack. It allows LIFO and FIFO behaviour. I can’t see why Sun/Oracle are so happy to abandon encapsulation like this.

Why is this Important?

If you don’t control what operations a stack class can perform, you open up the class for non-stack like uses. For example, you might be able to insert objects into the middle of the stack. If client code starts using this behaviour, there’s immediately a dependency on it. The client code now depends on the implementation and not the role of your class. You won’t be able to swap out the implementation of your stack without potentially forcing changes to clients.

You could argue that this is the client code’s choice. For classes with well known semantics like the stack, any client using non-stack behaviour should appreciate the coupling and be able to make an informed decision. For more domain or business specific behaviours however, it’s very likely that clients will benefit by avoiding this coupling. Forcing clients to depend on defined roles rather than implementation allows for flexibility of substitution.

Use Encapsulation

It seems like we should really use a Stack abstraction to define the role and composition to implement the stack. That way, we’re able to substitute any implementation and expect our clients to still work. We won’t be able to break encapsulation by exposing methods we shouldn’t and we’ll allow clients to substitute alternative implementations.

 public interface StackT>   void push(T object);  T pop(); > 

 public class DequeStackT> implements StackT>   private final DequeT> deque = new ArrayDequeT>();  @Override  public void push(T object)   deque.addFirst(object);  >  @Override  public T pop()   return deque.removeFirst();  > > 

It’s important to note that I’m not saying use composition to enforce encapsulation though. The example above restricts what can be done with the underlying Deque . It’s hiding the implementation details and exposing the role through an interface. It’s using information hiding to achieve encapsulation. That’s not to say that you can’t achieve the same thing using inheritance.

For example, the naive BoundedStack implementation below is still a Stack . It inherits it, it has an “is a” relationship with Stack . Any stack implementation most certainly does not have a “is a” relationship with list ( Vector ) or double ended queue ( Deque ).

 public class BoundedStackT> extends DequeStackT>   // .  @Override  public void push(T object)   if (count  UPPER_BOUND)   count++;  deque.addFirst(object);  >  >  @Override  public T pop()   count--;  return deque.removeFirst();  > > 

Related

Liquid error: 765: unexpected token at ”

Posted by Toby Weston Jan 10 th , 2013 java, object-oriented

Источник

Stacks and Queues in Java

I have been working on some Java code recently that required both a stack and a queue. The choices to use aren’t immediately obvious. There is a Queue interface, but no clear concrete implementation to use. There is also a Stack class, but the javadocs point out that other classes “should be used in preference to this class”. So, what implementation do you use for stacks and queues in Java? I found my quick rule of thumb to be that you can use the ArrayDeque class for both Stack and Queues, but some more details are below.

Common Definitions

First, let’s start with some definitions. In common usage of the word, a queue is FIFO (first-in-first-out). Just like the first person in line at the post office gets served first. A stack is LIFO (last in first out). Think of a stack of books – the last book you put on the stack is the first book you take off.

Choices in Java

In Java, things are a little more complicated, but the same principles apply. There is the aforementioned Queue interface which has the expected methods to add, remove and look at elements. (Actually, those methods come in two flavors: one throws an exception if the operation fails, the other returns a special value such as null or false; see more here). There is also a sub-interface of Queue called Deque, short for “double ended queue” and is usually pronounced “deck”. This interface defines methods to access the elements at both ends of the collection. This functionality makes Deque a useful base for both queue and stack implementations. However, both Queue and Deque are interfaces, so we still haven’t found a concrete implementation to use yet…

The shortlist: ArrayDeque & LinkedList

The 2 main choices are: ArrayDeque and LinkedList. There are a couple of other implementation of Deque such as ConcurrentLinkedDeque and LinkedBlockingDeque, and a plethora of implementations of Queue such as DelayQueue, LinkedBlockingDeque and PriorityQueue. Since those are more specialized (and I haven’t used them much), I won’t go into here.

ArrayDeque

From the javadocs, ArrayDeque is a resizable-array implementation of the Deque interface. Most ArrayDeque operations run in amortized constant time (i.e. slower “once in a while”, but on average constant) except for remove*, contains* and the bulk operations, all of which run in linear time. The docs point out that this class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue. It is this statement that leads me to use ArrayDeque as my default implmentation for both stacks and queues.

LinkedList

The LinkedList class implements the List, Queue and Deque interfaces. In addition to implementing the List interface, the LinkedList class provides uniformly named methods to get, remove and insert an element at the beginning and end of the list. These operations allow linked lists to be used as a stack, queue, or double-ended queue.

LinkedList vs ArrayDeque

• more flexible than the ArrayDeque implementation, as it
  • implements all optional list operations.
  • allows null elements (not allowed in ArrayDeque)
  • not ideal when iterating over items in general
  • consumes more memory than the ArrayDeque implementation

  Overall

  In terms of efficiency, ArrayDeque is more efficient than the LinkedList for iteration and add/remove operation at both ends. So, as the javadocs point out, in general, ArrayDeque is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

  Reference: Stacks and Queues in Java from our JCG partner Shaun Abram at the Shaun Abram’s blog blog.

  Источник