| 摘要 |
The invention relates to a method for implementing a double-ended queue (deque) in a memory (MEM), and to a memory arrangement. To be able to reduce the amount of copying, particularly in functional environments, the double-ended queue is used in the memory as a hierarchic data structure where on the highest level of hierarchy, there is a three-element node of whose elements one points to the buffer forming the front end of the queue and another to the buffer forming the tail end of the queue. The middle of the queue consists of nodes on different levels of hierarchy so that pointing from each level of hierarchy to the next lower level of hierarchy is done by a pointer in the third element of a three-element node. The pointer points to a node on the next lower level of hierarchy which is a similar three-element node, with the exception of the lowest level of hierarchy where the said node can also be a buffer, and with the exception of the highest level of hierarchy, where the said pointer can also be an NIL pointer. Also the pointers in the two predetermined elements of the three-element node in the middle of the queue point to buffers. In the data structure, a buffer on a given level of hierarchy is treated as an element of a buffer on the next lower level of hierarchy. Adding (removing) elements to the queue is done at the buffers forming the front or tail end of the queue. A buffer which becomes full (or empty) in connection with adding (or removing) an element, is moved from one level of hierarchy to another.
|
