Aug 1997 AP207: Advanced Programming Techniques (Question 4) Suggested Solutions

4.	(a) Define and explain the properties of a stack abstract data-type. In particular, identify any error conditions that may be raised when manipulating a stack.		[3]
	Properties of a stack.
		A stack is a last-in first-out data structure
		Data is only accessible at the top of the stack
		The items that have been in the stack the longest will be at the bottom (from the study guide).
		it is an error to "pop" an entry from an empty stack
		it is an error to enquire what the top entry of an empty stack is.
	one mark for each point, up to a maximum of three marks
	[3 marks]

	(b) Define appropriate Pascal type and record definitions for a type called StackType, where
		(i) the stack is represented by an array of characters that can only contain a fixed number of characters.	[3]
		(ii) the stack of characters can dynamically grow in size.	[3]
	Operations that form the interface to a stack:
		1. Push: add an element to a stack
		2. Pop: remove top element from the stack
		3. TOS (Top of Stack): return top element from stack without removing it.
		4. NewStack: create an empty stack
		5. DeleteStack: destroy a stack
		6. IsEmpty: check if the stack is empty
		7. IsFull: check if the stack is full (only required for static stacks)
	Procedure Push(Var stack: StackType; element: Integer);
	Procedure Pop(Var stack: StackType);
	Function TOS(stack: StackType): Integer;
	Function NewStack( ): StackType;
	Procedure DeleteStack(Var stack: StackType);
	Function IsEmpty(stack: StackType): Boolean;
	Function IsFull(stack: StackType): Boolean;
	Half a mark should be awarded for each routine if the students just list the routines that form the interface to the stack. One mark should be awarded for each routine if they name the routine, and give its type definition. Award no more than 6 marks. The element type passed to push may be of any type. The students may not define a TOS function, but define push as a function that removes and returns the top element from the stack: Function Pop(Var stack:StackType): Integer;
	[6 marks]

	(c) List, and give the type definitions, for the basic operations that would form an interface to a stack abstract data type.		[6]
	Type definitions for StackType:


		one mark for defining a record type
		one mark if the record type contains an array of stack element types (be it integers, characters, etc.), of a fixed size.
		one mark for having a top stack marker. This may either be an integer that represents the index of the top of stack element in the array, or a pointer to the top of the stack.
		The names of the fields of the record may be different than above. No marks should be deducted for trivial syntactic errors.
	[3 marks]

		one mark for defining a stack type as a pointer to a node type.
		one mark for defining a node type that contains a element type of the stack.
		one mark for defining a node type that contains a next field.
		The names of the fields of the record may be different than above. No marks should be deducted for trivial syntactic errors.
	[3 marks]

	(d) Using the routines you defined as the interface to the stack abstract data type, define a procedure reverse that has the type shown below that takes as its argument a stack of integers, and alter the stack so that the elements that are at the bottom of the stack are moved to the top of the stack, and those at the top move to the bottom.		[5]
	Procedure reverse (Var stack: StackType);
	A definition of reverse is shown below:

	and the following marking scheme should be used:
		one mark for creating a new temporary stack
		one mark for iterating over each element in stack
		one mark for pushing the top element on the stack onto the temporary stack.
		one mark for popping stack. Note: if the students do not define TOS, but define Pop to return and remove the top element from the stack, then give two marks for the statement: Push (tempstack, Pop(stack));
		one mark for assigning the temporary stack to stack.
		No marks should be deducted for trivial syntactic errors.
	[5 marks]