WAP to Implement DeQueue in Which Desired Operation Should be Execute in O(1)

Implement various operations of a double ended queue (Deque).
Deque is a data structure where items can be inserted and removed from both ends.
Operations :- insertToLeft(), removeFromLeft(), insertToRight(),removeFromRight().

This differs from the queue abstract data type or First-In-First-Out List (FIFO), where elements can only be added to one end and removed from the other. This general data class has some possible sub-types:

* An input-restricted deque is one where deletion can be made from both ends, but insertion can only be made at one end.

* An output-restricted deque is one where insertion can be made at both ends, but deletion can be made from one end only.

Both the basic and most common list types in computing, queues and stacks can be considered specializations of deques, and can be implemented using deques.

Implementations

There are at least two common ways to efficiently implement a deque: with a modified dynamic array or with a doubly linked list.

1st Method

using Doubly Linked List it works because we wants to do both operation start & end as DLL as prev & next pointers . it always possible to do above operation in O(1)

2nd Method


Dynamic array implementation uses a variant of a dynamic array that can grow from both ends, sometimes called array deques. These array deques have all the properties of a dynamic array, such as constant time random access, good locality of reference, and inefficient insertion/removal in the middle, with the addition of amortized constant time insertion/removal at both ends, instead of just one end. Three common implementations include:

* Storing deque contents in a circular buffer, and only resizing when the buffer becomes completely full. This decreases the frequency of resizings, but requires an expensive branch instruction for indexing.
* Allocating deque contents from the center of the underlying array, and resizing the underlying array when either end is reached. This approach may require more frequent resizings and waste more space, particularly when elements are only inserted at one end.
* Storing contents in multiple smaller arrays, allocating additional arrays at the beginning or end as needed. Indexing is implemented by keeping a dynamic array containing pointers to each of the smaller arrays.

1st Method - using Doubly Linked List

#include
#include
/*
Implement various operations of a double ended queue (Deque).
Deque is a data structure where items can be inserted and removed from both ends.
Operations :- insertToLeft(), removeFromLeft(), insertToRight(),removeFromRight().
*/
using namespace std;
class dequeu;

struct node
{
int data;
struct node *next;
struct node *prev;
friend class dequeue;
};
typedef struct node* Node;

class dequeue
{
Node head;
Node tail;
Node createNode(int data);
public:
dequeue():head(NULL),tail(NULL){}
~dequeue()
{
Node cur = head;
Node temp = NULL;
while(cur)
{
temp = cur;
cur=cur->next;
delete temp;
temp =NULL;
}
head = tail = NULL;
}


void insertToLeft(int data);
void insertToRight(int data);
int removeFromLeft();
int removeFromRight();
void print();
};

Node dequeue::createNode(int data)
{
Node temp = new struct node;
temp->data = data;
temp->prev = NULL;
temp->next = NULL;
return temp;
}

void dequeue::insertToLeft(int data)
{
Node temp = createNode(data);
if(head == NULL)
{
head= tail = temp;
}
else
{
temp->next = head;
head->prev = temp;
head = temp;
}

}

void dequeue::insertToRight(int data)
{
Node temp = createNode(data);
if(head == NULL)
{
head = tail = temp;
}
else
{
tail->next = temp;
temp->prev = tail;
tail = temp;
}
}

int dequeue::removeFromLeft()
{
if(head == NULL)
{
cout<<"Empty dequeue";
return -1;
}
else
{
Node temp = head;
if(head == tail)
{
head = tail = NULL;
}
else
{
head=head->next;
head->prev= NULL;
}
delete temp;
temp = NULL;
}
return 1;
}

int dequeue::removeFromRight()
{
if(tail == NULL)
{
cout<<"dqueue Empty ";
return -1;
}
else
{
Node temp = tail;
if(head == tail)
{
head = tail = NULL;
}
else
{
tail = tail->prev;
tail->next = NULL;
}
delete temp;
temp = NULL;
}
return 1;
}

void dequeue::print()
{
Node cur = head;
while(cur)
{
cout<<" "<data;
cur = cur->next;
}
cout<}

int main()
{
dequeue q;
int i;
for(i=1;i<6;i++)
q.insertToLeft(i);

for(i=6;i<11;i++)
q.insertToRight(i);

q.print();


q.removeFromRight();
q.removeFromLeft();

q.print();


q.removeFromLeft();
q.removeFromRight();

q.print();

}

TC O(1)
SC O(1)
Run Here https://ideone.com/UhKw0

* In a doubly linked list implementation and assuming no allocation/deallocation overhead, the time complexity of all deque operations is O(1). Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n).
* In a growing array, the amortized time complexity of all deque operations is O(1). Additionally, the time complexity of random access by index is O(1); but the time complexity of insertion or deletion in the middle is O(n).


