Queues and Stacks

An abstract class is a class that has at least one unimplemented (abstract) method. Abstract classes can't be directly instantiated but serve as blueprints for concrete subclasses.

A class that inherits from an abstract class must either implement the abstract methods or be declared abstract itself.

A trait is a construct that combines properties from different sources into a single entity.

Traits are often used to define functionality that can be reused across different classes, promoting code reusability and modularity.

Traits can include abstract methods, attributes, concrete methods, constructors and even inherit from other traits.

A data structure that follows the Last-In-First-Out (LIFO) principle, allowing you to add (push) or remove (pop) elements only from the top.

A node in a linked list storing data and a reference to the next node.

A private inner class within the LinkedNodesStack class, representing a single element in a stack.

A reference to the node at the top of a linked list stack.

The number of elements currently stored in a stack, a positive integer.

A method that adds an element to the top of a stack.

A method that removes and returns the element at the top of a stack.

A method that returns the element at the top of a stack without removing it.

The element at the top of the stack.

An array implementation of a stack uses a fixed-size array to store elements. The stack grows by adding elements to the end of the array.

The amount variable in an array-based stack keeps track of how many elements are currently in the stack.

A stack is considered empty when there are no elements in it.

In an array stack, the index amount - 1 points to the most recent element added.

The push operation adds a new element to the top of the stack. In an array-based stack, it adds the element to the next available index in the array.

The pop operation removes and returns the element at the top of the stack. In an array-based stack, it removes the element at index amount - 1 and decrements the amount variable.

In data structures, this refers to the time needed for an operation to complete. Operations with constant time complexity execute in the same amount of time regardless of the size of the data structure.

A data structure that allows for access to elements in a sequential way, where each element points to the next element. This type of structure offers flexibility in memory allocation.

A data structure where all elements are stored in contiguous memory locations, offering efficient access to elements at specific indices.

This refers to the amount of memory a data structure requires. It can change based on the number of elements stored.

The ratio between the actual number of elements used in a data structure and its maximum capacity. A large gap indicates wasted space.

The ability to dynamically change the size of a data structure as needed, responding to changes in data volume.

The ArrayQueue class utilizes a fixed-size array to store elements. This array is treated as a circular buffer, where the front and back indices wrap around to create a continuous loop.

In the ArrayQueue, the front index points to the first element in the queue, and the back index points to the next available position for adding a new element.

An empty queue is characterized by the condition front == back. This means that both indices point to the same location, indicating no elements are present.

A full queue is identified when (back + 1) % n == front, where n is the size of the array. This constraint ensures that there's always at least one empty slot for adding elements.

The enqueue operation adds an element to the queue by storing it at the back index and then advancing the back index to the next available position in the circular buffer.

The dequeue operation retrieves and removes the first element from the queue. It involves storing the element at the front index, setting that array position to null, and then moving the front index to the next position.

The array used in ArrayQueue is created with a specific capacity. This capacity represents the maximum number of elements the queue can hold. The actual number of elements in the queue (its size) can vary but never exceed the capacity.

In the ArrayQueue implementation, the actual number of elements stored in the queue is one less than the capacity of the array. This is because the back index always points to an available slot, leaving one position unused.

The resize() method in a DynamicArrayStack is responsible for adjusting the underlying array's size to accommodate changes in the number of elements in the stack.

When the number of elements in the stack exceeds the array capacity (or falls below a quarter of the capacity), the resize() function dynamically resizes the array to either double or half its size. This maintains efficiency by preventing unnecessary memory waste.

In a DynamicArrayStack, the resize() method is called after a push() or pop() operation to maintain an optimal ratio of elements to array size. This ensures that the array isn't too large or too small, preventing wasted memory and inefficient operations.

The push() operation adds an element to the top of the stack. In DynamicArrayStack, it also checks if the array needs resizing. If it does, resize() is called to ensure sufficient space.

The pop() operation removes and returns an element from the top of the stack. It also involves a size check and potential resizing to handle a shrinking stack.

The DynamicArrayStack implementation aims to maintain a balance between array size and the number of elements in the stack. It targets a ratio between 0.25 and 1, signifying a good utilization of memory.

While the resize() function might handle resizing the array, it involves copying all existing elements. This can lead to a worst-case time complexity of O(n) for individual push() and pop() operations.

Despite the potential for O(n) complexity in individual operations, resize() is strategically triggered to ensure optimal array size. As a result, the amortized time complexity of push() and pop() in a DynamicArrayStack is considered O(1) because the costly resize() operations are infrequent relative to the overall number of operations.