COMP5112 Chap.3 Stacks, Queues and Expression Processing
Stacks, Queues and Expression Processing
Access order is the abstraction
A stack removes the most recent item, while a queue removes the earliest. This chapter keeps those abstract rules separate from array and linked implementations, then uses them to explain postfix evaluation, infix conversion and circular queues.
Every trace labels the active end or ends, checks underflow and overflow before changing state, and distinguishes physical array position from logical queue order after wraparound.
A stack promises last-in, first-out behaviour through push, pop and top operations. Its representation may use an array with a top index or linked nodes with a head reference, but clients should reason from the abstract order.
An array implementation must define whether top names the occupied position or the next free slot. A linked implementation must decide how an empty head is represented. State the convention before tracing so each update has one interpretation.
Postfix evaluation makes operand order visible. Scan tokens left to right, pushing numeric operands.
When an operator appears, pop the right operand first and the left operand second, apply the operator, and push the result. Reversing those roles changes subtraction and division while leaving addition and multiplication deceptively correct.
A valid expression finishes with exactly one stack value; premature underflow or several remaining values signals malformed input under the stated grammar.
Infix-to-postfix conversion uses a stack for deferred operators rather than numeric results. Operands move directly to output. An incoming operator pops earlier operators according to precedence and associativity, then waits on the stack.
Parentheses create a boundary: the left parenthesis is stored but never emitted, and the matching right parenthesis releases operators until that marker is removed. Keeping conversion and evaluation traces separate prevents their different stack contents from being confused.
A queue promises first-in, first-out behaviour. Enqueue adds at the rear and dequeue removes at the front.
In a simple array, repeated removal can waste positions if elements are not shifted. A circular queue reuses storage by advancing indices modulo capacity. Physical positions may wrap from the final array slot to zero, while logical order still begins at front and follows the occupied sequence.
Draw both index values and logical contents after every operation.
Circular implementations need an unambiguous empty and full convention. Reserving one unused array slot distinguishes the two states using front and rear alone but sacrifices one storage position. Keeping an explicit size allows every position to hold data but adds a field that must change exactly once on successful operations.
Never combine the full test from one convention with the index updates of another. Record capacity, current size and pointer meanings above a trace.
Failure behaviour belongs to the data-type contract. Popping an empty stack, dequeuing an empty queue, or enqueuing beyond fixed capacity must be detected before state changes.
The operation may raise an error, return a distinguished result, or be disallowed by the problem statement. Whatever policy applies, the representation must remain unchanged after failure. This postcondition prevents one invalid action from corrupting every later step in a longer trace.
What this chapter covers
- 01
Stack LIFO operations
- 02
Queue FIFO operations
- 03
Array stack state
- 04
Circular-array queue indices
- 05
Postfix evaluation
- 06
Infix-to-postfix conversion
Worked example · free
Evaluate postfix with a stack
- 2Push operands and apply multiplication.
- 2Apply addition with correct pop order.
- 3Apply subtraction and check final state.
Key terms
- Stack
- A last-in, first-out abstract data type.
- Queue
- A first-in, first-out abstract data type.
- Circular Array
- An array interpretation in which the position after the final index is index zero.
- Postfix Notation
- An expression form placing each operator after its operands.
Stacks, Queues and Expression Processing FAQ
Why does postfix notation not need parentheses?
The operator appears only after the operands it consumes, so a stack trace determines evaluation order without precedence punctuation. A valid expression also leaves exactly one final value after all tokens.
Why use a circular array for a queue?
It reuses positions freed near the front without shifting every remaining item. Front and rear wrap modulo the capacity while logical order remains unchanged across the physical array boundary.
How do I distinguish stack and queue questions quickly?
Ask which pending item must leave next. Reverse completion order indicates a stack; preservation of arrival order indicates a queue, regardless of whether arrays or linked nodes implement it.
Exam move
Draw the stack vertically with a fixed top and the queue horizontally with front and rear labels. For expressions, classify every token before applying an operation. Practise postfix cases containing subtraction and division so operand direction cannot hide behind commutative operators. For circular queues, record the array, front, rear, size and logical order after every step.
Include failed operations and verify that the representation remains unchanged when underflow or overflow is reported.
Working through Stacks, Queues and Expression Processing in COMP5112? Sia is AskSia’s AI Computer Science tutor — ask any COMP5112 Stacks, Queues and Expression Processing question and get a clear, step-by-step explanation grounded in how COMP5112 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
