Constant Time Stack_Copy_To extension
Advisor(s): Dr. Bruce Weide,
Dr. Paolo Bucci
Participants: Jason Lesh,
Matt Forsythe
Start Date: Winter Quarter 1999
Project Status: Active
Index:
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:
Return to Europa
<Jason
Lesh>
<Matt Forsythe>
Last modified: Tue Mar 16 23:47:48 EST 1999