# Java Stacks and Queues

Both stacks and queues are usually represented using the various implementations of Deque and its superinterface Queue.

All Deque (double ended queue) implementations can be used both as a stack or a queue, hence the name.

## Deque implementations

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

**LinkedList**: doubly-linked list. See [Lists cheatsheet](https://fosseryweb.codeberg.page/cheatsheets/java/lists.html)

**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):

```java
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:

```java
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):

```java
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:

```java
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):

```java
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:

```java
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):

```java
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:

```java
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):

```java
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:

```java
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):

```java
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:

```java
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

```java
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](https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html), with examples in the [Lists cheatsheet](https://fosseryweb.codeberg.page/cheatsheets/java/lists.html).