On the Design and Performance Analysis of Dynamic Stack Systems


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 2, No. 3, pp. 364-373, Apr. 1995
10.3745/KIPSTE.1995.2.3.364,   PDF Download:

Abstract

We propose a probabilistic design method and performance analysis in the area of dynamic data structures. We assign two stacks to a block which consists of m contiguous memory cells. Frequencies of delete and insert operations are not fixed, but depend on stack heights. We present various probabilistic schema and a rigorous performance analysis for a random memory allocation. Especially, stack coillision problem is studied and exponential increase of the mean of collision time as m->%u221Eis showed. We also present general mathematical schema which can be applied to the performance problems of finite automata and other computer information systems.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
C. C. Bong, "On the Design and Performance Analysis of Dynamic Stack Systems," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 2, no. 3, pp. 364-373, 1995. DOI: 10.3745/KIPSTE.1995.2.3.364.

[ACM Style]
Chung Chy Bong. 1995. On the Design and Performance Analysis of Dynamic Stack Systems. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 2, 3, (1995), 364-373. DOI: 10.3745/KIPSTE.1995.2.3.364.