Deque

Data Structures: Deque Data Structure

The Definition of a Deque​

A Deque (pronounced "deck"), which stands for "double-ended queue," is a data structure that allows you to add or remove items from both its front and back ends. It can be seen as a hybrid of a stack and a queue.

Instructions for Creating a Deque Data Structure​

Here's a step-by-step guide to creating a Deque:

1. Understand the Concept​

• A Deque supports four primary operations:
1. `pushFront`: Add an item to the front.
2. `pushBack`: Add an item to the back.
3. `popFront`: Remove and return an item from the front.
4. `popBack`: Remove and return an item from the back.

2. Define the Deque Data Structure​

For simplicity, we'll use a JavaScript array to back our Deque, but more efficient implementations might use a doubly-linked list or a circular buffer.

``class Deque {    constructor() {        this.items = [];    }}``

3. Implement the `pushFront` Method​

Add an item to the front of the Deque.

``// ... Inside Deque classpushFront(item) {    this.items.unshift(item);}``

4. Implement the `pushBack` Method​

Add an item to the back of the Deque.

``// ... Inside Deque classpushBack(item) {    this.items.push(item);}``

5. Implement the `popFront` Method​

Remove and return an item from the front. If the Deque is empty, return `null` or a similar sentinel value.

``// ... Inside Deque classpopFront() {    if (this.isEmpty()) {        return null;    }    return this.items.shift();}``

6. Implement the `popBack` Method​

Remove and return an item from the back. If the Deque is empty, return `null` or a similar sentinel value.

``// ... Inside Deque classpopBack() {    if (this.isEmpty()) {        return null;    }    return this.items.pop();}``

7. Implement the `isEmpty` Method​

Check if the Deque is empty.

``// ... Inside Deque classisEmpty() {    return this.items.length === 0;}``

8. Implement the `size` Method (Optional)​

Retrieve the number of items in the Deque.

``// ... Inside Deque classsize() {    return this.items.length;}``

9. Using the Deque​

``const deque = new Deque();deque.pushBack(5);deque.pushFront(3);deque.pushFront(2);console.log(deque.popBack());   // 5console.log(deque.popFront());  // 2console.log(deque.popFront());  // 3console.log(deque.popFront());  // null, since the deque is now empty``

10. Possible Extensions​

• peekFront: View the front item without removing it.
• peekBack: View the back item without removing it.
• clear: Clear all items from the Deque.
• toArray: Convert the Deque to an array.

tip

Remember, while our implementation utilizes JavaScript's built-in array methods for simplicity, this may not be the most efficient representation. For performance-critical applications, other implementations, such as a doubly-linked list, might be more appropriate.

Complexity​

A Deque (pronounced "deck") stands for "Double-Ended Queue." It's a generalized version of the queue data structure that allows insertions and deletions from both ends.

Here's a table for the time and space complexities for common operations on a Deque:

OperationTime ComplexitySpace Complexity
Insert FrontO(1)O(1)
Insert RearO(1)O(1)
Delete FrontO(1)O(1)
Delete RearO(1)O(1)
Peek FrontO(1)O(1)
Peek RearO(1)O(1)
Is EmptyO(1)O(1)
SizeO(1)O(1)

Notes:

1. Insert Front and Insert Rear: These operations add an element to the front or rear of the deque. The time complexity is constant if the deque is implemented using a doubly-linked list or a dynamic array with amortized constant time resizing.

2. Delete Front and Delete Rear: These operations remove an element from the front or rear. For a doubly-linked list implementation, this is O(1). For a dynamic array, deletions at the rear are O(1), but deletions at the front can be O(n) unless special techniques are used to ensure constant time operations.

3. Peek Front and Peek Rear: These operations retrieve but do not remove the front or rear element. This is always O(1) for both doubly-linked list and dynamic array implementations.

4. Is Empty and Size: Checking if the deque is empty or finding its size is typically O(1), especially if a size counter is maintained.

5. Space Complexity: The space used by the deque is determined by the number of elements in it. The operational space complexities are O(1) because operations do not use additional space that scales with the size of the deque (except for occasional resizing operations with dynamic arrays).

It's worth noting that deques can be implemented using various internal data structures like dynamic arrays or doubly-linked lists. The exact time complexities can depend on these internal implementations, but the table above assumes optimal implementations for each operation.