Java program for Doing The Same

public class ListDeque
{
/** *//**
* This is the doubly-linked list node.
*/
private static class Node
{
public Node( AnyType d, Node p, Node n )
{
data = d; prev = p; next = n;
}

public AnyType data;
public Node prev;
public Node next;
}

private Node beginMarker;
private Node endMarker;
private int theSize;

public ListDeque()
{
beginMarker = new Node( null, null, null );
endMarker = new Node( null, beginMarker, null );
beginMarker.next = endMarker;

theSize = 0;
}


/** *//**
* Returns the number of items in this collection.
* @return the number of items in this collection.
*/
public int size( )
{
return theSize;
}


/** *//**
* Returns true if this collection is empty.
* @return true if this collection is empty.
*/
public boolean isEmpty( )
{
return (theSize == 0);
}


/** *//**
* Returns the first element of the deque
*
*/
public AnyType first()
{
if(size() == 0)
throw new QueueEmptyException("Empty Queue");

return beginMarker.next.data;
}


/** *//**
* Returns the last element of the deque
*
*/
public AnyType last()
{
if(size() == 0)
throw new QueueEmptyException("Empty Queue");

return endMarker.prev.data;
}


/** *//**
* Inserts e at the beginning (as the first element) of the deque
*
*/
public void insertFirst(AnyType e)
{
Node newNode = new Node( e, beginMarker, beginMarker.next );
newNode.prev.next = newNode;
newNode.next.prev = newNode;
theSize++;
}


/** *//**
* Inserts e at the end (as the last element) of the deque
*
*/
public void insertLast(AnyType e)
{
Node newNode = new Node( e, endMarker.prev, endMarker );
newNode.prev.next = newNode;
newNode.next.prev = newNode;
theSize++;
}


/** *//**
* Removes and returns the first element of the deque
*
*/
public AnyType removeFirst()
{
if(size() == 0)
throw new QueueEmptyException("Empty Queue");

AnyType temp = beginMarker.next.data;

beginMarker.next = beginMarker.next.next;
beginMarker.next.prev = beginMarker;

theSize--;

return temp;
}


/** *//**
* Removes and returns the last element of the deque
*
*/
public AnyType removeLast()
{
if(size() == 0)
throw new QueueEmptyException("Empty Queue");

AnyType temp = endMarker.prev.data;

endMarker.prev = endMarker.prev.prev;
endMarker.prev.next = endMarker;

theSize--;

return temp;
}
}



public class QueueEmptyException extends RuntimeException
{
public QueueEmptyException(String err) {
super(err);
}
}


public class Main6
{
public static void main(String[] args)
{
ListDeque deck = new ListDeque();

deck.insertFirst(new Integer(3));
deck.insertFirst(new Integer(5));
// (5,3)
System.out.println(deck.removeFirst()); // prints 5
// (3)
deck.insertLast(new Integer(7));
// (3,7)
System.out.println(deck.removeFirst()); // prints 3
//(7)
System.out.println(deck.removeLast()); // prints 7
// ()
deck.insertFirst(new Integer(1));
// (1)
System.out.println(deck.first()); // prints 1
// (1)
deck.insertFirst(new Integer(5));
// (5,1)
System.out.println(deck.last()); // prints 1
//
System.out.println(deck.removeFirst()); // prints 5
// (1)
deck.insertLast(new Integer(7));
// (1,7)
System.out.println(deck.removeFirst()); // prints 1
//(7)
System.out.println(deck.removeLast()); // prints 7
// ()

try
{
Integer a = deck.removeFirst();
System.out.println(a);
}
catch (Exception ex)
{
System.err.println(ex);
}

}
}

TC O(1) for Insertion/Deletion
SC O(1)

* In a doubly linked list implementation and assuming no allocation/deallocation overhead, the time complexity of all deque operations is O(1). Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n).
* In a growing array, the amortized time complexity of all deque operations is O(1). Additionally, the time complexity of random access by index is O(1); but the time complexity of insertion or deletion in the middle is O(n).


2nd Method Using Dynamic Array

/* Program of input and output restricted dequeue using array*/
# include
# define MAX 5

int deque_arr[MAX];
int left = -1;
int right = -1;


