Lists, stacks and queues

מילון מונחים

English	משמעות
array/əˈreɪ/	An indexed collection of elements arranged in one or more dimensions.
linked list/lɪŋkt lɪst/	linked list
node/nəʊd/	An individual unit or point in a network, graph, tree or linked data structure.
stack/stæk/	A last-in, first-out data structure in which items are added and removed at the same end.
queue/kjuː/	A data structure in which items are normally removed in the order they were added.

English

Two layouts, different ends

A Python list is a contiguous array: index $i$ computes the address in one step, but inserting at the front slides everyone. A linked list trades the jump for cheap splices: each node carries a pointer to the next.
A stack adds and removes at one end (LIFO); a queue enters one end and leaves the other (FIFO).

{exercise:uni-cs0502-layouts}

אימונים

Index number i in a contiguous array costs —

רמת קושי 1/5 · 100 מטבעות + בונוס קטן בהשלמה הראשונה היום

English

The array grows by doubling: appending $n$ items copies each element at most once across all regrows, so the average append is constant.
Front insertion never amortises: every insert(0) slides all residents — $n$ front-inserts move $\Theta(n^2)$ elements, and the count quadruples when $n$ doubles.

{exercise:uni-cs0502-append}

אימונים

Append at the end of a Python list is —

רמת קושי 1/5 · 100 מטבעות + בונוס קטן בהשלמה הראשונה היום

English

Stack: push 3, push 7, push 1, then pop, pop returns $1$ then $7$ — last in, first out. Balanced brackets ride the same discipline: scan ([]){} pushing opens; each closer must match the top, while ([)] fails because ) finds [ on top.
Queue: enqueue a, b, c; two dequeues return a then b; the front is c. collections.deque serves both ends in $O(1)$ — list.pop(0) in a loop is the classic $O(n)$ trap.

Example

Two stacks fake a queue: an inbox and an outbox, each element handled at most twice — which is why a real deque just does both ends natively.

{exercise:uni-cs0502-trace}

אימונים

push 3, push 7, push 1, pop, pop returns —

רמת קושי 1/5 · 100 מטבעות + בונוס קטן בהשלמה הראשונה היום