4.

Stacks and Queues 47

System.out.println("delete(): " + q.remove());

q.display();
System.out.println("size(): " + q.size());
}
}

Here is the output of this program:

Linked Q: empty
Linked Q: A B C D
remove(): A
Linked Q: B C D
peek(): B
remove(): B
Linked Q: C D E F
size(): 4

Deque ADT
22. Write Java programs to implement the deque (double ended queue) ADT using
(a) Array
(b) Doubly linked list.

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.

first last

Deletion Insertion
Insertion Deletion

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.
48 Lab Manual Data Structures through Java

ArrayDeque
Program 22(a) is an array implementation of ArrayDeque class and it is tested in Program 22(b).

Program 22(a): 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;
 4. Stacks and Queues 49

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<maxSize; 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); }
}

Program 22(b): 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
50 Lab Manual Data Structures through Java

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. Program 22(c) implements
LinkedDeque class which is tested in Program 22(d).

Program 22(c): 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
}
 4. Stacks and Queues 51

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;
52 Lab Manual Data Structures through Java

}
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("]");
}
}

Program 22(d): 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
 4. Stacks and Queues 53

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

Priority Queue
23. Write a Java program to implement a priority queue ADT.
In many situations, ordinary queues are inadequate, as when FIFO arrangement has to be overruled
using some priority criteria.
The problem with a priority queue is in finding an efficient implementation that allows relatively
fast insertion and deletion. Because items may arrive randomly to the queue, there is no guarantee that
the items at front will be the most likely to be removed and that the items inserted at the rear will be
the last items for deletion. Priority queues are implemented by using (1) arrays, (2) linked lists, (3)
binary heaps

Linked Implementation of a Priority Queue

We can represent a priority queue as an ordered linked list. The items of the queue are in ascending
order – the items of higher priority are at starting of the list. Each list node consists of three fields:
data, priority number and next. A node of higher priority is processed (removed) before any item of
lower priority. The items with the same priority are deleted according to the order in which they were
added to the queue – that is, FIFO discipline. The priority numbers work like this: the lower the
priority number, the higher the priority. The Node class is declared as follows (data field is a String
type, priority number, prn is an int, and next refers to the next node in the list):

class Node
{ data prn next
String data;
int prn;
Node next; Node
}

The head indicates (or refers to) first node of the list. The delete routine removes the head node
and makes the new head to refer to head next node.
Adding an item to the priority queue is complicated than deleting a node from the queue, because
we need to find the correct location to insert the node.
The insert method traverses the list until finding a node (call it N) whose priority number is
greater than priority number of new node to be added. Insert new node in front of N. If no such node is
found, insert new node after the end of the list (that is, as a last node of the list). While traversing the
list, the object reference of preceding node of the new node is to be saved.

LinkedPriorityQueue class implemented as a linked list is given in Program 23(b), and it is tested
in Program 23(c). Node class is defined in Program 23(a).

Program 23(a): Linked Priority Queue Node Class

public class Node
{ String data; // data item
int prn; // priority number (minimum has highest priority)
Node next; // "next" refers to the next node

Node( String str, int p ) // constructor

{ data = str;