dsa.deque module

Module containing deque classes.

class dsa.deque.Deque(capacity=10)

Bases: object

A static deque implementation that supports appending and popping elements from both ends, with a fixed capacity.

append_left(element)

Append an element to the left of the deque. Raises an exception when the deque is full.

Parameters:

element – The element to append.

Raises:

Exception – If the deque is full.

append_right(element)

Append an element to the right of the deque. Raises an exception when the deque is full.

Parameters:

element – The element to append.

Raises:

Exception – If the deque is full.

back()

Get the element at the back of the deque without removing it. Raises an exception if the deque is empty.

Returns:

The rightmost element.

Raises:

Exception – If the deque is empty.

capacity()

Get the maximum capacity of the deque.

Return type:

int

Returns:

The capacity of the deque.

classmethod from_list(alist)

Create a deque from a given list. Raises an exception if list exceeds the deque’s capacity.

Parameters:

alist (list) – The list to initialize the deque with.

Returns:

a deque instance with elements from the list.

Raises:

Exception – If list exceeds the deque’s capacity.

front()

Get the element at the front of the deque without removing it. Raises an exception if the deque is empty.

Returns:

The leftmost element.

Raises:

Exception – If the deque is empty.

is_empty()

Return a Boolean on whether the deque is empty or not.

Return type:

bool

peek_left()

Get the element at the left of the deque without removing it. Raises an exception if the deque is empty.

Returns:

The leftmost element.

Raises:

Exception – If the deque is empty.

peek_right()

Get the element at the right of the deque without removing it. Raises an exception if the deque is empty.

Returns:

The rightmost element.

Raises:

Exception – If the deque is empty.

pop_back()

Pop an element from the back of the deque. (synonym for pop_right) Raises an exception if the deque is empty.

Returns:

The rightmost element of the deque.

Raises:

Exception – If the deque is empty.

pop_front()

Pop an element from the front of the deque. (synonym for pop_left) Raises an exception if the deque is empty.

Returns:

The leftmost element of the deque.

Raises:

Exception – If the deque is empty.

pop_left()

Remove and return the element from the left of the deque. Raises an exception if the deque is empty.

Returns:

The leftmost element of the deque.

Raises:

Exception – If the deque is empty.

pop_right()

Pop an element from right the deque. Raise an exception if the deque is empty.

Returns:

The rightmost element of the deque.

Raises:

Exception – If the deque is empty.

push_back(element)

Push an element at the back of the deque. (synonym for append_right) Raises an exception when the deque is full.

Parameters:

element – The element to append.

Raises:

Exception – If the deque is full.

push_front(element)

Push an element at the front of the deque. (synonym for append_left) Raises an exception when the deque is full.

Parameters:

element – The element to append.

Raises:

Exception – If the deque is full.

to_list()

Convert the deque’s contents into a list.

Returns:

A list containg the elements in the deque.

class dsa.deque.DynamicDeque(capacity=10)

Bases: Deque

A dynamic deque implementation that adjusts its capacity as needed.

append_left(element)

Append an element to the left, adjusting capacity if needed.

Parameters:

element – The element to append.

append_right(element)

Append an element to the right, adjusting capacity if needed.

Parameters:

element – The element to append.

check_capacity()

Helper method to adjust the capacity of the deque based on its count: if count >= capacity, grow the deque if count <= 1/4 of capacity, shrink the deque

grow()

Helper method to double the capacity of the deque.

pop_left()

Remove and return the element from the left, adjusting capacity if needed.

Returns:

The leftmost element.

pop_right()

Remove and return the element from the right, adjusting capacity if needed.

Returns:

The rightmost element.

shrink()

Helper method to halve the capacity of the deque.