A central topic of Data Structures is the concept of an Abstract Data Type. Unfortunately, lectures on ADTs tend to themselves be a bit too abstract to generate the appropriate student enthusiasm. Nothing kindles interest in the subject more than actually implementing such structures, but the examples used should be more exciting than the shopworm cliches of Stack and Queue, for most students have already done exercises with these data types and see nothing useful in making something abstract out of something concrete, or, as one student put it, "making something simple really difficult." This problem disappears when a novel ATD is used, one for which students have no a priori implementation biases. An ADT that works well for this purpose is the BLOCK PILE, a data structure somewhat like a stack that imitates the way children stack and unstack letter blocks to make a pyramid. A full description of this ADT is given in the assignment below. The important point here is that students are challenged to think creatively about possible implementations. It is gratifying also to see that usually three or four quite different implementation choices are made. The differences in implementation become the subject of subsequent lectures and class discussion. Questions of efficiency, speed, storage, and coherency become concrete and heated as each student defends his or her particular implementation choice.
Your assignment is to implement the abstract data type BLOCK PILE. Its real-world inspiration is a child's pyramid of letter blocks. The child strives to stack each new block as near to the top of the pyramid as possible. The following illustration shows the resulting block pile after stacking six blocks in the order A through F.
We imagine the child removes the blocks from top to bottom, right to left. The six blocks above would be unstacked in the order
The structure is reminiscent of a stack, but clearly is not a FIFO ordering. This ADT is bounded by a preset MAXLEVEL. A MAXLEVEL of 10, for example, would allow the BLOCK PILE to hold 55 blocks according to the formula
An unbounded version of this ADT would set no limit on the number of blocks stacked and would not require the operator IS FULL. Your assignment is to build the implementation module BLOCKS.MOD for the ADT BLOCK PILE described above. Your operators are formally described in the following definition module BLOCKS.DEF, which you will use as your guide. When you have completed the module, your instructor will test your work by linking your files to a diagram. Hopefully we will be able to stack and unstack blocks to our hearts' content!
DEFINITION MODULE BLOCKS;
EXPORT QUALIFIED BLOCK_PILE, CREATE_BLOCK_PILE, CLEAR,
STACK, TOP_BLOCK, UNSTACK, IS EMPTY,
IS_FULL;
TYPE
BLOCK_PILE: (* Opaque type *)
PROCEDURE CREATE_BLOCK_PILE( VAR BP : BLOCK PILE );
(* POST: Created(BP) *)
PROCEDURE CLEAR( VAR BP : BLOCK PILE );
(* PRE: Created(BP) *)
(* POST: num_blocks(BP) *)
PROCEDURE STACK( BLOCK : CHAR; VAR BP : BLOCK_PILE );
(* PRE: Assigned(BLOCK) & NOT full(BP) *)
(* POST: BP = BP + BLOCK added at highest *)
(* possible level *)
PROCEDURE TOP_BLOCK( VAR BP : BLOCK_PILE ) : CHAR;
(* PRE: num_blocks(BP) >= 1 *)
(* POST: RESULT = name of rightmost block on *)
(* top level *)
PROCEDURE UNSTACK( VAR BP : BLOCK_PILE );
(* PRE: num_blocks(BP) >= 1 *)
(* POST: BP = BP - rightmost block on top level *)
PROCEDURE IS_EMPTY( VAR BP : BLOCK_PILE ) : BOOLEAN;
(* PRE: Created(BP) *)
(* POST: if num_block(BP) = 0 *)
(* then return TRUE *)
(* else return FALSE *)
PROCEDURE IS_FULL( VAR BP : BLOCK_PILE ) : BOOLEAN;
(* POST: RESULT = (level(BP) = maxlevel ) *)
END BLOCKS.
DISCUSSION
For the curious, it seems that the most efficient and straightforward implementation of this ADT is an array of stacks, each stack representing one level of the block pile. New blocks are pushed onto the highest-level stack in which insertions are allowed. Blocks are unstacked by emptying the stacks from the top stack down. Most students who discovered this implementation opted for linked list stacks and an array of stack headers, each header including a count field for the number of blocks in the stack. The least elegant solution involved having each block represented by a node with six pointer fields linking it to all its possible neighbors. Although this implementation was made to work, its shortcomings became clearly obvious during subsequent class discussion. The practicality of abstract data types was driven home when the same driver program worked successfully on each of the very different implementations with no "code fiddling."