Абстрактные типы данных — стек, очередь, связный список

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.

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

Worked example: trace the stack

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

Worked example: describe adding to and removing from a queue

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

Worked example: add a node in order

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.

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

You've got it