Algorithms and Data Structures 2020

Week 13. Memory


14.2 Exercises

Problem 14.3 Describe an external-memory data structure to implement the stack ADT so that the total number of disk transfers needed to process a sequence of k push and pop operations is O(kB), where B is the block size, i.e. number of elements fitting in a block.