Data Structures: Stacks, Queues, Deques, Bags, and Recursion

Comprehensive vocabulary flashcards covering Queues, Deques, Priority Queues, Stacks, Bags, Sets, Linked Chains, Arrays, and Recursion based on computer science course quiz material.

Queue

An abstract data type (ADT) that exhibits first-in, first-out (FIFO) behavior, organizing its entries strictly according to the order in which they were added by inserting new items at the back and removing items from the front.

Enqueue

The queue operation that adds a new entry to the back of the queue; common aliases include add, put, and insert.

Dequeue

The queue operation that removes and returns the item located at the front of the queue, throwing an exception if the queue is empty; common aliases include remove, get, and delete.

getFront

The queue operation that retrieves the entry currently at the front of the queue without altering or removing it; commonly aliased as peek.

Deque

A double-ended queue ADT that allows operations to add, remove, or retrieve entries at both its front and back ends, behaving like both a queue and a stack.

Priority Queue

An ADT that organizes entries according to their priority rather than the order added; in Java, it cannot contain null entries and uses the compareTo method to determine entry order.

Time-Driven Simulation

A simulation wherein a counter explicitly enumerates simulated time units.

Circular Array Queue

An array-based queue implementation where the index of the first location follows the index of the last location using modulo arithmetic, typically leaving one array location unused or tracking item counts to differentiate between full and empty states.

Two-Part Circular Linked Chain

A queue implementation featuring a circular chain with two conceptual parts: nodes actively forming the queue, followed by available nodes referenced by a freeNode pointer to avoid frequent node deallocation and reallocation.

Doubly Linked Chain

A linked chain composed of nodes that each maintain references to both the next node and the previous node in the sequence.

Stack

An ADT that restricts access exclusively to its top entry, exhibiting last-in, first-out (LIFO) behavior where the most recently added item is the first one removed.

Push

The stack operation that adds a new entry onto the top of the stack; an alias is insert.

Pop

The stack operation that retrieves and removes the top entry from the stack, throwing an EmptyStackException if the stack is empty; aliases include pull, remove, and delete.

Peek

The stack operation that returns the entry located at the top of the stack without removing it; an alias is getTop.

Program Stack

The system call stack that stores activation records chronologically during program execution, where the top record belongs to the currently executing method.

Activation Record

A data structure pushed onto the program stack when a method is invoked, containing the method's arguments, local variables, and a copy of the program counter.

Program Counter

A processor or runtime register that references the instruction currently being executed.

Infix Expression

An ordinary algebraic expression where operators are written in-between their operands, governed by rules of operator precedence and parentheses.

Postfix Expression

Also known as Reverse Polish notation; an expression format where operators appear after their operands, eliminating the need for parentheses because operator evaluation order is strictly positional.

Polish Notation

An algebraic notation alternative, also called a prefix expression, in which operators are positioned before their operands.

Balanced Expression

An expression containing delimiters (such as parentheses, brackets, or braces) that are correctly matched and nested in pairs.

Recursive Method

A method that calls itself repeatedly, where each invocation solves a smaller, identical subproblem until reaching a non-recursive terminating condition.

Base Case

A condition in a recursive method that produces an immediate result without making any additional recursive calls.

Infinite Recursion

The runtime condition occurring when a recursive method fails to reach or satisfy its base case, repeatedly calling itself until program memory is exhausted.

Stack Overflow

An error that occurs when too many consecutive method calls create more activation records on the program stack than allocated memory can handle.

Tail Recursion

A specific recursive pattern where the very last action performed in a method's execution path is the recursive call.

Indirect Recursion

A recursive chain where a method calls another method that eventually loops back to invoke the original method (e.g., method X calls Y, Y calls Z, and Z calls X).

Mutual Recursion

A two-way recursive relationship where method X directly calls method Y, and method Y directly calls method X.

Recurrence Relation

A mathematical formula or equation that expresses the execution time or step complexity of a recursive method in terms of its value on smaller inputs.

Abstract Data Type (ADT)

A language-independent specification describing a group of values and the specific operations that may be performed on those values.

Data Structure

The concrete implementation of an abstract data type within a specific programming language.

Bag ADT

An unordered collection ADT that permits duplicate items and provides methods to query item counts, presence, and frequencies, without allowing clients to specify entry positions.

Set ADT

A specialized collection ADT derived from a bag that does not permit duplicate entries (no two objects where x.equals(y) is true).

Stub

An incomplete method definition written early during software implementation to prevent syntax errors, display test messages, or return dummy values for early driver testing.

Fail-Safe Programming

