Fun challenge: implement the linear data structure known as "stack" in PL/SQL.
A stack is a totally ordered finite set of values, all of the same data type. In addition to storing those values in whatever way, "stack" must also support the following three operations (methods):
empty (<stack>) - a Boolean function telling us if the stack is empty (no values).
push(<stack>, <value>) - a procedure to add one more value AT THE END of the sequence.
pop(<stack>) - a function that returns the LAST ELEMENT of the stack, and removes it from the stack.
In addition, obviously, we need to be able to create empty stacks as needed.
The challenge is to implement this structure in PL/SQL, as efficiently as possible.
Since PL/SQL doesn't support generic data types (at least I think it doesn't), to fix ideas, let's only consider numeric stacks. That is, the data type of the values stored in the stack is NUMBER.
In theory, there should be no upper limit to the number of elements in a stack ("stack overflow" is always an implementation concept, it shouldn't exist in the ideal world none of us lives in). In practice, there is always at least the physical limit imposed by available resources; we can either implement "stack" with a user-provided max size, and handle "stack overflow" conditions, or write the implementation so that the stack size can grow dynamically (and then still handle "stack overflow" caused by resource exhaustion). I will be happy with either version; in my tests, the latter creates significant drag on performance.
There are (at least) two natural ways to attack this. ("Natural" in my view, which may be wrong.) One is to create a package with the needed type and procedure/function definitions, and the other is to create a stand-alone (schema-level) data type, encapsulating everything within an object's attributes and methods. In my tests, I found that the package approach is more efficient, but perhaps I didn't come up with the best solution (for EITHER approach). For this challenge, use whichever approach you think is best.
The implementation should support the execution of the following anonymous block (which assumes a package approach to the solution; the changes needed for an object type implementation should be trivial). Here DATA_STRUCT is the package name, N_STACK is the type name, etc.
declare
s data_struct.n_stack;
x number;
begin
s := data_struct.new_n_stack(10000000);
for i in 1 .. 10000000 loop
data_struct.push(s, i);
end loop;
while not data_struct.empty(s) loop
x := data_struct.pop(s);
-- dbms_output.put_line(x);
end loop;
end;
/
Notice the NEW_N_STACK function call. That function returns an empty stack with a maximum capacity of 10 million values.
The commented-out PUT_LINE call is for testing (of course, test with ten values or so, not with 10 million). Otherwise the procedure doesn't generate any output; just observe the execution time. Also, while you are developing solutions, you may want to start with fewer values, but the final solution should be able to handle 10 million values in a reasonable amount of time - for example, less than a minute. Note that the block executes each of EMPTY, PUSH and POP 10 million times, and the stack itself gets to be big enough for proper testing; this should suffice for most reasonable applications.
MOTIVATION: A couple of months ago I implemented an algorithm for finding the connected components of a (possibly very large) graph. I compared against the Oracle-provided package for the same, and I found that my implementation was much faster. I wonder what else can be done better. For more complex algorithms, I will need many basic ADT's such as stack, so I decided to start from the bottom. This is the first step.