Programming – Pascal: Essential skills 7

Learning Outcomes:

• Construct lists, stacks and queues in terms of arrays.
• Students should be able to create and manipulate linear linked lists, stacks and queues in terms of arrays.

 

Data structure - Queue

 

Features of a queue:

• First-in-first-out i.e. moving an item can only be from the front(head) and adding an item can only be to the end(tail).

A queue represented by an array:

• Inconvenient to move every items forward when first item is removed. Pointers are used to represent the head and tail positions. I.e. head pointer moves to next location when first item is removed.
• When more and more items are added and removed from the queue, the tail pointer reaches the end of the array. In order to fully utilize the array, the tail pointer move to the first position of the array for the queue to continue. In this way, the array is analogous to a circular array.
• The queue size is limited by the size of the array.

 

One of the way to implement a queue:

var                 queue : array[0..2] of string;       (* array with 3 slots *)                 head, tail : integer; begin head := 0; tail := 0;                (* when head = tail, queue is empty *)                 …

 

	head = 0		head = 1		head = 2
Size of of the queue	head	tail	head	tail	head	tail
0	0	0	1	1	2	2
1	0	1	1	2	2	0
2	0	2	1	0	2	1
3	0	0 (3 mod 3)	1	1	2	2

 

Two ways to handle a ‘full’ array

1. Use a counter to count the number of items in the queue. So even head = tail, we know the queue is not empty as counted by counter. (max number in the queue is 3)
2. Avoid filling up the array. I.e. avoid the situation of head = tail when the queue is not empty. (max number in the queue is 2)

 

Relevant past paper:

DSE ICT Elect B(SP-2017):  2014 1cii,iii,d.

Programming – Pascal: Essential skills 6

 Programming – Pascal: Essential skills 6

 

Learning Outcomes:

• Implement parameters passing in manipulating sub-programs.
• The sub-programs are called by two parameters passing methods: call by value and call by reference.

  

Call-by-value/Call-by-reference

 

When using procedure or function, parameters may be passed into the called procedure / function. The original parameters may or may not be affected depending on call-by-value or call-by-reference.

 

Call-by-value:

var                 x, y : integer;      (* global variables *)                 procedure add (a, b : integer);    (* a and b have their own memory address *) begin                 a := a + 1;                 b := b + 1;                 write (a+b) end;   begin                 x := 1;                 y := 2;                 add (x, y);            (* the use of this procedure does NOT affect the  value of x and y *)                 write (x + y) end.

Output: 53

 

Call-by-reference:

(the only difference from the program above is the var in the procedure heading)

var                 x, y : integer;      (* global variables *)                 procedure add (var a, b : integer);             (* a and b uses the memory address of x and y *) begin                 a := a + 1;             (* x is now 2 *)                 b := b + 1;            (* y is now 3 *)                 write (a+b) end;   begin                 x := 1;                 y := 2;                 add (x, y);            (* the use of this procedure AFFECTS the values of x and y *)                 write (x + y) end.

Output: 55

 

Procedure and function

While a procedure is a subprogram which is quite similar to a usual program (see above), a function always returns a single result.

 

Procedure:

procedure add (a, b : integer); …

 

Function:

function add (a, b : integer) : integer; …

Having the extra part (: integer), it means this function is going to return an integer when called.

 

var                 x, y, sum : integer;   function add (a, b : integer) : integer; begin                 add := a + b end;   begin                 x := 1;                 y := 2;                 sum := add (x, y);              (* similar to using a built-in function *)                 write (sum) end.

Output: 3

 

You can use call-by value or call-by-reference when using functions depending on the purposes of the function / program.

 

Relevant past paper:

DSE ICT Elect B(SP-2017): SP 3d. PP 3a-d. 2012 3ac, 4ai.

CE CIT Elect A(2005-2011): 2009 4bii,iii.