Stacks

Overview

Recall questions on stacks and their uses, the stack pointer, creating a static stack, push, pop and peek, overflow and underflow, static and dynamic stacks, tracing operations, and why recursion needs a stack rather than a queue.

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?

   Model answer

   A last in, first out (LIFO) data structure: items are added and removed at the same end, called the top, so the most recently added item is the first one to come off. Only the top item is accessible; you cannot reach an item lower down without removing the ones above it.

2. 2

   Give three real uses of a stack in a computer system.

   Model answer

   Storing return addresses, parameters and local variables when subroutines are called, so that execution can return correctly - this is why recursion needs a stack. Saving the contents of registers when an interrupt occurs so the interrupted program can be resumed. Implementing the undo function in applications and the back button in a browser, and evaluating expressions in reverse Polish notation.

3. 3

   Why does a stack need a pointer, and what does it hold?

   Model answer

   The stack pointer records where the top of the stack currently is, because that is the only position at which pushing and popping happen. A common convention is for it to hold the index of the top item, set to -1 when the stack is empty. Some implementations instead have it point at the next free slot; either is fine as long as you are consistent, because the push and pop steps differ slightly between them.

4. 4

   How do you create an empty static stack?

   Model answer

   Declare an array of the required maximum size to hold the items, and a stack pointer variable. Set the stack pointer to -1 (or to 0 if your convention is that it indexes the next free slot), which marks the stack as empty. Recording the maximum size lets you detect overflow later.

5. 5

   Describe the push operation.

   Model answer

   First check whether the stack is full - if the pointer is already at the maximum index, report overflow and do not proceed. Otherwise increment the stack pointer by one and store the new item at that index. The new item is now the top of the stack, and the item previously on top is untouched underneath it.

6. 6

   Describe the pop operation.

   Model answer

   First check whether the stack is empty - if the pointer is -1, report underflow and do not proceed. Otherwise read the item at the index held in the stack pointer, then decrement the stack pointer by one, and return the item that was read. The data may physically remain in the array, but it is now above the pointer and so is treated as no longer on the stack and will be overwritten by the next push.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.