配列を用いたADTの実装

There is no such thing as a stack in memory

• Open a computer and look for the stack. You will not find one. Memory is one enormous array of numbered cells, and that is all there is.
• Every stack, every queue, every linked list is that array plus two or three integer variables that remember where things are. Push is "add one to a number and store"; dequeue is "read a cell and add one to a different number".
• The whole of this lesson is bookkeeping: which pointers, which checks, and what happens at the edges.
• The exam asks you to describe the declarations, walk the pointers through a few operations, and say why the checks are there.

A stack in an array

• Hold the items in Stack[1:MaxSize] with an integer Top, 0 when the stack is empty.
• Push(x): if Top = MaxSize the stack is full, an overflow 溢出; otherwise Top ← Top + 1 and Stack[Top] ← x.
• Pop(): if Top = 0 the stack is empty, an underflow 下溢; otherwise return Stack[Top] and Top ← Top − 1.

The array never moves; only Top does

Worked example: declare and initialise the stack

A queue in a plain array

• Two pointers: Front for the next item to leave, Rear for the next free space. Enqueue stores at Rear and moves it on; dequeue reads at Front and moves it on.
• Both pointers only ever move forward, so after a few operations they march off the end of the array while the cells at the start sit empty and unusable.
• The fix is to let the pointers wrap around.

The circular array

• A circular array 循环数组 wraps a pointer back to the first cell when it passes the last: with 1-based indices, Rear ← (Rear MOD MaxSize) + 1.
• Enqueue(x): check not full; Rear ← (Rear MOD MaxSize) + 1; Queue[Rear] ← x. Dequeue(): check not empty; return Queue[Front]; Front ← (Front MOD MaxSize) + 1.
• Keep a separate count: when the queue is completely full and when it is completely empty the two pointers are in the same relative position, so the pointers alone cannot tell the two apart.

After the last cell comes the first cell

Worked example: walk the pointers

Worked example: the enqueue algorithm in words

A linked list in an array

• Use an array of node records, each with a Next index; -1 marks the end. A Head index marks the first node, -1 if the list is empty.
• The unused slots are chained into a free list 空闲列表 from FreeListHead, exactly as the data list chains its used ones.

TYPE TNode
    DECLARE Value : INTEGER
    DECLARE Next  : INTEGER     // index of the next node, or -1
ENDTYPE
DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER          // -1 when empty
DECLARE FreeListHead : INTEGER  // first unused slot

• Insert: take the slot at FreeListHead, set its Value and Next, then rewire the previous node's Next or Head. Delete: unlink the node and return its slot to the front of the free list.

Two lists share one array: the data list and the free list

Worked example: insert into the array-held list

Marks that slip away

You've got it