Arrays, stacks, queues, linked lists

Array representation

Definition. An array stores a fixed number of elements of one type in contiguous memory. For a one-dimensional array with base address B and element size w, element i is at $B+iw$ when indexing begins at zero. C arrays do not store their length as part of the array value.

Example. If base=1000 and each item uses 4 bytes, a[3] starts at address 1012.

Exam point. Index bounds are 0 through n−1 for an n-element array.

Solved calculation. An array of 20 integers begins at address 5000; sizeof(int)=4. Find the address of a[13].

1. Zero-based offset is 13 elements.
2. Byte offset is $13\times4=52$.
3. Address is $5000+52=5052$. Answer. 5052.

Array operations and costs

Definition. Access by index takes constant time in the usual random-access memory model. Insertion or deletion near the front may require shifting many elements, giving linear time. Appending to a fixed array is constant time if capacity remains; dynamic-array resizing may make append amortized constant time.

Operation	Typical cost	Reason
Read/write index	$O(1)$	Direct address calculation
Search unsorted	$O(n)$	May inspect every element
Insert at front	$O(n)$	Shift existing entries
Delete at end	$O(1)$	Reduce logical length

Example. Inserting at index 0 in a full ordered array shifts all existing items one place right.

Exam point. State whether capacity and ordering must be preserved.

Two-dimensional arrays

Definition. A two-dimensional C array is an array of row arrays stored in row-major order. For an r×c array of element size w, a[i][j] has offset $(ic+j)w$ from the base. The last subscript changes fastest.

Example. In a 3×5 array, a[2][1] has element offset $2(5)+1=11$.

Exam point. Use the number of columns as the row stride.

Solved calculation. A 4×6 integer array starts at address 200 and sizeof(int)=4. Find a[2][3].

1. Element offset is $2(6)+3=15$.
2. Byte offset is $15\times4=60$.
3. Address is $200+60=260$. Answer. 260.

Linear search

Definition. Linear search checks elements sequentially until a key is found or the array ends. It works on sorted or unsorted arrays. For an n-element array, the worst case uses n comparisons; a successful search's average depends on key position distribution.

Example. Searching 9 in [4,9,1] takes two comparisons.

Exam point. A missing key requires checking all n entries.

Solved trace. Search 17 in [5,12,17,21,30].

1. Compare with 5: unequal.
2. Compare with 12: unequal.
3. Compare with 17: equal.
4. Stop; later values are not inspected. Answer. Found at index 2 after 3 comparisons.

Stack ADT

Definition. A stack supports insertion and removal at one end called the top. Push adds an item; pop removes and returns the most recently pushed item. The LIFO rule governs order. A stack may be array-based or linked, and operations are usually O(1) when capacity or allocation permits.

Example. Push A, then B; pop returns B.

Exam point. Underflow occurs when pop is requested on an empty stack; fixed-array overflow occurs when capacity is full.

Solved trace. Start with an empty stack; perform push(4), push(7), pop(), push(2), pop().

1. push(4): [4], top=4.
2. push(7): [4,7], top=7.
3. pop returns 7; stack is [4].
4. push(2): [4,2].
5. pop returns 2; stack is [4]. Answer. Popped sequence 7,2; final stack contains 4.

Array implementation of a stack

Definition. An array stack stores items from index 0 through top. An empty stack can use top=−1; push increments top before storing, and pop reads then decrements. Every operation must check the relevant boundary before changing top.

Example. With capacity 5 and top=4, another push would overflow.

Exam point. Check whether the implementation updates top before or after accessing the array.

Solved trace. Capacity is 4, initial top=−1. Push 6, push 8, pop, push 3. Give array contents and top.

1. Push 6: top=0, A[0]=6.
2. Push 8: top=1, A[1]=8.
3. Pop returns A[1]=8 and sets top=0.
4. Push 3 sets top=1 and A[1]=3. Answer. A[0]=6, A[1]=3, top=1; remaining cells are unused.

Stack applications

Definition. Stacks support nested function calls, parenthesis matching, expression evaluation, undo histories, and depth-first search. In infix conversion or evaluation, precedence and associativity determine when operators leave the stack. A delimiter checker pushes opening symbols and matches each closing symbol with the top.

Example. ([{}]) is balanced because each closing delimiter matches the most recent unmatched opener.

Exam point. The stack is LIFO; matching by type alone without checking order is insufficient.

Solved trace. Check ([)] using a delimiter stack.

1. ( pushes: [(].
2. [ pushes: [(,[].
3. ) expects ( but the top is [. The order is invalid.
4. The scan can reject immediately. Answer. Not balanced.

Queue ADT

Definition. A queue inserts at the rear and removes from the front, following FIFO order. Enqueue adds a new item; dequeue returns the oldest current item. A queue may be implemented with a linked list or a circular array to avoid shifting all entries after every deletion.

Example. Enqueue A, B then dequeue returns A.

Exam point. Track front and rear separately, including empty and one-element cases.

Circular queue

Definition. A circular array queue wraps indices modulo capacity. If capacity is C, the next index is $(i+1)\bmod C$. Implementations distinguish full from empty using a count, an extra slot, or a separate flag; the chosen convention determines the exact full condition.

Example. With capacity 5, advancing index 4 gives 0.

Exam point. Do not apply a full/empty rule from one circular-queue convention to another.