Doubly ended queue

Question

*Can an input restricted deque be implemented using a linear queue instead of a circular queue?

Is this possibly (although not preferred) Please verify!!!

Here is the code(but the time complexity for insertion from front is O(n);*

    #include <stdio.h>
    #define SIZE 5
    struct QUEUE{
        int queue[SIZE];
        int front,rear;
    }q;
    int isFull(){
        if(q.rear==SIZE-1)return 1;
        return 0;
    }
    int isEmpty(){
        if(q.front==-1 ||q.front>q.rear)return 1;
        return 0;   
    }
    void enqueue_back(){
        if(!isFull()){
            int ele;
            printf("\nEnter the element you want to enqueue: ");
            scanf("%d\n",&ele);
            q.queue[++q.rear]=ele;
        }
        else{
            printf("\nThe Queue is Full.");
        }
        if (q.front==-1){
            q.front++;
        }  
    }
    void enqueue_front(){
        if (q.front==-1){
            q.front++;
        } 
        if(!isFull()){
            for (int i=q.rear+1;i>q.front;i--){
                
                q.queue[i]=q.queue[i-1];
            }
            int ele;
            printf("\nEnter the element you want to enqueue: ");
            scanf("%d\n",&ele);
            q.queue[q.front]=ele;
            q.rear++;
        }
else{
            printf("\nThe Queue is Full.");
        }
        }
    void dequeue(){
        if(!isEmpty()){
            ++q.front;
        }
        else{
            printf("\nThe Queue is Empty.");
        }
    }

Answer 1

Can an input restricted deque be implemented using a linear queue instead of a circular queue?

It can be, but as you noted it's going to be non-optimum. A standard queue supports two operations:

1. push - add an item to the queue.
2. pop - remove an item from the queue.

Items are removed in a first-in, last-out manner.

A double-ended queue supports four operations.

1. push-back - add an item to the back of the queue. This is the same as push in a standard queue.
2. pop-front - remove an item from the front of the queue. This is the same as pop in a standard queue.
3. push-front - add an item to the front of the queue.
4. pop-back - remove an item from the back of the queue.

It's possible to implement push-front and pop-back in terms of push and pop. In the case of push-front:

create a new queue
push the new item onto the new queue
for each item in the old queue
    pop from the old queue
    push onto the new queue
deleted the old queue

This operation, as you discovered, is O(n).

To implement pop-back

create a new queue
for each item on the old queue
    pop the item
    if the old queue is not empty
        push the item onto the new queue
    else
        delete the old queue
        return the item

Again, the complexity is O(n).

You can, however, create an input-restricted deque with a doubly-linked list. All you need is pointers to the head and tail of the list. It does not have to be circular.