Queues and Stacks

False (B)

Because it has unimplemented methods

<p>mix</p> Signup and view all the answers

<p>They do not allow multiple inheritance. (D)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>Abstract Class = A class with at least one unimplemented method. Trait = A property that can be mixed into different classes. Inclusion Polymorphism = Allows a variable of a supertype to refer to objects of subtypes.</p> Signup and view all the answers

<p>fit</p> Signup and view all the answers

<p>An item and a reference to the next node (A)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>0</p> Signup and view all the answers

<p>front</p> Signup and view all the answers

<p><code>isEmpty</code> = Checks if the stack is empty <code>size</code> = Returns the number of elements in the stack <code>push</code> = Adds a new element to the top of the stack <code>pop</code> = Removes and returns the top element from the stack</p> Signup and view all the answers

<p>It creates a new node and places it such that current top node is its <code>next</code>. (C)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>4</p> Signup and view all the answers

<p>At the position <code>amount - 1</code> (C)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>Exception(&quot;Stack is empty&quot;)</p> Signup and view all the answers

<p>constant</p> Signup and view all the answers

<p>Linked nodes stack memory = Dynamically changes with the number of elements Array stack memory = Depends on the capacity of the underlying array Linked nodes stack = uses references to the elements and next node Array stack = stores elements next to each other</p> Signup and view all the answers

<p>Linked nodes stack memory changes dynamically with memory (C)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>wasted space and the restrictions</p> Signup and view all the answers

<p>It throws an exception. (D)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>amount</p> Signup and view all the answers

<p>0</p> Signup and view all the answers

<p><code>topNode</code> = Reference to the most recently added element in <code>ListStack</code> <code>amount</code> = Number of elements currently stored in <code>ArrayStack</code> <code>capacity</code> = Maximum number of elements <code>ArrayStack</code> can hold</p> Signup and view all the answers

<p>It moves the top reference to the next element in the list, effectively removing the top one. (D)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>It is needed for creating arrays of arbitrary types.</p> Signup and view all the answers

<p>To adjust the size of the underlying array when needed. (D)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>O(1)</p> Signup and view all the answers

<p>0.25</p> Signup and view all the answers

<p>Current amount of elements is less than 1/4 of the array size = Array size is halved Current amount of elements is greater than or equal to the array size = Array size is doubled Current amount of elements is between 1/4 and 1 of the array size = No change in array size</p> Signup and view all the answers

<p>The old array is removed. (B)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>Copying all elements when resizing.</p> Signup and view all the answers

<p><code>front</code> is equal to <code>back</code> (B)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>ring buffer</p> Signup and view all the answers

<p>empty</p> Signup and view all the answers

<p>When the queue is full (D)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>(back + 1) % n</p> Signup and view all the answers

<p>Queue is empty = <code>front == back</code> Queue is full = (back + 1) % n == front Enqueue element = store the element in <code>array(back)</code>, and update <code>back</code> Dequeue element = store the element at <code>front</code>, update <code>front</code></p> Signup and view all the answers

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.