Data Structures Midterms Reviewer PDF

Data Structures Midterms Reviewer 1. Stacks  Definition: A stack is an ordered list where the last element added is the first to be retrieved or removed (Last-In, First-Out or LIFO).  Common Operations: o Push: Adds an element to the top of the stack....

Data Structures Midterms Reviewer 1. Stacks  Definition: A stack is an ordered list where the last element added is the first to be retrieved or removed (Last-In, First-Out or LIFO).  Common Operations: o Push: Adds an element to the top of the stack.  Java: stack.push(element)  Python: stack.append(element) o Pop: Removes the element from the top of the stack.  Java & Python: stack.pop() o Peek: Views the top element without removing it.  Java: stack.peek()  Python: stack[-1] o Check if Empty:  Java: stack.isEmpty()  Python: if not stack  Applications: o Checking for palindromes. o Evaluating postfix expressions. o Converting infix expressions to postfix. 2. Queues  Definition: A queue is an ordered list where the first element added is the first to be retrieved or removed (First-In, First-Out or FIFO).  Common Operations: o Enqueue: Adds an element to the back of the queue.  Java: queue.offer(element)  Python: queue.append(element) (using collections.deque) o Dequeue: Removes the element from the front of the queue.  Java: queue.poll()  Python: queue.popleft() o Peek: Views the front element without removing it.  Java: queue.peek()  Python: queue o Check if Empty:  Java: queue.isEmpty()  Python: if not queue  Applications: o CPU and disk scheduling. o Managing tasks or customer requests. o Print queues or hotline management. 3. Trees  Definition: A tree is a hierarchical structure consisting of nodes, where each node can have multiple children but only one parent (except the root).  Key Terms: o Root: The topmost node of the tree. o Child/Parent Nodes: Nodes connected through edges; child nodes are successors of a parent. o Leaf Node: A node with no children. o Internal Node: A node with at least one child. o Subtree: A tree formed from a node and its descendants.  Types of Traversal: o Breadth-First: Visits nodes level by level. o Depth-First:  Inorder (Left, Root, Right): Used in binary trees.  Preorder (Root, Left, Right): Starts at the root.  Postorder (Left, Right, Root): Ends with the root.  Common Applications: o Representing file structures. o Hierarchical data storage. o Searching and sorting algorithms (binary search tree).