In the preceding section we saw that a queue in which we insert items at one end and from which we remove items at the other end. In this section we examine an extension of the queue,Deque ,which provides a means to insert and remove items at both ends of the queue. This data structure is a deque. The word deque is an acronym derived from double-ended queue. Figure 4.5 shows the representation of a deque.
A deque provides four operations. Figure 4.6 shows the basic operations on a deque.
- enqueue_front: insert an element at front.
- dequeue_front: delete an element at front.
- enqueue_rear: insert element at rear.
- dequeue_rear: delete element at rear.
There are two variations of deque. They are:
- Input restricted deque (IRD)
- Output restricted deque (ORD)
An Input restricted deque is a deque, which allows insertions at one end but allows deletions at both ends of the list.
An output restricted deque is a deque, which allows deletions at one end but allows insertions at both ends of the list.