Double Ended Queue - Programming and Data Structures - Computer Science

Table of Contents
1. Introduction
2. Implementation of a Double-ended Queue
3. Time and Space Complexity
4. Advantages and Limitations
5. Alternative Implementations
6. Worked Example - Trace on Array of SIZE = 5
7. Applications of Deque
8. Implementation Notes and Edge Cases
9. Summary
View more

Introduction

A double-ended queue (commonly written deque or double-ended queue) is a linear data structure that allows insertion and removal of elements from both ends - the front and the back. It generalises both stacks and queues: a deque supports push and pop operations at both ends. Deques are used where flexibility of both LIFO and FIFO behaviour is required.

Implementation of a Double-ended Queue

One common implementation of a deque uses a circular array. The circular array lets front and rear indices wrap around when they reach the array boundaries, enabling efficient use of fixed array space. The implementation below provides the typical operations supported by a deque.

• push_back: insert element at back (rear)
• push_front: insert element at front
• pop_back: remove element from back
• pop_front: remove element from front
• get_back: return element at back without removing it
• get_front: return element at front without removing it
• empty: returns true if deque is empty
• full: returns true if deque is full (for fixed-size array)

The following C++ style outline shows a circular-array implementation with a fixed maximum size.

#define SIZE 5 class Dequeue { int *arr; int front, rear; public: Dequeue() { arr = new int[SIZE]; front = -1; rear = -1; } void push_front(int key); void push_back(int key); void pop_front(); void pop_back(); int get_front(); int get_back(); bool full(); bool empty(); };

Insert Element at Front (push_front)

Before inserting, check whether the deque is full. If not full, insert at the front using circular behaviour for the index.

• If the deque is empty, set front = rear = 0.
• Else if front == 0, wrap around and set front = SIZE - 1.
• Else decrement front by 1 and insert the element at arr[front].

