Go to the previous, next section.

Double ended Queues

Deques are declared as an "abstract" class. They are currently implemented in two ways.

XPDeque
implement dynamically-sized Deques via XPlexes.

DLDeque
implement dynamically-size Deques via linked lists.

All possess the same capabilities. They differ only in constructors. XPDeque constructors optionally take a chunk size argument. DLDeque constructors take no argument.

Double-ended queues support both stack-like and queue-like capabilities:

Assume the declaration of a base element x.

Deque d; or Deque d(int initial_capacity)
declares a deque.

d.empty()
returns true if deque d is empty.

d.full()
returns true if deque d is full. Always returns false in current implementations.

d.length()
returns the current number of elements in the deque.

d.enq(x)
inserts x at the rear of deque d.

d.push(x)
inserts x at the front of deque d.

x = d.deq()
dequeues and returns the front of deque

d.front()
returns a reference to the front of deque.

d.rear()
returns a reference to the rear of the deque.

d.del_front()
deletes, but does not return the front of deque

d.del_rear()
deletes, but does not return the rear of the deque.

d.clear()
removes all elements from the deque.

Go to the previous, next section.