|
(a) Describe informally what is meant
by a stack abstract data type. [2 marks]
(b) Given the following definition of
a stack abstract data type, and the functions and procedures which
operate on it:
TYPE
StackType= ˆStackElement;
StackElement= RECORD
next : StackType;
data : INTEGER;
END;
FUNCTION IsEmpty(stack : StackType) : BOOLEAN;
FUNCTION Pop(VAR stack : StackType) : StackElement;
PROCEDURE Push(VAR stack : StackType; a : StackElement);
(i) Explain, with reference to the above examples, the difference
between a function and a procedure. [1 mark]
(ii) Explain why the parameter stack is declared as a VAR parameter
in the procedure Push. [1 mark]
(iii) Explain why the parameter stack is not declared as a VAR parameter
in the function IsEmpty. [1 mark]
(c) (i) Implement the function Inspect,
the signature of which is given below, which takes a stack s and an
element e, and returns the position of the first occurrence of e in
the stack, and the depth of the stack should e not occur in the stack.
The function should not attempt to remove e from the stack.
FUNCTION Inspect(s: StackType; e: INTEGER) : INTEGER; [5 marks]
(ii) Implement the procedure SplitStack, which takes three stacks
a, b, and c as
reference parameters. The procedure should iterate through the stack
a, such that on each odd iteration it removes the item from a and
adds it to b, and on each even iteration it removes the item from
a and adds it to c, until a is empty. On
termination of the procedure, a should be returned empty. [5 marks]
|