Question
A new parking service has been introduced: staff will park the car for the driver and then return it later when the driver wants to leave. This service will use a narrow parking area surrounded on three sides by walls, where any cars behind the required car must be reversed out. For example, car x00000011 was the first vehicle to be parked, so to remove it from the parking area, the other five cars, starting with x00000123, will need to be removed. The cars are then returned starting with car x00000010.
Figure 5: Cars parked in the parking area
The class Stack, which contains the Vehicle objects, has the following methods:
The method staffRemoveCar will remove a vehicle with a specified registration plate from the parking area (you can assume the vehicle is in the parking area):
public static void staffRemoveCar(Stack stack, String reg){
Stack temp = new Stack();
//add code here
}
a. Construct the staffRemovecar method.[6]
b. A stack can be implemented using an array or a singly linked list. $[4]$
Compare the use of these two data structures for creating a stack.
▶️Answer/Explanation
Ans:
a. )
Award [1] for looping around the main stack using isEmpty() method;
Award [1] for using “while” loop in both loops (note: not a “do while”!);
Award [1] for breaking out of outer loop when car is removed and other cars are replaced;
Award [1] for correctly removing cars before target car is found;
Award [2] for replacing cars in same order by popping off temporary stack;
Example 1:
public void staffRemoveCar (Stack stack, String reg) \{
Stack temp = new Stack();
while (!stack.isEmpty()) \{
Vehicle $\mathrm{v}=$ (Vehicle) stack.pop ();
if (v.getRegistration (). equals(reg)) \{
// correct car is now removed
// return others
while (!temp.isEmpty()) \{
$\quad$ stack.push(temp.pop());
break; // don’t keep repeating
}
temp.push(v);
}
}
Example 2:
public static void staffRemoveCar(Stack<Vehicle> stack, String reg)
{ Stack<Vehicle> temp = new Stack<Vehicle>();
boolean found = false;
while (!found && !stack.isEmpty())
{ Vehicle curr = stack.pop();
found = curr.getRegistration().equals(reg);
if (!found) temp.push(curr);
}
while (!temp.isEmpty()) stack.push(temp.pop());
}
b. )
Award [1] for an initial valid comparison and [1] for a valid expansion.
Memory
Linked lists can deal with memory issues more efficiently than arrays;
Arrays are static so will have a maximum size and cannot grow beyond that;
Memory will be allocated for maximum size at instantiation so while it is not full memory is wasted Links are dynamic and can add/remove memory as required- no memory is wasted;
Implementation
No particular advantage is gained by the use of either structure;
As additions and removals (push and pop) work on one end of the stack, navigation speed (i.e. O1) is not very helpful; Linked lists can adjust the pointer at the end of the list (can use a tail pointer) so slow navigation is not an issue;
Errors
The use of arrays is more likely to lead to run-time errors;
As arrays can reach their maximum limit whilst linked lists are only limited in size by the specifications of the CPU;
Question
A single parking space that holds one car can be used to hold two motorbikes. The programmer has decided to use a two-dimensional array to create a map of the parking area.
Vehicle parkingSpaces[] [] = new vehicle[2] [200];
Note: $m$ and $c$ have been used to show where motorbikes and cars are parked.
Police have requested a way of searching the parking area for vehicles with a specified registration plate, and a binary tree has been suggested.
a.i. Identify one advantage of using a two-dimensional array for this purpose.$[1]$
a.ii.ldentify one disadvantage of using a two-dimensional array for this purpose.$[1]$
b. Outline why searching for the registration plate in a binary tree would be faster than looking for it in the two-dimensional array.$[3]$
c. Identify the steps that would be involved in taking the data from this two-dimensional array and creating a binary search tree. [5]
▶️Answer/Explanation
Ans:
a.i. )
Faster to access (i.e. $\mathrm{O} 1$ instead of On);
Arrays take less memory than lists (as they do not store pointers);
Mirrors real life situation;
a.ii )
Static, therefore memory wasted when not being fully utilised;
Inability to grow, should further spaces be added, i.e. If Parking area grows;
b. )
The array would need to be searched using a linear search which is inefficient $O(n)$ whereas a binary search is much more efficient $O($ log $n)$;
A linear search for a car in this parking area could require a maximum of 200 comparisons (i.e. it would look at the first row of every column) whereas a binary search would only require 8 (i.e. log 200 base 2 );
A linear search for a motorbike in this parking area would require a maximum of 400 comparisons (i.e. it would need to look at both rows of every column) whereas a binary search would only require 7 (log 100 base 2 );
In a binary search, each comparison would eliminate half of the remaining possible matches, whereas in a linear search it only eliminates 1 ;
A binary search has the registration plate as its key and therefore it doesn’t require accessing the field of the vehicle object for each comparison, whereas in a linear search, each comparison would be slower because it would require getting the vehicle object’s registration field using an accessor method;
A binary search is always faster than a linear search on a large data set. As the police may be searching for many cars and in many parking areas, their searches will be on large set of data;
c.)
Create a binary tree to store vehicle objects;
Loop around all of the elements in the 2 dimensional array (e.g. using inner and outer loop);
Skip empty locations;
Take the first vehicle found and add as the head of the binary tree;
Take all subsequent vehicles found and do the following;
Get the node’s vehicle registration;
Find the appropriate insertion point in the binary tree by navigating from the root and comparing the registration to the key of the current node;
When a leaf node is reached compare the registration with the vehicle to be inserted and insert it as the left or right child node, using its registration as the key;
Continue until the end of the vehicle array has been reached;