DSA
interface vs implementation
the contract vs the swappable backing structure
Source board
This definition comes from the board below. Open it to see the term in context.
Linked Lists Stacks and QueuesDSAMore terms from this board
- ADTabstract data type (interface, not storage)
- call stackthe CPU/OS stack of frames
- dequedouble-ended queue (O(1) both ends)
- head/tailfirst/last node
- LIFO/FIFOlast-in-first-out / first-in-first-out
- linked listnodes + next pointers (non-contiguous)
- monotonic dequekeeps a sorted window (sliding-window-max)
- nodevalue + pointer(s)
- priority queuehighest-priority-first (→ heap, l.05)
- queueFIFO (enqueue/dequeue, O(1))
- ring / circular bufferarray with wrapping head+tail (O(1) dequeue)
- singly / doubly linkednext only / next+prev
- stackLIFO (push/pop/peek, all O(1))