Deque Implementation in Ruby

1. Introduction

A Deque (short for "double-ended queue") is a data structure that allows the addition or removal of elements from both its ends. Unlike a regular queue where operations are restricted to the front and back, a deque provides more flexibility with enqueue and dequeue operations possible at both the front and the rear. This versatile property makes deques useful in various applications such as in certain algorithm implementations and specific real-world scenarios.

2. Implementation Steps

1. Define the Deque class and initialize an empty list to store the elements.

2. Implement the add_front method to insert an element at the front of the deque.

3. Implement the add_rear method to insert an element at the rear of the deque.

4. Implement the remove_front method to remove and return the front element from the deque.

5. Implement the remove_rear method to remove and return the rear element from the deque.

6. Implement a method to check if the deque is empty and another to view its size.

3. Implementation in Ruby Programming

class Deque
    def initialize
        @items = [] # Initializing an empty array to store the deque elements
    end
    # Adding an item to the front of the deque
    def add_front(item)
        @items.unshift(item)
    end
    # Adding an item to the rear of the deque
    def add_rear(item)
        @items.push(item)
    end
    # Removing the front item from the deque
    def remove_front
        @items.shift
    end
    # Removing the rear item from the deque
    def remove_rear
        @items.pop
    end
    # Checking if the deque is empty
    def is_empty?
        @items.empty?
    end
    # Getting the size of the deque
    def size
        @items.length
    end
end
# Client code
dq = Deque.new
dq.add_front("Item A")
dq.add_rear("Item B")
dq.add_front("Item C")
puts "Size of deque after adding three items: #{dq.size}"  # Output: 3
puts "Removing front item: #{dq.remove_front}"  # Output: Item C
puts "Removing rear item: #{dq.remove_rear}"  # Output: Item B

Output:

Size of deque after adding three items: 3
Removing front item: Item C
Removing rear item: Item B

Explanation:

1. The Deque class is initialized with an empty array @items to store the deque's elements.

2. The add_front method uses the unshift method to add an element to the beginning of the @items array.

3. The add_rear method uses the push method to add an element to the end of the @items array.

4. The remove_front method uses the shift method to remove and return the first element from the @items array.

5. The remove_rear method uses the pop method to remove and return the last element from the @items array.

6. The is_empty? method checks if the @items array is empty, indicating that the deque is empty.

7. The size method returns the length of the @items array, representing the number of elements in the deque.