JavaCollections

Queue and Stack

Queue

The queue is a collection that is inserted and removed according to the first-in-first-out (FIFO) principle.

An excellent example of a queue is a line of students in the food court. New additions to a line made to the back of the queue, while removal (or serving) happens in the front. In the queue, only two operations are allowed enqueue and dequeue. Enqueue means to insert an item into the back of the queue, dequeue means removing the front item. In Java, these methods have other names.

The interface Queue

This interface extends the interface Collection and adds some new methods:

boolean add(E e) inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
boolean offer(E e) inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.
E remove() retrieves and removes the head of this queue; if it's empty, the method throws NoSuchElementException.
E poll() retrieves and removes the head of this queue, or returns null if this queue is empty.
E element() retrieves, but does not remove, the head of the queue; if it's empty, the method throws NoSuchElementException.
E peek() retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

Stack

The stack is a collection that are inserted and removed according to the last-in-first-out (LIFO) principle. In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure - elements can be added and removed from the stack only at the top.

A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top.

The Standard Class Library has the class Stack, but, according to JavaDoc, 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.

Deque

The java.util.Deque<E> interface extends the interface. java.util.Queue<E>. It represents a queue where you can insert and remove elements from both ends of the queue. Thus, "Deque" is short for "Double-Ended Queue".

It has methods for working with the first and the last element of a queue:

Table of deque methods: some throws an exception and some returns a special value

There are two implementations of the interface Deque: ArrayDeque and LinkedList. So, these classes can work as Queue (FIFO), Stack (LIFO), and Deque (Double-Ended Queue).

Deque in practice

It's possible to use implementations of the Deque interface as a queue (FIFO).

Queue<String> q = new ArrayDeque<>();

q.add("first");
q.add("second");
q.add("third");

System.out.println(q.peek()); // "first", it doesn't remove the element
System.out.println(q.peek()); // "first"
System.out.println(q.remove()); // "first", it removes and returns the head element

System.out.println(q.peek()); // "second"
System.out.println(q.remove()); // "second"

System.out.println(q.remove()); // "third"

System.out.println(q.isEmpty()); // "true"

Also, it's possible to use any implementation of the Deque interface as a stack (LIFO).

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

stack.offerLast("first");
stack.offerLast("second");
stack.offerLast("third");

System.out.println(stack); // [first, second, third]

System.out.println(stack.pollLast()); // "third"
System.out.println(stack.pollLast()); // "second"
System.out.println(stack.pollLast()); // "first"

System.out.println(stack.pollLast()); // null

The old Stack class

But sometimes, the class Stack<E> with more a minimalistic API is used. It doesn't implement Deque or Queue interface.

See an example below.

Stack<String> stack = new Stack<>();

stack.push("first");
stack.push("second");
stack.push("third");

System.out.println(stack); // [first, second, third]

System.out.println(stack.pop()); // "third"
System.out.println(stack.pop()); // "second"
System.out.println(stack.pop()); // "first"

System.out.println(stack.pop()); // throws EmptyStackException

The method pop() always throws an exception if the stack is empty.

According to the Java Doc, it's preferable to use implementations of the Deque interface as stacks.

How did you like the theory?

Report a typo