Navigation

    ask avan logo
    • Register
    • Login
    • Search
    • Categories
    • Unsolved
    • Solved

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

    C
    2
    2
    296
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • Shavy Gaming
      Shavy Gaming last edited by

      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.

      Reply Quote 0
        1 Reply Last reply

      • avan
        avan last edited by 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);
                            }
                        }
                    }
                }
            }
        }
        Reply Quote 0
          1 Reply Last reply

        • First post
          Last post