Constant Time Stack_Copy_To extension

Index:

Abstract
Calendar
Project Development
Findings and Contributions
Links and References
Return to Europa

Abstract:

Implementation of new Stack_Kernel with the following member functions, all of which operate in constant time:


• Constructor
  
• Destructor
  
• Push
  
• Pop
  
• Length
  
• Copy_To
  

Calendar:

This project was begun winter quarter 1999. Currently, the design is completed, and implementation is underway.

Project Development:

The basic idea behind copying a stack in constant time is to only copy the top node and make a new top_of_stack pointer to point to the copied node. Then when you pop a node off of the copied stack, you make a copy of the next node and move the stack pointer. The only problem we ran into was getting the destructor to work in constant time. We did not realize there was a problem until we presented our algorithm to the group. The final idea we ended up using for the destructor was to keep a linked list of the destructed stacks and recycle the destructed nodes instead of creating new ones with Push.

Findings and Contributions:

One interesting thing about this project is that the same algorithm will work for binary tree. This is slightly more interesting than stack because binary tree can then be used to implement partial map, set, or sequence. This would mean that you could use the constant time copy function to make a backup of a database, for example if you wanted to implement something like an "undo" command. We may continue in this direction in a future project.

Links and References:

Stack Component as implemented in the RESOLVE Catalog

  Return to Europa