Question

Give a pseudo-code description for an array-based implementation of the deque ADT (Abstract Data Type). What is the running time for each operation?

Answer 1

BELOW ARE DESCRIBED THE BASIC FUNCTIONALITIES OF DEQUE

IS EMPTY:

isEmpty(){
   if(head==tail)
       return true
   else
   false
}

IS FULL:

isFull(){
   if((tail + 1) == head)
       return true;
else if (tail == (size-1) && head == 0)
       return true;
   else return false;
}

PUSH BACK:

pushBack(element){
if( isFull() )
   output: deque is full
else if( isEmpty() ) pushFront(element);
else if( tail == (size - 1)){
data[tail] = element;
tail = 0;
}
else data[tail++] = element;
}

PUSH FRONT:

pushFront(element){
if( isFull() )
   output: cannot insert more
else if( isEmpty() && tail == size-1 ){
tail = 0;
data[head] = element;
}
else if( isEmpty() ) data[tail++] = element;
else if( head == 0 ){
head = (size - 1);
data[head] = element;
}
else data[--head] = element;
}

POP FRONT:

popFront(){
if( isEmpty() )
output deque is already empty
else if( head == (size - 1))
   head = 0;
else
   head++;
}

POP BACK:

popBack(){
if( is_empty() )
   output: already empty
else if( tail == 0 )
   tail = (size - 1);
else tail--;
}

PEEK FRONT:

peekFront(){
if( is_empty() )
   output: deque is empty
return data[head];
}

PEEK BACK:

peekBack(){
if( is_empty() )
   output: deque is empty
if( tail == 0 )
   return data[size-1];
return data[tail-1];
}

IF YOU HAVE ANY QUERY PLEASE COMMENT DOWN BELOW
PLEASE GIVE A THUMBS UP