Stacks, postfix evaluation and circular queues

By UK A Level Computer Science · independent study · myAudience

Original conceptual plate generated with OpenAI imagegen; inspected in scratch production. · Generated original teaching artwork; pending operator rights/provenance review before publication.

Stacks, postfix evaluation and circular queues

An abstract data type specifies permitted operations and their behaviour without choosing a storage representation. A stack is last-in first-out: push adds the next top item and pop removes that item. A queue is first-in first-out: enqueue adds at the rear and dequeue removes the oldest outstanding item. These are logical ordering rules. A Python list, linked nodes or a fixed array can implement them with different costs. A data structure is the concrete representation supporting the abstract operations.

Reverse Polish notation writes an operator after its operands, so brackets are unnecessary when operator arity is known. For 8 3 − 2 ×, push 8 then 3; subtract the right operand 3 from the left operand 8; push 5; push 2; multiply to obtain 10. Order matters for subtraction. A stack evaluator must check that each binary operator has two available operands and that one result remains at the end. Rejecting malformed tokens is part of correctness, not an optional inconvenience. The supplied integer evaluator supports only +, − and × and is not a general language interpreter.

For a circular queue of capacity c, head denotes the next item to remove and tail the next free insertion slot. Both advance modulo c. A count in [0,c] distinguishes full from empty, because head==tail occurs in both states under this convention. put checks count==c before storing; get checks count==0 before reading. None marks cleared storage for illustration, but count is the authoritative occupancy measure, so None may still be a valid queued item. Exam questions can use different pointer conventions; state yours before tracing.

The selected circular-queue plate shows a five-slot array initially containing A,B,C at indices 0,1,2 with head=0,tail=3,count=3. Removing A and B leaves C at index 2. Adding D,E,F writes positions 3,4,0 and leaves head=2,tail=1,count=4. Thus physical storage [F,empty,C,D,E] represents logical order C,D,E,F. The wrapping index is not a change in FIFO priority. Every label in the plate corresponds to the supplied RingQueue implementation and independently checked operation trace.

With a fixed-capacity array, enqueue and dequeue use a constant number of index operations, giving O(1) time in the unit-cost model and Θ(c) reserved storage. Removing the first element of an ordinary array-backed list may require shifting many elements, giving O(n) time. A priority queue chooses by priority instead of arrival order, and therefore requires a different behavioural contract. The present lesson establishes stacks and circular FIFO queues; linear queue variants, priority representations and every static/dynamic tradeoff remain further assessed work.

Runnable original Python 3, independently executed on Python the related topic. Read the stated input contract before running. These examples use fictional data and are teaching models, not production services.

```python
def rpn(tokens):
"""Evaluate integer postfix +,-,*; reject malformed expressions."""
stack = []
for token in tokens:
if token in ('+', '-', '*'):
if len(stack) < 2:
raise ValueError('missing operands')
right, left = stack.pop(), stack.pop()
stack.append({'+': lambda: left + right,
'-': lambda: left - right,
'*': lambda: left * right}[token]())
else:
stack.append(int(token))
if len(stack) != 1:
raise ValueError('one result required')
return stack[0]

class RingQueue:
"""Fixed positive capacity FIFO; count disambiguates full from empty."""
def __init__(self, capacity):
if type(capacity) is not int or capacity <= 0:
raise ValueError('positive integer capacity required')
self.data = [None] * capacity
self.head = self.tail = self.count = 0

def put(self, item):
if self.count == len(self.data):
raise OverflowError('full')
self.data[self.tail] = item
self.tail = (self.tail + 1) % len(self.data)
self.count += 1

def get(self):
if self.count == 0:
raise IndexError('empty')
item = self.data[self.head]
self.data[self.head] = None
self.head = (self.head + 1) % len(self.data)
self.count -= 1
return item

def logical(self):
return [self.data[(self.head + i) % len(self.data)]
for i in range(self.count)]
```

Worked example: Evaluate 8 3 − 2 × and reproduce the queue plate’s sequence from an empty five-slot queue.

RPN stack contents after tokens: [8], [8,3], [5], [5,2], [10].

Enqueue A,B,C; dequeue twice to obtain A,B; enqueue D,E,F. Modulo-five updates send the final insertion to index 0.

Physical array is [F,None,C,D,E], head=2,tail=1,count=4; logical() gives [C,D,E,F].

Answer: RPN result=10; queue removal order remains C,D,E,F.

Check your understanding: 1. Evaluate 3 8 −. 2. Why is head==tail ambiguous? 3. After the pictured state, enqueue G and attempt to enqueue H. Give pointers, count, removal order and failure behaviour.

Answer: 1. −5 because the earlier operand is the left operand. 2. Both zero and c outstanding items make tail congruent to head. 3. G occupies index 1; head=2,tail=2,count=5. The order is C,D,E,F,G. H raises OverflowError before any state change because the queue is full. Checking count avoids overwriting C.

Why: A stack reverses retrieval order; a queue preserves arrival order. Pointer equality alone is not a sufficient fullness test here. Reversing popped operands changes noncommutative operators. A queue image must be read from head through count positions, not left to right across physical storage.