Abstract Data Types — stack, queue, linked list
| English | Chinese | Pinyin |
|---|---|---|
| queue | 队列 | duì liè |
| push | 入栈 | rù zhàn |
| abstract data type | 抽象数据类型 | chōu xiàng shù jù lèi xíng |
| stack | 栈 | zhàn |
| linked list | 链表 | liàn biǎo |
| LIFO | 后进先出 | hòu jìn xiān chū |
| pop | 出栈 | chū zhàn |
| pointer | 指针 | zhǐ zhēn |
| FIFO | 先进先出 | xiān jìn xiān chū |
| enqueue | 入队 | rù duì |
| dequeue | 出队 | chū duì |
| node | 节点 | jié diǎn |
| traverse | 遍历 | biàn lì |
The Back button and the printer queue
- Every page you visit is pushed onto a pile; the Back button takes the top one off. The page you left most recently is the first you return to.
- Down the corridor, a printer works through jobs in the order they arrived. The document sent first comes out first, however small the ones behind it.
- Two structures, opposite rules, and you use both before break. Neither says how it is stored; each says only what its operations do.
- That is an abstract data type 抽象数据类型. This lesson is the three the syllabus names, the operations on each, and how to justify one for a situation.
What an ADT is
- An abstract data type (ADT) is a collection of data together with a set of operations on that data. That one sentence is the one-mark definition.
- It is defined by what the operations do, not by how the data is stored. The implementation is hidden, so it can change without affecting the code that uses it.
- A stack, a queue, a linked list, a binary tree and an array are all ADTs.
An Abstract Data Type (ADT) is defined by:
An ADT specifies the operations (the interface); the implementation is hidden and can change freely.
The stack
- A stack 栈 is a list in which items are added to and removed from the same end, the top, so the last item added is the first removed: LIFO 后进先出.
- Operations: push 入栈 adds to the top, pop 出栈 removes from the top, peek looks at the top, and tests for empty and full.
- Uses: undo history, the Back button, the return addresses of function calls, checking brackets, backtracking.
Everything happens at the top
A stack works in which order?
A stack is LIFO: the most recently pushed item is the first to be popped.
Worked example: trace the stack
- A stack holds, from the bottom,
'P' 'N' 'Z' 'X' 'Y' 'W'; the top pointer is at'W'. The operationsPOP,POP,PUSH 'A',PUSH 'B',POPare performed. What does the stack hold, and where is the pointer? - The two pops remove
'W'then'Y'. The pushes put'A'then'B'in their places. The last pop removes'B'. - The stack holds
'P' 'N' 'Z' 'X' 'A', with the pointer at'A'. The item on the stack longest is the bottom one,'P'; five more pops are possible, and a sixth would be an error, which is why pop tests for empty first.
A stack holds P N Z X Y W (top is W). After POP, POP, PUSH 'A', PUSH 'B', POP, which item is on top?
W and Y are popped, A then B pushed, B popped. The top is A, above X.
The queue
- A queue 队列 is a list in which items are added at the rear and removed from the front, so the first item added is the first removed: FIFO 先进先出.
- Operations: enqueue 入队 adds at the rear, dequeue 出队 removes from the front, and tests for empty and full.
- Uses: print spooling, keyboard buffers, scheduling, customers in a shop, breadth-first search.
Join at the back, leave 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 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.
Worked example: describe adding to and removing from a queue
- Adding: check that the queue is not full; store the item at the position given by the rear pointer; move the rear pointer on (and add one to the count).
- Removing: check that the queue is not empty; read the item at the front pointer; move the front pointer on (and subtract one from the count).
- State the convention you use: if the rear pointer marks the next free space, store first and then move; if it marks the last item, move first and then store. Either scores, if you are consistent.
Put the steps of adding an item to a queue in order (rear pointer marks the next free space).
The check comes first; then store, then move, under this convention. Say which convention you use.
The linked list
- A linked list 链表 is a list in which each node 节点 holds a data item and a pointer 指针 to the next node, with a start pointer to the first node. The last node's pointer is a sentinel such as
NULL. - Operations: insert, delete, search, and traverse 遍历, following the pointers from the head to visit every node in order.
- Advantage over an array: inserting or deleting is cheap, just rewire pointers, and the list grows as needed. Disadvantage: no random access; reaching the tenth node means following nine pointers.
A value and an arrow, repeated
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.
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.
Worked example: add a node in order
- Describe how a new value is inserted into a linked list that is kept in ascending order. [4]
- Traverse the list from the head, following the pointers, until the node before the position is found: the last node whose value is smaller than the new one.
- Take a free node and store the new value in it. Set the new node's pointer to the address the previous node currently points to.
- Then set the previous node's pointer to the new node. If the new value belongs at the front, it is the head pointer that changes instead.
Put the steps of inserting a value into an ordered linked list in order.
Find, fill, point the new node forward, then rewire the previous node. Reversing the last two loses the rest of the list.
Justifying the choice
- Items must be handled in the order they arrived, print jobs, key presses, customers: a queue, because it is first in, first out.
- The most recent item must be handled first, undo, going back, nested calls: a stack, because it is last in, first out.
- Items are frequently inserted or deleted in the middle of an ordered collection, and the size is unknown: a linked list, because only pointers change and nothing is shifted.
- Name the structure, name its rule, tie the rule to the situation.
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.
Print jobs must be printed in the order they were sent. Which ADT, and why?
Order of arrival is the FIFO rule. A stack would print the most recent job first.
ADT versus implementation
- The ADT is the behaviour: push and pop, enqueue and dequeue, insert and traverse.
- The implementation is the storage: in this course, an array plus a few pointer variables (next lesson).
- A question about the ADT wants operations and rules; a question about implementation wants arrays, pointers and the checks.
Marks that slip away
- Push and enqueue test for full first; pop and dequeue test for empty first. Write the check into the description.
- Inserting into a linked list: set the new node's pointer before changing the previous node's, or the rest of the list is lost.
- A stack changes at one end, a queue at both. "Remove from the top of the queue" is a stack answer.
- Expand the abbreviations once: LIFO, last in first out; FIFO, first in first out.
You've got it
- an ADT is a collection of data together with a set of operations on it; behaviour, not storage
- stack: add and remove at the top, LIFO, push and pop · queue: add at the rear, remove at the front, FIFO, enqueue and dequeue
- linked list: nodes of value + pointer from a head pointer; cheap insert and delete, slow random access; traverse by following pointers
- justify by rule: order of arrival → queue; most recent first → stack; frequent insertion in the middle → linked list