Abstract Data Types — stack, queue, linked list
Abstract Data Types
- An Abstract Data Type (ADT) is a collection of data plus the operations on it, defined by what it does, not how it's stored.
- The user works only through the operations; the implementation is hidden.
- Know three: stack, queue, linked list.
An Abstract Data Type (ADT) is defined by:
An ADT specifies the operations (the interface); the implementation is hidden and can change freely.
Stack — LIFO
- A stack is Last In, First Out.
- Operations: push (add to the top), pop (remove from the top), peek (look at the top).
- Uses: undo history, function-call return addresses, expression parsing, backtracking.
A stack works in which order?
A stack is LIFO: the most recently pushed item is the first to be popped.
Which is a typical use of a stack?
Undo and the call stack are LIFO. Print spooling, fair scheduling and BFS use a queue (FIFO).
Queue — FIFO
- A queue is First In, First Out.
- Operations: enqueue (add to the rear), dequeue (remove from the front).
- Uses: print spooling, scheduling, breadth-first search, buffering.
A queue removes items from the ____ and adds them at the ____.
FIFO: dequeue from the front, enqueue at the rear.
Linked list
- A linked list is a sequence of nodes; each node holds a value and a pointer to the next node.
- A head pointer marks the start; the last node's pointer is a sentinel (
NULL). - Advantage over an array: cheap insertion/deletion (just adjust pointers). Disadvantage: slow random access (you must follow pointers from the head).
Each node of a linked list holds:
A node stores its value plus a pointer (reference) to the next node; the head marks the start, NULL the end.
Compared with an array, a linked list is better at:
Insert/delete only rewires pointers (cheap). The trade-off is slow random access — you must follow pointers from the head.
You've got it
- an ADT = data + operations, hiding the implementation
- stack = LIFO (push/pop the top) — undo, call stack
- queue = FIFO (enqueue rear, dequeue front) — spooling, scheduling
- linked list = nodes with a value + next pointer; cheap insert/delete, slow random access