2.3.2 Algorithms for the Main Data Structures

Question 1

Describe stacks

Answer 1

A first in last out data structure. They use a single pointer to keep track of the element which is currently at the top of the stack.

Question 2

Why might someone choose to initialise the top pointer of the stack at -1, where the top pointer represents the position of the top item?

Answer 2

The first element in the stack will be stored at position 0. If the pointer was 0, this would imply there is an item in the stack.

Question 3

Name the operations that can be performed on a stack.

Answer 3

size()
isEmpty()
peek()
push(element)
pop()

Question 4

Stacks: Size operation

Answer 4

Returns the number of elements in the stack (top pointer + 1)

Question 5

Stacks: isEmpty operation

Answer 5

Checks if the stack is empty (topPointer = -1)

Question 6

Stacks: peek operation

Answer 6

Returns the item at the top of the stack, after checking if the stack is empty.

Question 7

Stacks: push operation

Answer 7

Adds an item to the top of the stack, by updating the top pointer then inserting the item at the top pointer position. The new item must be passed as a parameter.

Question 8

Stacks: pop operation

Answer 8

Removes the item at the top of the stack, after checking if the stack is empty. The item at the top is recorded before being removed. The top pointer decrements by 1, and the removed item is returned.

Question 9

Describe queues

Answer 9

A type of first in first out data structure. It uses a front and back pointer to hold the position of the first element and the position of the next available space.