Documentation
¶
Overview ¶
Package arraydeque implements a generic double-ended queue data structure based on a linear slice.
ArrayDeque is a data structure that allows efficient addition and removal of elements at both ends, internally using a linear slice as the underlying storage. All operations have the following time complexity: - PushBack, Back, Len, Cap, IsEmpty: O(1) time complexity - PushFront, PopFront: O(n) time complexity due to slice shifting - PopBack: O(1) time complexity (amortized)
Features:
- Support for addition and removal of elements at both ends
- Support for capacity management
- Support for iterator access
- Avoid memory leaks
Example usage:
// Create an integer double-ended queue
dq := New[int]()
// Add elements from the end
dq.PushBack(1)
dq.PushBack(2)
// Add element from the front
dq.PushFront(0)
// Access elements
front, _ := dq.Front() // 0
back, _ := dq.Back() // 2
// Traverse elements
for val := range dq.Iter() {
fmt.Println(val) // Output: 0, 1, 2
}
// Remove elements
val, _ := dq.PopFront() // 0
val, _ := dq.PopBack() // 2
Package arraydeque implements a generic double-ended queue data structure.
Index ¶
- type ArrayDeque
- func (d *ArrayDeque[T]) Back() (T, bool)
- func (d *ArrayDeque[T]) Capacity() int
- func (d *ArrayDeque[T]) Clear()
- func (d *ArrayDeque[T]) Clone() *ArrayDeque[T]
- func (d *ArrayDeque[T]) Extend(i iter.Seq[T])
- func (d *ArrayDeque[T]) Front() (T, bool)
- func (d *ArrayDeque[T]) IsEmpty() bool
- func (d *ArrayDeque[T]) Iter() iter.Seq[T]
- func (d *ArrayDeque[T]) IterBack() iter.Seq[T]
- func (d *ArrayDeque[T]) IterBackMut() iter.Seq[*T]
- func (d *ArrayDeque[T]) IterMut() iter.Seq[*T]
- func (d *ArrayDeque[T]) Len() int
- func (d *ArrayDeque[T]) PopBack() (T, bool)
- func (d *ArrayDeque[T]) PopFront() (T, bool)
- func (d *ArrayDeque[T]) PushBack(value T)
- func (d *ArrayDeque[T]) PushFront(value T)
- func (d *ArrayDeque[T]) Reserve(capacity int)
- func (d *ArrayDeque[T]) ShrinkToFit()
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ArrayDeque ¶
type ArrayDeque[T any] struct { // contains filtered or unexported fields }
ArrayDeque is a generic double-ended queue implementation based on a linear slice Using a slice as the underlying storage with direct indexing
func New ¶
func New[T any]() *ArrayDeque[T]
New creates a new empty double-ended queue
Type parameters:
- T: The type of elements in the queue
Returns:
- A new ArrayDeque instance
Time complexity: O(1)
func (*ArrayDeque[T]) Back ¶
func (d *ArrayDeque[T]) Back() (T, bool)
Back returns the element at the end of the queue (without removing it)
Returns:
- If the queue is not empty, returns the back element and true
- If the queue is empty, returns a zero value and false
Time complexity: O(1)
func (*ArrayDeque[T]) Capacity ¶
func (d *ArrayDeque[T]) Capacity() int
Capacity returns the capacity of the queue
Returns:
- The capacity of the queue
Time complexity: O(1)
func (*ArrayDeque[T]) Clear ¶
func (d *ArrayDeque[T]) Clear()
Clear empties the queue, removing all elements
Time complexity: O(n) Note: This method sets all elements to zero value to avoid memory leaks
func (*ArrayDeque[T]) Clone ¶
func (d *ArrayDeque[T]) Clone() *ArrayDeque[T]
Clone creates a deep copy of the queue
Returns:
- A new ArrayDeque instance containing all elements of the original queue
Time complexity: O(n)
func (*ArrayDeque[T]) Extend ¶
func (d *ArrayDeque[T]) Extend(i iter.Seq[T])
Extend appends all elements from the given iterator to the back of the deque
Parameters:
- i: An iterator over elements of type T
Time complexity: O(n)
func (*ArrayDeque[T]) Front ¶
func (d *ArrayDeque[T]) Front() (T, bool)
Front returns the element at the front of the queue (without removing it)
Returns:
- If the queue is not empty, returns the front element and true
- If the queue is empty, returns a zero value and false
Time complexity: O(1)
func (*ArrayDeque[T]) IsEmpty ¶
func (d *ArrayDeque[T]) IsEmpty() bool
IsEmpty checks if the queue is empty
Returns:
- true if the queue is empty, false otherwise
Time complexity: O(1)
func (*ArrayDeque[T]) Iter ¶
func (d *ArrayDeque[T]) Iter() iter.Seq[T]
Iter returns an iterator over all elements in the queue, in normal order.
Returns:
- An iterator over the elements, of type iter.Seq[T]
Time complexity: O(n)
func (*ArrayDeque[T]) IterBack ¶
func (d *ArrayDeque[T]) IterBack() iter.Seq[T]
IterBack returns an iterator over all elements in the queue, in reverse order.
Returns:
- An iterator over the elements in reverse order, of type iter.Seq[T]
Time complexity: O(n)
func (*ArrayDeque[T]) IterBackMut ¶
func (d *ArrayDeque[T]) IterBackMut() iter.Seq[*T]
IterBackMut returns a mutable iterator over all elements in the queue, in reverse order.
Returns:
- A mutable iterator over the elements in reverse order, of type iter.Seq[*T]
Time complexity: O(n)
func (*ArrayDeque[T]) IterMut ¶
func (d *ArrayDeque[T]) IterMut() iter.Seq[*T]
IterMut returns a mutable iterator over all elements in the queue, in normal order.
Returns:
- A mutable iterator over the elements, of type iter.Seq[*T]
Time complexity: O(n)
func (*ArrayDeque[T]) Len ¶
func (d *ArrayDeque[T]) Len() int
Len returns the number of elements in the queue
Returns:
- The number of elements in the queue
Time complexity: O(1)
func (*ArrayDeque[T]) PopBack ¶
func (d *ArrayDeque[T]) PopBack() (T, bool)
PopBack removes and returns the element from the end of the queue
Returns:
- If the queue is not empty, returns the removed element and true
- If the queue is empty, returns a zero value and false
Time complexity: O(1) Note: This method sets the position of the removed element to zero value to avoid memory leaks
func (*ArrayDeque[T]) PopFront ¶
func (d *ArrayDeque[T]) PopFront() (T, bool)
PopFront removes and returns the element from the front of the queue
Returns:
- If the queue is not empty, returns the removed element and true
- If the queue is empty, returns a zero value and false
Time complexity: O(n) (requires shifting all elements) Note: This method sets the position of the removed element to zero value to avoid memory leaks
func (*ArrayDeque[T]) PushBack ¶
func (d *ArrayDeque[T]) PushBack(value T)
PushBack adds an element to the end of the queue
Parameters:
- value: The element value to add
Time complexity: O(1) (amortized, O(n) when growing)
func (*ArrayDeque[T]) PushFront ¶
func (d *ArrayDeque[T]) PushFront(value T)
PushFront adds an element to the front of the queue
Parameters:
- value: The element value to add
Time complexity: O(n) (requires shifting all elements)
func (*ArrayDeque[T]) Reserve ¶
func (d *ArrayDeque[T]) Reserve(capacity int)
Reserve ensures that the queue has enough capacity to hold the specified number of elements
Parameters:
- capacity: The capacity to ensure
Time complexity: O(n) (only when expansion is needed)
func (*ArrayDeque[T]) ShrinkToFit ¶
func (d *ArrayDeque[T]) ShrinkToFit()
ShrinkToFit reduces the capacity of the queue to match its length
Time complexity: O(n)
Source Files