Week 13 Stacks

Question 1

What kind of data structure is a stack?

Answer 1

LIFO - Last In First Out

Question 2

Describe the push operation for a stack. It must account for any errors that may occur.

Answer 2

1. Check if stack is full.
2. If not, increase pointer by one
3. Store new item at location indicated by pointer

Question 3

Describe the pop operation for a stack. It must account for any errors that may occur.

Answer 3

1. Check if stack is empty
2. If not, decrease pointer by one

Question 4

Explain how a single stack can be used to reverse the order of the items in a queue.

Answer 4

(Until the queue is empty) repeatedly remove / delete (the front item) from the queue and push it on to the stack;

(Until the stack is empty) repeatedly pop items from the stack and add them to the (rear of the) queue;

Question 5

Describe how a single stack could be used to evaluate an RPN expression.

Answer 5

(Starting at LHS of expression) push values/operands on to stack; R. if operators are also pushed onto stack, unless they are immediately popped off the stack

Each time operator reached pop top two values off stack (and apply operator to them) // Each time operator reached pop required number of values off stack (and apply operator to them);

Push result (of applying operator) to stack;

When end of expression is reached the top item of the stack is the result // when end of expression is reached pop one value off the stack;