Python Programming and Data Structures

Stack, queue and hash table operations

A stack follows the last-in, first-out (LIFO) rule. Push adds an element to the top, pop removes the top element, and both run in constant time. A queue follows the first-in, first-out (FIFO) rule. Elements enter at the rear and leave from the front, which is why queues model waiting lines and breadth-first traversal. Memorize the pairs FIFO → queue and LIFO → stack, and the lookup operation → hash table.

A double-ended queue (deque) allows insertion and removal at both ends, so it generalizes both stacks and queues. Its operations are insertFirst, insertLast, removeFirst and removeLast. To trace a sequence, keep the contents as an ordered list and change only the indicated end. For example, starting from an empty deque, insertLast(4), insertFirst(1) and insertLast(9) give [1, 4, 9]. A following removeFirst() returns 1, and a removeLast() then returns 9.

A hash table stores each key at the index h(x) computed by a hash function, so a lookup computes h(x) and inspects that slot first. Collisions are resolved by open addressing, which probes other slots of the same table. With linear probing, the probe sequence is h(x), h(x)+1, h(x)+2, \ldots \pmod m. For instance, with m = 7 and h(x) = x \bmod 7, inserting 8 places it at index 1, and inserting 15 then finds index 1 occupied and moves it to index 2.

The load factor is \alpha = n/m, where n elements occupy m slots. Under uniform hashing with open addressing, an insertion follows the same probe sequence as an unsuccessful search, because it stops at the first empty slot. Its expected number of probes is therefore at most \frac{1}{1-\alpha} for \alpha < 1, and this bound grows without limit as \alpha \to 1. The logarithmic expression \ln\left(\frac{1}{1-\alpha}\right) belongs to the successful search analysis, not to insertion.

Tracing a stack-driven pseudocode means updating the stack after every push or pop and checking the loop condition after each step. When a step pops a value and conditionally pops again, record which elements are removed and which are discarded, since the order of removal is the reverse of insertion.

Recursive Python functions

A recursive function calls itself on a smaller input and must have a base case that returns without recursing. Tracing a recursive call means expanding the calls in order and combining results on the way back up, as the call stack does.

When a recursion updates a container in place, each call acts on a segment that shrinks from both ends. A function that swaps the outermost pair and then recurses with the bounds moved inward, such as calling itself with s_1+1 and s_2-1, reverses that segment in place. Recognize this pattern rather than assuming sorting.

In Python 3, the operator / always returns a float, so (a-1)/2 is a float such as 3.0 even when the value is integral. Such a float still compares equal to the integer 0, and the test a \% 2 == 1 still works, so the recursion behaves as intended. Keep this in mind when a recursion divides an integer argument.

The number of activations of a recursive function is counted by a recurrence. If a call with argument n makes calls with n-1 and n-2, and the base cases each count as one activation, then N(n) = 1 + N(n-1) + N(n-2) with N(n) = 1 for n \le 0. Evaluating from the base cases upward gives the total, including the initial call.

A recursive routine may also mutate a list and return a count. Each adjacent swap of an inverted pair removes exactly one inversion, so the total of all returned counts over repeated passes equals the number of inversions in the original list. An inversion is a pair of positions i < j with L[i] > L[j].

Binary tree traversal reconstruction

In a preorder traversal, the root is visited first; in a postorder traversal, the root is visited last; in an inorder traversal, the left subtree comes before the root and the right subtree after it. Because the root is identified by preorder or postorder, and inorder splits the sequence into left and right parts, a tree is uniquely determined by inorder together with either preorder or postorder. For example, if preorder is A, B, C and inorder is B, A, C, then A is the root, B is the left child, and C is the right child.