Stack ADT

Question 1

Array based implementation of stack, what are the main methods?

Answer 1

Push
Pop
Peek
Size
IsEmpty

Question 2

What are the runtimes of the main methods for an array based stack?

Answer 2

Push: theta 1
pop: theta 1
peek: theta 1
size: theta 1
isEmpty: theta 1

Question 3

In a list based implementation of the stack, where is the top?

Answer 3

At the front of the list (new elements added to element 0) as we can insert and delete elements in const time from front only

Question 4

What is the runtime for methods in a list based stack implementations?

Answer 4

All theta 1 (if implemented correctly)