Data Structures · Module 1
Arrays, Stacks, Queues and Binary SearchChoose a data structure by the operations your program needs. A search history, a queue of print jobs and a sorted mark list may all contain records, but they need different rules for insertion, removal and lookup. 1. Arrays make position-based access simpleAn array places elements of the same type in consecutive slots. Given a valid index, an implementation can calculate the element’s address directly. Access by index takes constant time in the standard RAM model. Finding an unknown value in an unsorted array may require checking every element. Inserting into the middle of a packed array shifts later elements. For [10, 20, 30, 40], inserting 15 at index 1 first moves 40, 30 and 20 one place right. The resulting sequence is [10, 15, 20, 30, 40]. Reserving extra capacity avoids allocating on every append, but does not avoid those middle-insertion shifts. 2. A stack removes the most recent itemA stack uses last-in, first-out ordering. Push A, push B, pop, push C, pop produces B and then C. A remains in the stack. This makes stacks useful for nested operations such as parsing brackets, undo actions and traversing a search path. To check brackets, push each opening bracket. For each closing bracket, require a matching opening bracket on top, then pop it. At the end the stack must be empty. The text “([)]” fails because the first closing parenthesis encounters “[” on top. Merely counting opening and closing brackets would miss that error. 3. A queue serves the oldest itemA queue uses first-in, first-out ordering. Enqueue A, enqueue B, dequeue, enqueue C, dequeue produces A and then B. A circular array queue reuses freed slots by wrapping its indices around the capacity. Implementations need either an explicit count or a deliberate spare-slot convention to distinguish full from empty. In Python, a list can act as a stack through append and pop at the end. A deque is a practical queue representation when removing from the left; repeatedly removing the first list element shifts the remaining elements. 4. Trace binary search rather than memorizing itBinary search requires sorted data and a comparison rule consistent with that sorting. Use a half-open interval [low, high). For the sorted array [4, 9, 15, 21, 28, 36], search for 21:
5. Complexity and boundary checksEach binary-search iteration halves the candidate interval, giving O(log n) comparisons and O(1) extra space for this iterative implementation. Linear search needs O(n) comparisons in the worst case but works on unsorted input. Sorting only to run one search may cost more than scanning once. Test an empty list, a one-element list, a missing value smaller or larger than every entry, and repeated values. The function above returns the first equal value. For [2, 2, 2], target 2 gives 0. For [4, 9], target 5 gives -1. Further reference: the Python data structures tutorial includes practical stack, queue and dictionary operations. The worked traces here use their own inputs so you can repeat every step. |