| 摘要 |
The invention relates to a method for implementing a queue, particularly a FIFO queue, in a memory (MEM) and to a memory arrangement. In order to enable reducing the amount of copying particularly in a functional environment, at least part of the queue is formed with a tree-shaped data structure (A, B) known per se, having nodes at several different hierarchy levels, wherein an individual node can be (i) an internal node (N1-N3) containing at least one pointer pointing to a node lower in the tree-shaped hierarchy or (ii) a leaf node (N4-N6) containing at least one pointer to a data unit (1...6) stored in the memory or at least one data unit. A given maximum number of pointers that an individual node can contain is defined for the nodes. The additions to be made to said part are directed in the tree-shaped data structure to the first non-full node (N4), seen from below, on a predetermined first edge of the data structure and they are further implemented in such a way that the leaf nodes remain at the same hierarchy level of the tree-shaped data structure, wherein when a non-full node is not present, new nodes are created to maintain the leaf nodes at the same hierarchy level. The deletions to be made from said part are typically directed to the leaf node on the opposite edge of the tree.
|
