Source Code

Get programs to develop you own applications.

Deque ADT

Posted by mohammedmoulana on March 26, 2012

A deque is a double-ended queue. You can insert items at either end and delete them from either end. Methods are addFirst(), addLast(), removeFirst() and removeLast().
If you restrict yourself to addFirst() and removeFirst() (or their equivalents on the right), then the deque acts like a stack. If you restrict yourself to addFirst() and removeLast() (or the opposite pair), then it acts like a queue.
A deque provides a more versatile data structure than either a stack or a queue, and is sometimes used in container class libraries to serve both purposes. However, it is not used as often as stacks and queues.
The deque is maintained by either an array or linked list with pointers first and last which point to the two ends of the deque. Such a structure is represented by the following figure.

The methods of deque ADT are as follows:
addFirst(Object)
Inserts an item at the left side of deque.
addLast(Object)
Inserts an item at the right side of deque.
removeFirst()
Deletes an item from the left of deque.
removeLast()
Deletes an item from the right of deque.
getFirst()
Returns an item from the left, without deleting the item.
getLast()
Returns an item from right, without deleting the item.
size()
Returns the current number of items in the deque.
isEmpty()
Returns true, if deque is empty else returns false.

ArrayDeque

An ArrayDeque Class
public class ArrayDeque
{
private int maxSize;
private Object[] que;
private int first;
private int last;
private int count; // current number of items in deque
public ArrayDeque(int s) // constructor
{ maxSize = s;
que = new Object[maxSize];
first = last = -1;
count = 0;
}
public void addLast(Object item)
{ if(count == maxSize)
{ System.out.println(“Deque is full”); return; }
last = (last+1) % maxSize;
que[last] = item;
if(first == -1 && last == 0) first = 0;
count++;
}
public Object removeLast()
{ if(count == 0)
{ System.out.println(“Deque is empty”); return(‘ ‘);}
Object item = que[last];
que[last] = ‘ ’;
if(last > 0) last = (last-1) % maxSize;
count–;
if(count == 0) first = last = -1;
return(item);
}
public void addFirst(Object item)
{ if(count == maxSize)
{ System.out.println(“Deque is full”); return; }
if(first > 0) first = (first-1) % maxSize;
else if(first == 0) first = maxSize-1;

que[first] = item;
count++;
}
public Object removeFirst()
{ if(count == 0)
{ System.out.println(“Deque is empty”);
return(‘ ‘);
}
Object item = que[first];
que[first] = ‘ ’;
if(first == maxSize-1) first = 0;

else first = (first+1) % maxSize;
count–;
if(count == 0) first = last = -1;
return(item);
}
void display()
{ System.out.println(“—————————-“);
System.out.print(“first:”+first + “, last:”+ last);
System.out.println(“, count: ” + count);
System.out.println(” 0 1 2 3 4 5″);
System.out.print(“Deque: “);
for( int i=0; i
System.out.print(que[i]+ ” “);
System.out.println(“\n—————————-“);
}
public boolean isEmpty() // true if queue is empty
{ return (count == 0); }
public boolean isFull() // true if queue is full
{ return (count == maxSize); }
}

Testing ArrayDeque Class
class ArrayDequeDemo
{ public static void main(String[] args)
{ ArrayDeque q = new ArrayDeque(6); // queue holds a max of 6 items
q.insertLast(‘A’); /* (a) */
q.insertLast(‘B’);
q.insertLast(‘C’);
q.insertLast(‘D’);
System.out.println(“deleteFirst():”+q.deleteFirst());
q.display();
q.insertLast(‘E’); /* (b) */
q.display();
/* (c) */
System.out.println(“deleteLast():”+q.deleteLast());
System.out.println(“deleteLast():”+q.deleteLast());
q.display();
q.insertFirst(‘P’); q.insertFirst(‘Q’); /* (d) */
q.insertFirst(‘R’); q.display();
q.deleteFirst(); q.display(); /* (e) */
q.insertFirst(‘X’); q.display(); /* (f) */
q.insertLast(‘Y’); q.display(); /* (g) */
q.insertLast(‘Z’); q.display(); /* (h) */
}
}

Output of this program is as follows:
deleteFirst(): A
—————————-
first:1, last:3, count: 3
0 1 2 3 4 5

Deque: B C D
—————————-
first:1, last:4, count: 4
0 1 2 3 4 5
Deque: B C D E
—————————-
deleteLast(): E
deleteLast(): D
—————————-
first:1, last:2, count: 2
0 1 2 3 4 5
Deque: B C
—————————-
first:4, last:2, count: 5
0 1 2 3 4 5
Deque: P B C R Q
—————————-
first:5, last:2, count: 4
0 1 2 3 4 5
Deque: P B C Q
—————————-
first:4, last:2, count: 5
0 1 2 3 4 5
Deque: P B C X Q
—————————-
first:4, last:3, count: 6
0 1 2 3 4 5
Deque: P B C Y X Q
—————————-
Deque is full
—————————-
first:4, last:3, count: 6
0 1 2 3 4 5
Deque: P B C Y X Q
—————————-

Linked Deque
A deque is implemented by using a doubly linked list with references to first and last. Following figure illustrates the linked deque operations. Each node of the doubly linked list contains three fields: data, prev and next. The fields prev and next refer to the node itself.

A LinkedDeque class
public class LinkedDeque
{
public class DequeNode
{
DequeNode prev;
Object data;
DequeNode next;
DequeNode( Object item ) // constructor
{
data = item;
} // prev & next automatically refer to null
}

private DequeNode first, last;
private int count;
public void addFirst(Object item)
{ if( isEmpty() )
first = last = new DequeNode(item);
else
{ DequeNode tmp = new DequeNode(item);
tmp.next = first;
first.prev = tmp;
first = tmp;
}
count++;
}
public void addLast(Object item)
{
if( isEmpty() )
first = last = new DequeNode(item);
else
{ DequeNode tmp = new DequeNode(item);
tmp.prev = last;
last.next = tmp;
last = tmp;
}
count++;
}
public Object removeFirst()
{
if( isEmpty() )
{ System.out.println(“Deque is empty”);
return null;
}
else
{ Object item = first.data;
first = first.next;
first.prev = null;
count–;
return item;
}
}

public Object removeLast()
{
if( isEmpty() )
{ System.out.println(“Deque is empty”);
return null;
}
else
{ Object item = last.data;
last = last.prev;
last.next = null;
count–;
return item;
}
}
public Object getFirst()
{
if( !isEmpty() ) return( first.data );
else return null;

}
public Object getLast()
{
if( !isEmpty() ) return( last.data );
else return null;
}
public boolean isEmpty()
{ return (count == 0); }
public int size()
{ return(count); }
public void display()
{ DequeNode p = first;
System.out.print(“Deque: [ ");
while( p != null )
{ System.out.print( p.data + " " );
p = p.next;
}
System.out.println("]“);
}}

Testing LinkedDeque Class
public class LinkedDequeDemo
{
public static void main( String args[])
{
LinkedDeque dq = new LinkedDeque();
System.out.println(“removeFirst():” + dq.removeFirst());
dq.addFirst(‘A’);
dq.addFirst(‘B’);
dq.addFirst(‘C’);
dq.display();
dq.addLast(‘D’);
dq.addLast(‘E’);
System.out.println(“getFirst():” + dq.getFirst());
System.out.println(“getLast():” + dq.getLast());
dq.display();
System.out.println(“removeFirst():”+dq.removeFirst());
System.out.println(“removeLast():”+ dq.removeLast());
dq.display();
System.out.println(“size():” + dq.size());
}
}

Output of this program is:
Deque is empty
removeFirst(): null
Deque: [ C B A ]
getFirst(): C
getLast(): E
Deque: [ C B A D E ]
removeFirst(): C

removeLast(): E
Deque: [ B A D ]
size(): 3

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

Join 443 other followers

%d bloggers like this: