Stacks and queues in fixed lists
このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
English
The exam's way: a fixed list and pointers
- In Paper 4, a stack or queue is not built with
appendandpop. The question gives a fixed-size list and integer pointers. - The list is made once, full of empty values:
StackData = [0] * 5. Its length never changes. - A pointer holds an index into that list. Python indexes start at 0, so
-1can mean "no item". - Use the exact identifiers and starting values the question gives. Here:
TopOfStack = -1means the stack is empty.
![Four snapshots of StackData[0] to StackData[4]: empty with TopOfStack -1; after Push(4) and Push(9) TopOfStack is 1; after Push(7) it is 2; Pop() returns 7 and TopOfStack is 1 again](/static/code/a-level-cs/stack-array-py.png)
English
StackData = [0] * 5
TopOfStack = -1
def Push(Item):
global TopOfStack
if TopOfStack == 4:
return False
TopOfStack = TopOfStack + 1
StackData[TopOfStack] = Item
return True
def Pop():
global TopOfStack
if TopOfStack == -1:
return -1
Item = StackData[TopOfStack]
TopOfStack = TopOfStack - 1
return Item
Push(4)
Push(9)
Push(7)
print(Pop(), Pop(), "TopOfStack =", TopOfStack)
- The output is
7 9 TopOfStack = 0.PushreturnsFalsewhen the stack is full, andPopreturns-1when it is empty.
探索
A stack: the last item pushed is the first popped
Push and Pop both use the top of the stack.
English
Why global?
- Inside a function,
TopOfStack = TopOfStack + 1would make a new local variable, and Python stops with anUnboundLocalError. global TopOfStackat the top of the function says: use the variable from the main program.- Changing one element,
StackData[TopOfStack] = Item, works withoutglobal. Mark schemes still writeglobalfor every global the function uses, so do the same.
English
A circular queue in a fixed list
QueueHeadis the index of the first item andQueueTailthe index of the last.NumberInQueuecounts the items.- Enqueue: move
QueueTailon by one, then store. Dequeue: read atQueueHead, then move it on. - "Move on by one" wraps round:
(QueueTail + 1) % 4gives 1, 2, 3, then 0 again. The free cells at the front are reused. - Test for full (
NumberInQueue == 4) before an enqueue and for empty (NumberInQueue == 0) before a dequeue.

English
QueueData = [""] * 4
QueueHead = 0
QueueTail = -1
NumberInQueue = 0
def Enqueue(Item):
global QueueTail, NumberInQueue
if NumberInQueue == 4:
return False
QueueTail = (QueueTail + 1) % 4
QueueData[QueueTail] = Item
NumberInQueue = NumberInQueue + 1
return True
def Dequeue():
global QueueHead, NumberInQueue
if NumberInQueue == 0:
return ""
Item = QueueData[QueueHead]
QueueHead = (QueueHead + 1) % 4
NumberInQueue = NumberInQueue - 1
return Item
for Name in ["Ann", "Ben", "Cat"]:
Enqueue(Name)
print(Dequeue())
Enqueue("Dev")
Enqueue("Eve")
print("Eve is at index", QueueTail)
print(Dequeue())
- The output is
Ann, thenEve is at index 0, thenBen.
English
Common mistakes
| Wrong | Right | Why |
|---|---|---|
StackData.append(Item) |
StackData[TopOfStack] = Item |
the list has a fixed size; the pointer chooses the cell |
store, then add 1 to TopOfStack |
add 1, then store | the pointer is the index of the top item |
no global TopOfStack |
global TopOfStack first |
assigning it would make a new local variable |
QueueTail = QueueTail + 1 in a circular queue |
QueueTail = (QueueTail + 1) % 4 |
the tail must wrap from 3 back to 0 |
testing QueueHead == QueueTail for empty |
count with NumberInQueue |
a full queue and an empty one can have the same pointers |
English
Now you try
- Keep the fixed list and the pointers. Write
globalfor every pointer you change. - Press Check answer to test your code.
難易度 3/5 · 200 コイン + 今日初回達成時の小ボーナス
StackData is a fixed list of 3 and TopOfStack starts at -1. Write Push(Item), which returns False when the stack is full and otherwise stores the item and returns True, and Pop(), which returns -1 when the stack is empty and otherwise returns the top item.
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
QueueData is a fixed list of 3 used as a circular queue. QueueHead starts at 0, QueueTail at -1 かつ NumberInQueue at 0. Write Enqueue(Item) (returns False when full, else True) and Dequeue() (returns "" when empty, else the front item).
実行ボタンをクリックして出力を確認してください。