An applicative random-access stack

DOI10.1016/0020-0190(83)90106-0MaRDI QIDQ1062446zbMATH OpenOpenAlexFDO

Authors Eugene W. Myers

Publication date 1983

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(83)90106-0

zbMATH Keywords

applicative algorithms for a random-access stackapplicative programmingsingly- linked list representationskew-binary number systemstack data abstraction

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• A scalable lock-free stack algorithm
• A bidirectional multiple stack algorithm
• Random access machines with multi-dimensional memories
• scientific article; zbMATH DE number 3900130
• Space-time trade-offs for stack-based algorithms
• Space-time trade-offs for stack-based algorithms
• Delay analysis of the n-ary stack random-access algorithm

Cites work

• Can programming be liberated from the von Neumann style?
• Combining Algebraic and Algorithmic Reasoning: An Approach to the Schorr-Waite Algorithm
• scientific article; zbMATH DE number 3635458 (Why is no real title available?)
• Symmetric list processor

Cited in

(7)

• Making data structures persistent
• A parallel algorithm for finding a blocking flow in an acyclic network
• Regular numeral systems for data structures
• Optimal purely functional priority queues
• An overview of Edison
• Priority queues with decreasing keys
• Two skew-binary numeral systems and one application

This page was built for publication: An applicative random-access stack

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1062446)