Java Stacks and Queues

Deque implementations

ArrayDeque: resizable, uses array internally, most efficient for most operations

LinkedList: doubly-linked list. See Lists cheatsheet

ConcurrentLinkedDeque: thread-safe, concurrent

LinkedBlockingDeque: thread-safe; has fixed size (specified as constructor parameter); blocks threads trying to insert elements to a full deque or remove elements from an empty deque, until space/elements are available; more memory overhead

Use Deque as stack

Add element

Throw exception if operation fails (e.g. if limited size deque is full):

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> kritaHistory = new ArrayDeque<>();
kritaHistory.addFirst("Insert image as new layer");
// or
kritaHistory.push("Move image on canvas");
// `kritaHistory` becomes [Move image on canvas, Insert image as new layer]

Return boolean:

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> kritaHistory = new ArrayDeque<>();
kritaHistory.offerFirst("Insert image as new layer");

Read first element

Throw exception if operation fails (e.g. if deque is empty):

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> kritaHistory = new ArrayDeque<>();
kritaHistory.addFirst("Insert image as new layer");
kritaHistory.addFirst("Move image on canvas");

String toUndo = kritaHistory.getFirst(); // "Move image on canvas"

Return null if operation fails:

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> kritaHistory = new ArrayDeque<>();
kritaHistory.addFirst("Insert image as new layer");
kritaHistory.addFirst("Move image on canvas");

String toUndo = kritaHistory.peekFirst(); // "Move image on canvas"
// or
String toUndo2 = kritaHistory.peek(); // "Move image on canvas"

Remove (and return) first element

Throw exception if operation fails (e.g. if deque is empty):

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> kritaHistory = new ArrayDeque<>();
kritaHistory.addFirst("Insert image as new layer");
kritaHistory.addFirst("Move image on canvas");

String undo = kritaHistory.removeFirst(); // "Move image on canvas"
// or
String undo2 = kritaHistory.pop(); // "Insert image as new layer"
// `kritaHistory` becomes empty

Return null if operation fails:

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> kritaHistory = new ArrayDeque<>();
kritaHistory.addFirst("Insert image as new layer");
kritaHistory.addFirst("Move image on canvas");

String undo = kritaHistory.pollFirst(); // "Move image on canvas"

Use Deque as queue

Add element

Throw exception if operation fails (e.g. if limited size deque is full):

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> pizzeriaOrders = new ArrayDeque<>();
pizzeriaOrders.addLast("pizza");
// or
pizzeriaOrders.add("lasagna");
// `pizzeria` becomes [pizza, lasagna]

Return boolean:

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> pizzeriaOrders = new ArrayDeque<>();
pizzeriaOrders.offerLast("pizza");
// or
pizzeriaOrders.offer("lasagna");
// `pizzeria` becomes [pizza, lasagna]

Read first element

Throw exception if operation fails (e.g. if deque is empty):

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> pizzeriaOrders = new ArrayDeque<>();
pizzeriaOrders.addLast("pizza");
pizzeriaOrders.addLast("lasagna");

String nextOrder = pizzeriaOrders.getFirst(); // "pizza"
// or
String nextOrder2 = pizzeriaOrders.element(); // "pizza"

Return null if operation fails:

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> pizzeriaOrders = new ArrayDeque<>();
pizzeriaOrders.addLast("pizza");
pizzeriaOrders.addLast("lasagna");

String nextOrder = pizzeriaOrders.peekFirst(); // "pizza"
// or
String nextOrder2 = pizzeriaOrders.peek(); // "pizza"

Remove (and return) first element

Throw exception if operation fails (e.g. if deque is empty):

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> pizzeriaOrders = new ArrayDeque<>();
pizzeriaOrders.addLast("pizza");
pizzeriaOrders.addLast("lasagna");

String completeOrder = pizzeriaOrders.removeFirst(); // "pizza"
// or
String completeOrder2 = pizzeriaOrders.remove(); // "lasagna"
// `pizzeriaOrders` becomes empty

Return null if operation fails:

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> pizzeriaOrders = new ArrayDeque<>();
pizzeriaOrders.addLast("pizza");
pizzeriaOrders.addLast("lasagna");

String completeOrder = pizzeriaOrders.pollFirst(); // "pizza"
// or
String completeOrder2 = pizzeriaOrders.poll(); // "lasagna"

Methods inherited from Collection

import java.util.Deque;
import java.util.ArrayDeque;

Deque<String> pizzeriaOrders = new ArrayDeque<>();
pizzeriaOrders.addLast("pizza");
pizzeriaOrders.addLast("lasagna");

int size = pizzeriaOrders.size(); // 2
boolean empty = pizzeriaOrders.isEmpty(); // false
boolean contains = pizzeriaOrders.contains("pizza"); // true

More inherited methods in the Java documentation, with examples in the Lists cheatsheet.