# Write algorithms to add and delete elements from either end of the deque.

• A double-ended queue (deque) is a linear list in which additions and deletions may be made at either end. Obtain a data representation mapping a deque into a one dimensional array. Write algorithms to add and delete elements from either end of the deque.

• I don't know C but with a little bit of googling I was able to find a Java implementation of a deque using a one-dimensional array.

https://codereview.stackexchange.com/questions/120722/array-based-deque-in-java

Here is the solution found on the page. You might be able to understand it enough to implement a C version of it. Keep in mind the main method just tests the Deque in this case. Good luck!

``````import java.util.NoSuchElementException;
import java.util.Random;

public class Deque {

private final int arr[];
private int size;

public Deque(int capacity) {
arr = new int[capacity];
}

checkCapacity();
arr[(head + size++) % arr.length] = element;
}

checkCapacity();

arr[(head = arr.length - 1)] = element;
} else {
}

size++;
}

public int removeFirst() {
checkNotEmpty();

size--;
return ret;
}

public int removeLast() {
checkNotEmpty();

int ret = arr[(head + size - 1) % arr.length];
size--;
return ret;
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");

for (int i = 0; i < size; ++i) {

if (i < size - 1) {
sb.append(", ");
}
}

return sb.append("]").toString();
}

public int size() {
return size;
}

private void checkCapacity() {
if (arr.length == size) {
throw new IllegalStateException("No more space is available.");
}
}

private void checkNotEmpty() {
if (size == 0) {
throw new NoSuchElementException("Trying to pop an empty deque.");
}
}

public static void main(String args[]) {
Deque deque = new Deque(10);
Random random = new Random();

for (int op = 0; op < 30; ++op) {
if (deque.size() == 0) {
int num = random.nextInt(100);
System.out.print("Adding " + num + " to front: ");
System.out.println(deque);
} else {

boolean front = random.nextBoolean();
int num = random.nextInt(100);

if (front) {
System.out.print("Adding " + num + " to front: ");
System.out.println(deque);
} else {
System.out.print("Adding " + num + " to back:  ");
System.out.println(deque);
}
} else {
boolean front = random.nextBoolean();

if (front) {
System.out.print("Removing from front: ");
deque.removeFirst();
System.out.println(deque);
} else {
System.out.print("Removing from back:  ");
deque.removeLast();
System.out.println(deque);
}
}
}
}
}
}``````