A-Level Computer Science / Unit 10: Organising Data in Programs

10.4.2 Stacks: Push, Pop and LIFO

🔒 Lesson slides are available to signed-in users. Sign in

10.4.2 Stacks: Push, Pop and LIFO

A stack stores items in a controlled order. New items are placed at one end, called the top, and removals also take place from that same end. This produces last in, first out behaviour.

This page focuses on stack behaviour, stack operations and choosing a stack for a suitable problem. The detailed array representation and pointer tracing are developed later in 10.4.5 Implementing ADTs with Arrays.

By the end of this section, you should be able to:

  • Describe a stack as an Abstract Data Type with access at the top.
  • Explain the meaning of last in, first out (LIFO).
  • Apply push, pop and peek operations to a stack.
  • Trace a sequence of stack operations accurately.
  • Recognise stack underflow and overflow in a fixed-capacity implementation.
  • Explain the limitations of editing an item below the top.
  • Justify the use of a stack for a given situation.
Syllabus scope: students should be able to use a stack to add, inspect, edit and remove data, and explain why the structure is suitable. Writing implementation pseudocode for the stack is not required.

The Stack Rule

A stack exposes only one active end. The item currently at the top is the next item that can be inspected or removed. Any item below it remains blocked until the items above have been removed.

LIFO: last in, first out. The newest item added is the first item removed.
Top
Checkpoint D
Checkpoint C
Checkpoint B
Checkpoint A
Base

In this example, Checkpoint D was added last. It is therefore the next item that a pop operation would remove.

Common misconception: a stack does not normally remove an item from the base or middle. Doing so would break its LIFO access rule.

Push, Pop and Peek

Operation Purpose Effect on the stack
Push Add a new item. The new item becomes the top item.
Pop Remove and return the top item. The item below becomes the new top.
Peek Inspect the top item without removing it. The contents and order remain unchanged.
IsEmpty Test whether the stack contains no items. Returns a Boolean result.
IsFull Test whether a fixed-capacity stack has no free slot. Returns a Boolean result.
Exam tip: distinguish peek from pop. Both access the top item, but only pop removes it.

Tracing a Sequence of Operations

Start with an empty stack and apply the following operations: 

PUSH "Map"
PUSH "Messages"
PUSH "Camera"
POP
PUSH "Calendar"
PEEK
Step Operation Stack from base to top Value returned
1 Push Map Map —
2 Push Messages Map, Messages —
3 Push Camera Map, Messages, Camera —
4 Pop Map, Messages Camera
5 Push Calendar Map, Messages, Calendar —
6 Peek Map, Messages, Calendar Calendar
After the final step, Calendar remains on the stack because peek does not remove the item.
When tracing a stack, write its contents consistently from base to top or from top to base, and label the order you use.

Empty and Full Stacks

A stack operation must respect the current state of the structure.

Condition Meaning Unsafe operation Resulting problem
Empty stack No item is available at the top. Pop or peek Underflow
Full fixed-capacity stack No unused storage slot remains. Push Overflow
Stack underflow: attempting to remove or inspect an item when the stack is empty.
Stack overflow: attempting to push an item when a fixed-capacity stack is full.
Overflow here refers to exceeding the stack's available capacity. It is different from arithmetic overflow in binary calculations.

Editing Data in a Stack

The top item can be inspected, removed or replaced directly. An item deeper in the stack is not immediately accessible because newer items are above it.

Requested change Possible directly? Explanation
Replace the top item Yes Pop the current top, then push the replacement.
Inspect the top item Yes Use peek.
Edit an item below the top Not directly Items above it must first be removed and later restored.
Delete an item from the middle Not directly A stack exposes only its top item.
A stack is a poor choice when a program frequently needs arbitrary access to items in the middle. A different structure may suit that requirement better.

When Is a Stack Suitable?

Choose a stack when the most recently stored item must be processed before earlier items.

Situation Why a stack fits
Undo actions in a drawing editor The newest action must be reversed first.
Browser Back history The most recently visited earlier page is returned to first.
Checking nested brackets The newest unmatched opening bracket must be matched first.
Depth-first exploration The most recently discovered unfinished route is resumed first.
Tracking nested function calls The most recently called unfinished function must return first.
Strong justification: “A stack is suitable because the most recently stored action must be removed first, matching LIFO behaviour.”
Weak justification: “A stack is suitable because it stores actions.” Many structures store actions; the important reason is the required removal order.

Implementation Preview

A stack may be implemented using a one-dimensional array and a variable that identifies the current top position. A fixed-size array also gives the stack a maximum capacity.

The array stores the values. A top pointer or top index records which stored item is currently at the top.

Detailed pointer values, array states, empty-stack conventions and array-based push/pop traces belong to 10.4.5 Implementing ADTs with Arrays.

On this page, concentrate on what push and pop do. In 10.4.5, concentrate on how an array and pointer make those operations work.

Interactive: Stack Operations Lab

Enter a value or load a preset sequence. Use push, pop and peek to observe LIFO behaviour. The lab also demonstrates underflow and overflow in a five-item stack.

Stack capacity: 5 3 items
Base
Current state
Top item Panel D
Is empty? FALSE
Is full? FALSE
Last returned None
The top item is Panel D. Push adds above it; pop removes it.
Operation history

    Common Mistakes and Misconceptions

    • Confusing LIFO with FIFO.
    • Removing an item from the base rather than the top.
    • Saying that peek removes the item.
    • Forgetting that pop both returns and removes the top item.
    • Trying to pop or peek an empty stack.
    • Trying to push into a full fixed-capacity stack.
    • Assuming that an item in the middle can be edited directly.
    • Giving array pointer details when the question asks only for stack behaviour.
    • Justifying a stack without mentioning the required LIFO order.

    Practice

    Task 1: Basic trace

    Start with an empty stack and apply: PUSH 18, PUSH 42, PUSH 27, POP, PUSH 63.

    1. State the final stack from base to top.
    2. State the value returned by the pop.
    3. State the final top item.

    Task 2: Peek or pop?

    A program must display the newest notification without deleting it. Name the required operation and explain why.

    Task 3: Identify the error

    A student says: “After pushing A, B and C, the first pop returns A because A entered first.” Explain the error.

    Task 4: Choose and justify

    Decide whether a stack is suitable for each situation.

    1. Reversing the most recent command first.
    2. Serving customers in arrival order.
    3. Matching nested HTML tags.
    4. Editing any item in a long sequence directly by position.

    Task 5: Underflow and overflow

    A fixed-capacity stack can store four values.

    1. What happens if pop is requested when it is empty?
    2. What happens if push is requested when it already contains four values?
    3. Name both error conditions.

    Review

    Question Strong answer should include
    How does a stack organise access? Items are added and removed at the top.
    What does LIFO mean? The most recently added item is removed first.
    What does push do? Adds a new item at the top.
    What does pop do? Removes and returns the top item.
    What does peek do? Returns or inspects the top item without removing it.
    What causes underflow? Trying to pop or peek an empty stack.
    What causes overflow? Trying to push into a full fixed-capacity stack.
    How should a stack choice be justified? By explaining that the newest item must be accessed or removed first.
    Final exam tip: connect the operation to the order: push adds at the top, pop removes from the top, and this creates LIFO behaviour.