input_que()
{
int choice;
while(1)
{
printf("1.Insert at right\n");
printf("2.Delete from left\n");
printf("3.Delete from right\n");
printf("4.Display\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1:
insert_right();
break;
case 2:
delete_left();
break;
case 3:
delete_right();
break;
case 4:
display_queue();
break;
case 5:
exit();
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of input_que() */

output_que()
{
int choice;
while(1)
{
printf("1.Insert at right\n");
printf("2.Insert at left\n");
printf("3.Delete from left\n");
printf("4.Display\n");
printf("5.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1:
insert_right();
break;
case 2:
insert_left();
break;
case 3:
delete_left();
break;
case 4:
display_queue();
break;
case 5:
exit();
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of while*/
}/*End of output_que() */

insert_right()
{
int added_item;
if((left == 0 && right == MAX-1) || (left == right+1))
{
printf("Queue Overflow\n");
return;
}
if (left == -1) /* if queue is initially empty */
{
left = 0;
right = 0;
}
else
if(right == MAX-1) /*right is at last position of queue */
right = 0;
else
right = right+1;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
deque_arr[right] = added_item ;
}/*End of insert_right()*/

insert_left()
{
int added_item;
if((left == 0 && right == MAX-1) || (left == right+1))
{
printf("Queue Overflow \n");
return;
}
if (left == -1)/*If queue is initially empty*/
{
left = 0;
right = 0;
}
else
if(left== 0)
left=MAX-1;
else
left=left-1;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
deque_arr[left] = added_item ;
}/*End of insert_left()*/

delete_left()
{
if (left == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",deque_arr[left]);
if(left == right) /*Queue has only one element */
{
left = -1;
right=-1;
}
else
if(left == MAX-1)
left = 0;
else
left = left+1;
}/*End of delete_left()*/

delete_right()
{
if (left == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",deque_arr[right]);
if(left == right) /*queue has only one element*/
{
left = -1;
right=-1;
}
else
if(right == 0)
right=MAX-1;
else
right=right-1;
}/*End of delete_right() */

display_queue()
{
int front_pos = left,rear_pos = right;
if(left == -1)
{
printf("Queue is empty\n");
return;
}
printf("Queue elements :\n");
if( front_pos <= rear_pos )
{
while(front_pos <= rear_pos)
{
printf("%d ",deque_arr[front_pos]);
front_pos++;
}
}
else
{
while(front_pos <= MAX-1)
{
printf("%d ",deque_arr[front_pos]);
front_pos++;
}
front_pos = 0;
while(front_pos <= rear_pos)
{
printf("%d ",deque_arr[front_pos]);
front_pos++;
}
}/*End of else */
printf("\n");
}/*End of display_queue() */

int main()
{
int choice;

printf("1.Input restricted dequeue\n");
printf("2.Output restricted dequeue\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1 :
input_que();
break;
case 2:
output_que();
break;
default:
printf("Wrong choice\n");
}/*End of switch*/
}/*End of main()*/

TC O(1) for Insertion/Deletion
SC O(1)

* In a doubly linked list implementation and assuming no allocation/deallocation overhead, the time complexity of all deque operations is O(1). Additionally, the time complexity of insertion or deletion in the middle, given an iterator, is O(1); however, the time complexity of random access by index is O(n).
* In a growing array, the amortized time complexity of all deque operations is O(1). Additionally, the time complexity of random access by index is O(1); but the time complexity of insertion or deletion in the middle is O(n).


Java Program of Dequeue Using Dynamic Array

import java.lang.reflect.Array;

class Deque
{
private int maxSize=100;
private final Item[] array;
private int front,rear;
private int numberOfItems;
public Deque()
{
array=(Item[])(new Object[maxSize]);
front=0;
rear=-1;
numberOfItems=0;
}
public boolean isEmpty()
{
return (numberOfItems==0);
}
public void addFirst(Item item)
{
if(front==0)
front=maxSize;
array[--front]=item;
numberOfItems++;
}
public void addLast(Item item)
{
if(rear==maxSize-1)
rear=-1;
array[++rear]=item;
numberOfItems++;
}
public Item removeFirst()
{
Item temp=array[front++];
if(front==maxSize)
front=0;
numberOfItems--;
return temp;
}
public Item removeLast()
{
Item temp=array[rear--];
if(rear==-1)
rear=maxSize-1;
numberOfItems--;
return temp;
}
public int getFirst()
{
return front;
}
public int getLast()
{
return rear;
}
public static void main(String[] args)
{
Deque element1=new Deque();
Deque element2=new Deque();
for(int i=0;i element1.addFirst(args[i]);
try {
for(;element1.numberOfItems+1>0;)
{
String temp=element1.removeFirst();
System.out.println(temp);
}
}
catch(Exception ex)
{
System.out.println("End Of Execution due to remove from empty queue");
}
System.out.println();
for(int i=0;i element2.addLast(args[i]);
try {
for(;element2.numberOfItems+1>0;)
{
String temp=element2.removeLast();
System.out.println(temp);
}
}
catch(Exception ex)
{
System.out.println("End Of Execution due to remove from empty queue");
}
}
}