Tech cheat sheets - Stacks & queues

A Stack data structure is a Last-In-First-Out (LIFO) list.  There is a Stack<T> Interface, but the recommended Java structure is the Deque (another interface featuring an Array and Linked implementation).

A Queue data structure is simply the opposite, First-In-First-Out (FIFO) structure. The current Java recommendation is also to use the Deque (noramlly pronounced "deck" if you were interested,  and stands for Double-Ended Queue)

Having read the discussion of ArrayList vs LinkedList, many of the same considerations apply - but given the common use-pattern of stacks/queues, the different implementations make sense.

Deque

Java's Deque implements the Queue interface, and can be used as either a Queue or a Stack, offering methods appropriate for either use.

ArrayDeque vs LinkedDeque

Similar to ArrayList, the Array based implementation is the most popular, and, by-and-large the most recommended implementation to use.

Based on what we already know about ArrayList and LinkedLists, and what we know about Stack vs Queue behaviour, there would be a natural use for each (e.g. LinkedList seems like a good option Stack/LIFO - we can easily add to the list by adding new objects to the front of the list, and then popping objects off the stack by removing from the head of the List - both operations O(1) - compared to the cost of adding to the front of an ArrayList that requires a lot of copying ).

However, in the ArrayDeque implementation it is a circular array - so no copying is required and add/remove is a constant O(1), and the LinkedList implementation creates a very slight performance overhead by using additional memory creating "nodes" for each object in the list.