Abstract Data Types

Question 1

Advantages of Stack Implementation using Array

Answer 1

1. Simple implementation
2. Constant time: O(1)
3. Better cache locality

Question 2

Disadvantages of Stack Implementation using Array

Answer 2

1. Fixed size with maximum capacity
2. Cost of Resizing: O(n)
3. Wasted memory
4. Not suitable for applications where the size of the stack is not known in advance

Question 3

Advantages of Stack Implementation using Linked List

Answer 3

1. Dynamic size
2. No preallocation
3. Easy resizing: O(1)

Question 4

Disadvantages of Stack Implementation using Linked List

Answer 4

1. Memory overhead due to the storage of pointers
2. Poor cache locality

Question 5

Choice of Stack Implementation

Answer 5

1. If stack size is known -> Array-based
2. If the stack varies dynamically ->linked list
3. If efficient memory access and cache locality -> Array-based