The defensive programming practice of anticipating potential runtime errors by thoroughly checking, validating input arguments, and handling boundary states.

Node

An object building-block in linked data structures that contains a data portion and one or more reference links pointing to other nodes.

Head Reference

An external reference variable that points directly to the first node in a linked chain.

Tail Reference

An external reference variable pointing directly to the last node in a linked chain, allowing $O(1)$ access to the end.

Inner Class

A non-static nested class defined completely within an enclosing class, allowing direct access to the outer class's private data fields.

Vector

A standard Java Class Library object that acts like a resizable, high-level array with a default initial capacity of 10 that doubles its size when filled.

Queues are used in operating systems. (True/False)

True

Unlike a stack, a queue does not restrict access to its entries. (True/False)

False

The Queue interface extends the Deque interface. (True/False)

False

A priority queue cannot have null entries. (True/False)

True

The Java Class Library ADT PriorityQueue uses what method to determine how to order entries?

compareTo

The ArrayDeque class implements the Stack interface. (True/False)

False

When a counter explicitly enumerates simulated time units, it is called a(n):

Time-driven simulation

The Java Class Library interface Queue method to put an entry on the back of a queue that throws an exception if the method fails is:

add

The Java Class Library interface Queue method to put an entry on the back of a queue that returns false if the method fails is:

offer

The Java Class Library interface Queue method that retrieves and removes the front entry and throws a NoSuchElementException if empty is:

remove

The Java Class Library interface Queue method that retrieves and removes the front entry and returns null if empty is:

poll

The Java Class Library interface Queue method that retrieves the front entry without removing it and throws a NoSuchElementException if empty is:

element

The Java Class Library interface Queue method that retrieves the front entry without removing it and returns null if empty is:

peek

Explain why the recursive Fibonacci program is so inefficient.

Numerous calls on the same sequence; the larger the sequence, the more repetitive and redundant the calculations become.

What is the efficiency for recursively traversing a chain of linked nodes?

$$O(n)$$

What is the efficiency for recursively calculating $x^n$?

$$O(\log(n))$$

What is the efficiency for solving the Towers of Hanoi problem recursively?

$$O(2^n)$$

In an array-based implementation of a queue, why is keeping the front entry at queue[0] inefficient?

It requires shifting all subsequent entries after every dequeue operation, resulting in $O(n)$ time.

In a circular array-based implementation of a queue, explain why checking for frontIndex equal to backIndex + 1 does not work to indicate a full queue.

It is the exact same condition used to indicate an empty array.

In a circular array-based implementation of a queue where one unused location differentiates front and back, the frontIndex is _ than the backIndex when full.

Two more

When would you choose a two-part circular linked chain over a standard circular chain for a queue?

When you frequently add an entry after removing one.

Why is it a bad programming practice for the Stack ADT clear method to simply set topIndex to -1 in an array-based implementation?

Memory references would still be allocated, preventing garbage collection.

In an array-based implementation of a Stack ADT, what value of topIndex indicates that the stack is empty?

-1

In the Java Class Library, what is the default initial capacity of a Vector?

10

Which Vector method is used to access the last entry?

lastElement

What exception type do the pop and peek methods throw when called on an empty stack in Java?

EmptyStackException (a RuntimeException)

Explain the rationale for returning a boolean value from the Bag add method.

A client should know what happened; a boolean value indicates true for success or false for a failed operation.

Explain why writing a test program before implementing an ADT class is beneficial.

It helps you understand the specifications before committing to your design and implementation.

Explain why the Set ADT does not need a getFrequencyOf operation.

A set contains no duplicate items; therefore, frequency is either 0 or 1 and unnecessary.

What is the design rationale for providing a toArray method instead of a displayBag method?

It gives the client freedom to display the elements of the bag in whatever format they choose.

Why doesn't the Bag contains method return the index of a located entry?

The internal index is an implementation detail that only the programmer needs; the client only needs to know whether the entry exists.

Which Java compiler annotation suppresses an unchecked-cast warning?

@SuppressWarnings("unchecked")

What is the most efficient approach to dealing with the gap left in an array after removing an entry from an unordered bag?

Replace the entry being removed with the last entry in the array, and replace the last entry with null.

When resizing an array to expand a bag, what exception should checkCapacity throw if memory limits are exceeded?

IllegalStateException

What occurs when a bag becomes full in a linked chain implementation?

An OutOfMemoryError will occur.

Should a linked chain Node class be public or private?

No, it should not be public; the implementation details of an ADT should remain private.

What happens at runtime when you attempt to access a reference that is null?

A NullPointerException is thrown.