void Dequeue::push_front(int key) { if (full()) { std::cout <>
";="" }="" else="" {="" if="" (front="=" -1)="" empty="" deque="" front="rear" =="" 0;="" else="" if="" (front="=" 0)="" wrap="" front="" to="" end="" front="SIZE" -="" 1;="" else="" --front;="" arr[front]="key;" }="" }="">

Insert Element at Back (push_back)

Before inserting, check whether the deque is full. If not full, insert at the rear using circular index updates.

• If the deque is empty, set front = rear = 0.
• Else if rear == SIZE - 1, wrap around and set rear = 0.
• Else increment rear by 1 and insert the element at arr[rear].

void Dequeue::push_back(int key) { if (full()) { std::cout <>
";="" }="" else="" {="" if="" (front="=" -1)="" empty="" deque="" front="rear" =="" 0;="" else="" if="" (rear="=" size="" -="" 1)="" wrap="" rear="" to="" start="" rear="0;" else="" ++rear;="" arr[rear]="key;" }="" }="">

Delete First Element (pop_front)

To remove the element at the front, first check if the deque is empty. If not empty, remove and update indices according to these rules.

• If only one element is present (front == rear), set front = rear = -1 to make the deque empty.
• Else if front == SIZE - 1, wrap and set front = 0.
• Else increment front by 1.

void Dequeue::pop_front() { if (empty()) { std::cout <>
";="" }="" else="" {="" if="" (front="=" rear)="" only="" one="" element="" front="rear" =="" -1;="" else="" if="" (front="=" size="" -="" 1)="" wrap="" front="" to="" start="" front="0;" else="" ++front;="" }="" }="">

Delete Last Element (pop_back)

To remove the element at the rear, first check if the deque is empty. If not empty, remove and update indices according to these rules.

• If only one element is present (front == rear), set front = rear = -1 to make the deque empty.
• Else if rear == 0, wrap and set rear = SIZE - 1.
• Else decrement rear by 1.

void Dequeue::pop_back() { if (empty()) { std::cout <>
";="" }="" else="" {="" if="" (front="=" rear)="" only="" one="" element="" front="rear" =="" -1;="" else="" if="" (rear="=" 0)="" wrap="" rear="" to="" end="" rear="SIZE" -="" 1;="" else="" --rear;="" }="" }="">

Check if Deque is Empty (empty)

A deque implemented with the above convention is empty when front == -1.

bool Dequeue::empty() { if (front == -1) return true; else return false; }

Check if Deque is Full (full)

For a circular array, the deque is full when the next position of rear is front. The common tests are shown below.

bool Dequeue::full() { if ((front == 0 && rear == SIZE - 1) || (front == rear + 1)) return true; else return false; }

Return First Element (get_front)

If the deque is not empty, return the value at arr[front]. If it is empty, indicate underflow or return a sentinel value (for example -1) as a simple error signal.

int Dequeue::get_front() { if (empty()) { std::cout <>
";="" return="" -1;="" }="" else="" {="" return="" arr[front];="" }="" }="">

Return Last Element (get_back)

If the deque is not empty, return the value at arr[rear]. If it is empty, indicate underflow or return a sentinel value.

int Dequeue::get_back() { if (empty()) { std::cout <>
";="" return="" -1;="" }="" else="" {="" return="" arr[rear];="" }="" }="">

Time and Space Complexity

• Time complexity: All fundamental deque operations (push_front, push_back, pop_front, pop_back, get_front, get_back, empty, full) take O(1) time in the circular-array implementation.
• Space complexity: The array implementation uses O(SIZE) space. For dynamic-size deques, a dynamic array or a linked list may be used.

Advantages and Limitations

• Advantages: constant-time insertions and deletions at both ends; simple array-based implementation when maximum size is known; useful in many algorithms (sliding window, caching, BFS with two-ended extensions).
• Limitations: fixed-size circular array has limited capacity and requires careful index management; resizing a circular array requires copying elements in correct order. A linked-list implementation removes fixed-size limitation but uses extra memory per node and has less cache locality.

Alternative Implementations

Deques can also be implemented using a doubly linked list. In a doubly linked list:

• Each node stores a value, a pointer to the next node and a pointer to the previous node.
• push_front and push_back add new nodes at the two ends; pop_front and pop_back remove nodes from the ends.
• All operations are O(1) time and the size can grow dynamically; however, extra memory is needed per node for pointers.

Worked Example - Trace on Array of SIZE = 5

Consider an initially empty deque with SIZE = 5 and the following sequence of operations:

• push_back(10)
• push_back(20)
• push_front(5)
• pop_back()
• push_back(30)
• push_back(40)
• push_back(50)
• pop_front()

Trace of front, rear and array contents after each operation:

• Initial: front = -1, rear = -1, arr = [ , , , , ]
• After push_back(10): front = 0, rear = 0, arr = [10, , , , ]
• After push_back(20): front = 0, rear = 1, arr = [10, 20, , , ]
• After push_front(5): front = SIZE-1 = 4, rear = 1, arr = [10, 20, , , 5]
• After pop_back(): removes arr[rear]=20, rear becomes 0, arr (logical) = [10, , , , 5]
• After push_back(30): rear becomes 1, arr = [10, 30, , , 5]
• After push_back(40): rear becomes 2, arr = [10, 30, 40, , 5]
• After push_back(50): rear becomes 3, arr = [10, 30, 40, 50, 5]
• After pop_front(): removes arr[front]=5, front wrapped from 4 to 0, logical contents = [10, 30, 40, 50]

This example demonstrates the wrap-around of indices and how the logical order differs from physical positions in the array.

Applications of Deque

• Implementing undo/redo functionality where operations are added and removed from both ends.
• Sliding window algorithms (e.g., find maximum in each window of size k) - deque optimises to O(n).
• Deque is used in certain BFS variants and bidirectional search algorithms.
• Circular buffers, scheduling, and caching schemes where both ends need updates.

Implementation Notes and Edge Cases

• Always check full() before a push in fixed-size array implementation to avoid overflow.
• Always check empty() before a pop or get to avoid underflow.
• When resizing a circular array, copy elements starting from front in logical order into a new larger array and reset front to 0 and rear to size-1 of the filled elements.
• Decide on an error-handling policy for underflow/full conditions: printing an error, throwing exceptions, or returning sentinel values are common choices in C++ implementations.

Summary

A deque is a flexible linear structure that permits insertion and deletion at both ends in constant time. The circular-array implementation is efficient when an upper bound on size is known, while a doubly linked list provides dynamic sizing. Understanding index updates (wrap-around) and careful handling of empty/full states are essential for a correct implementation.