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

[Shavy Gaming]

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.

[avan]

Hey @Shavy-Gaming

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.

Here is the link:

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 head;
    private int size;

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

    public void addLast(int element) {
        checkCapacity();
        arr[(head + size++) % arr.length] = element;
    }

    public void addFirst(int element) {
        checkCapacity(); 

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

        size++;
    }

    public int removeFirst() {
        checkNotEmpty();

        int ret = arr[head];
        head = (head + 1) % arr.length;
        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) {
            sb.append(arr[(head + i) % arr.length]);

            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: ");
                deque.addLast(num);
                System.out.println(deque);
            } else {
                boolean add = random.nextBoolean();

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

                    if (front) {
                        System.out.print("Adding " + num + " to front: ");
                        deque.addFirst(num);
                        System.out.println(deque);
                    } else {
                        System.out.print("Adding " + num + " to back:  ");
                        deque.addLast(num);
                        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);
                    }
                }
            }
        }
    }
}