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.



  • 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);
                        }
                    }
                }
            }
        }
    }