deque ADT

Complete

Summary

Deque ADT

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	-

java.util.Dequeue interface

java.util.ArrayDeque -> circular array
java.util.LinkedList -> DLL

Library implemetations

java

import java.util.ArrayDeque;
import java.util.LinkedList;

Deque<Integer> A = new ArrayDeque<>();
// or
Deque<Integer> A = new LinkedList<>();
// insert at tail, following java.util.Queue
A.add(5);
A.add(10);
A.add(15);
A.add(25); // A = 5 -> 10 -> 15 -> 25

// insertHead
A.addFirst(4); // 4 -> 5 -> 10 -> 15 -> 25
// think of it as first element to be popped

// insertTail
A.addLast(8); // 4 -> 5 -> 10 -> 15 -> 25 -> 8

// remove at head, following java.util.Queue
int a = A.remove(); // 5 -> 10 -> 15 -> 25 -> 8

// removeHead
int b = A.removeFirst(); // 10 -> 15 -> 25 -> 8

// removeTail
int c = A.removeLast(); // 10 -> 15 -> 25

// peek at head, following java.util.Queue
int d = A.peek(); // 10

// peekHead
int e = A.peekFirst(); // 10

// peekTail
int f = A.peekLast(); // 25

Concept

Dequeue 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 ADT, 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