An applicative random-access stack (Q1062446)

In this article, applicative algorithms for a random-access stack (RA- stack) are presented. An RA-stack is a stack data abstraction in which one is further permitted to access the kth element of a stack. The approach uses a singly-linked list representation which is augmented with auxiliary pointers that permit the access of arbitrary stack elements in O(lg N) time were N is the size of the stack. The auxiliary linking structure is based on a number representation scheme for which subtraction by one involves at most one carry operation.