Abstract Data Types — stack, queue, linked list
| English | Chinese | Pinyin |
|---|---|---|
| abstract data type | 抽象数据类型 | chōu xiàng shù jù lèi xíng |
| stack | 栈 | zhàn |
| queue | 队列 | duì liè |
| linked list | 链表 | liàn biǎo |
| LIFO | 后进先出 | hòu jìn xiān chū |
| push | 入栈 | rù zhàn |
| pop | 出栈 | chū zhàn |
| enqueue | 入队 | rù duì |
| dequeue | 出队 | chū duì |
| FIFO | 先进先出 | xiān jìn xiān chū |
| node | 节点 | jié diǎn |
| pointer | 指针 | zhǐ zhēn |
Structures with rules
- 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.
Enqueue 入队 adds at the rear; dequeue 出队 removes from the front
Stacks, queues & linked lists
LIFO vs FIFO
A stack is last-in-first-out; push and pop happen at the same end (the top).
A stack works in which order?
A stack is LIFO: the most recently pushed item is the first to be popped.
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 linked list: each node 节点 points to the next
A queue is first-in-first-out: items are removed from the ______ and added at the rear.
FIFO: dequeue from the front, enqueue at the rear — like a line of people.
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).
- ADT operations are described in pseudocode.
A linked list: nodes joined by pointers
Each node stores a value and a pointer to the next node. Inserting or deleting just re-links pointers — no items shift along, unlike an array.
Match each ADT to its rule and a typical use.
Stack = last-in-first-out; queue = first-in-first-out; a linked list chains nodes with pointers.
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.
A linked list makes inserting/deleting cheap (just rewire pointers) but random access slow (you must follow pointers from the head).
That is the array-vs-list trade-off: arrays give O(1) index access; lists give cheap insert/delete.
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