A Queue Abstract Data type (ADT) has these associated operations:
– Create queue
– Add item to queue
– Remove item from queue
The queue ADT is to be implemented as a linked list of nodes.
Each node consists of data and a pointer to the next node.
a) The following operations are carried out:

Copy the diagram and add appropriate labels to show the final state of the queue. Use the space on the left as a workspace.
Show your final answer in the node shapes on the right.

b) Using pseudocode, a record type, Node, is declared as follows:

The statement

Reserves space for 10 nodes in array Queue.

i) The CreateQueue operation links all nodes and initialises the three pointers that need to be used: HeadPointer, TailPointer and FreePointer.
Copy and complete the diagram to show the value of all pointers after CreateQueue has been executed.

ii) The algorithm for adding a name to the queue is written, using pseudocode, as a procedure with the header:

Where NewName is the new name to be added to the queue.
The procedure uses the variables as shown in the identifier table.

Copy and complete the pseudocode for the procedure RemoveName.
Use the variables listed in the identifier table.

Transcribed Image Text:

CreateQueue AddName ("Ali") AddName ("Jack") AddName ("Ben") AddName ("Ahmed") RemoveName AddName ("Jatinder") RemoveName