deque

Complete

Summary

Deque

both LIFO and FIFO

Circular array implementation - arrays

Operation	Method	Performance
`enqueue(v)`	add before head/after tail	-
`dequeue()`	remove from head/tail	-
`peek()`	get head/tail	-

DLL implementation

Operation	Method	Performance
`enqueue(v)`	add before head/after tail	-
`dequeue()`	remove from head/tail	-
`peek()`	get head/tail	-

Concept

Dequeue ADT operations

enqueue(v)
- add v to the front/back of the deque
dequeue()
- get the first/last item in the deque and remove it
peek()
- get the first/last item in the deque without removing it

Deque as Queue

Queue Method	Deque Method
`add(v)`	`addLast(v)` or `add(v)`
`remove()`	`removeFirst()` or `remove()`
`peek()`	`peekFirst()` or `peek()`

Deque as Stack

Stack Method	Deque Method
`push(v)`	`addFirst(v)`
`pop()`	`removeFirst()` or `remove()`
`peek()`	`peekFirst()` or `peek()`

by convention following queue, the back(last) of the dequeue is the tail, the front(first) refers to the head

Application

Kattis: backspace

stack behaviour for backspace
queue behaviour for printing

java

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);

Deque<Character> dq = new ArrayDeque<>();

for (char c : br.readLine().toCharArray())
	if (c == '<') // we need LIFO
		dq.removeFirst();
	else
		dq.addFirst(c);

while (!dq.isEmpty())
	pw.append(dq.removeLast()); // we need FIFO

pw.println();
pw.close();

Kattis: integerlist

reversible queue

java

ArrayDeque<Integer> dq = new ArrayDeque<>();

for (int j = 0; j < n; j++)
	dq.add(Integer.parseInt(numArr[j])); // add normally

boolean reversed = false;
for (char c : prog.toCharArray()) {
	if (c == 'R') {
		reversed = !reversed;
	} else {
		if (!dq.isEmpty()) {
			if (reversed) { // take from head or tail depending on reversed state
				dq.pollLast();
			} else {
				dq.pollFirst();
			}
		}
	}
}

StringJoiner sj = new StringJoiner(",", "[", "]");
while (!dq.isEmpty()) {
	int next = 0;
	if (reversed) {
		next = dq.pollLast();
	} else {
		next = dq.pollFirst();
	}
	sj.add(String.format("%d", next));
}
pw.println(sj.toString());

pw.close();

use StringJoiner to handle the joining of strings separated by a delimter