Stacks

Overview

Recall questions on stacks and LIFO, push and pop algorithms, the complexity of push, pop and peek, tracing stack operations, overflow and underflow, static and dynamic stacks, subroutine returns, reversing words and bracket matching.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is a stack, and what does LIFO mean?

   Model answer

   A stack is a data structure in which items are added and removed only at one end, called the top. LIFO stands for last in, first out: the most recently added item is always the first one removed, like a pile of plates where you can only take the top plate.

2. 2

   Describe the algorithm for pushing an item onto a stack.

   Model answer

   First check whether the stack is full, that is whether the stack pointer has reached the maximum index; if it has, report overflow and stop. Otherwise increase the stack pointer by one and store the new item at that position. The pointer now identifies the new top item.

3. 3

   Describe the algorithm for popping an item from a stack.

   Model answer

   First check whether the stack is empty, usually by testing whether the stack pointer is minus one or zero depending on the convention; if it is, report underflow and stop. Otherwise read the item at the position given by the stack pointer, decrease the stack pointer by one, and return the item read.

4. 4

   What is the time complexity of push, pop and peek on a stack, and why is it the same for all three?

   Model answer

   All three are O(1), constant time, regardless of how many items the stack holds. Each operation touches only the stack pointer and the one location it addresses: push increments the pointer and writes at it, pop reads at the pointer and then decrements it, and peek reads at the pointer without changing it. Nothing has to be searched, shifted or copied, so the cost does not grow with the size of the stack. That constant cost is the reason a stack is the structure of choice wherever items must be handled in reverse order at speed, such as the call stack, where the overhead is paid on every subroutine call.

5. 5

   Trace this on an empty stack and state the final contents from bottom to top: push 3, push 7, push 2, pop, push 9, pop, pop.

   Model answer

   Push 3 gives [3]. Push 7 gives [3, 7]. Push 2 gives [3, 7, 2]. Pop returns 2, leaving [3, 7]. Push 9 gives [3, 7, 9]. Pop returns 9, leaving [3, 7]. Pop returns 7, leaving [3]. The final contents are just 3, and the values returned in order were 2, 9, 7.

6. 6

   What are stack overflow and stack underflow?

   Model answer

   Overflow is an attempt to push onto a stack that has no space left, which happens with a static stack of fixed size. Underflow is an attempt to pop or peek when the stack is empty and there is nothing to return. Both must be checked for, otherwise the algorithm reads or writes memory that does not belong to the stack.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.