This paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. This problem arises in the implementation of list-based and functional programming languages. A solution is proposed requiring constant time and space for each stack operation except catenation, which requires O1994 time and space. Here k is the number of stack operations done before the catenation. All the resource bounds are amortized over the sequence of operations.
All Science Journal Classification (ASJC) codes
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence
- data structures
- functional programming