Logout

Home Topic 5 Last Next

5.1.9

Construct algorithms using the access methods of a queue.

 

Teaching Note:

Access methods:

- enqueue
- dequeue
- isEmpty.

LINK Connecting computational thinking and program design.


 

Sample Question:

sdfsdfsf

JSR Notes:

Firstly, remember that for Topic 5, "Linked lists will be examined at the level of diagrams and descriptions. Students are not expected to construct linked list algorithms using pseudocode", but yes for the OOP Option.

Below is a full movie of stacks and queues (using linked lists, which makes most sense). (This is the same one as in 5.1.7.)

Note that I don't include an isEmpty method in the video. That would test to see if the head was == to null.

And also note that more Java implementation details are expected in the OOP extension later on in the curriculum.

 

And note that the enqueue( ) and isEmpty( ) methods are taken to a much deeper level in the OOP Option Extension later on in D.4.10.

And remember:

In terms of how you choose to implement them, a stack is a stack, or a queue is a queue not because of the end you are working with, but because of the **way** of working with it, either in a LIFO or a FIFO manner - LIFO for stack, and FIFO for queue.

 

Queue Enqueue (to the tail) In Words

(Remember that this is exactly the same as a stack's push, just a different name with a different connotation; to a queue, say for example queue of students at the cafeteria check-out, you want to "enqueue" the latest student to what is effectively the end of the line.)

To start, remember that you can only ever access a list from the head; that is the only node that you have a record of via the list object itself - all the List object itself is is a reference address of the Head node.

So from the head, you make your way along the list, one step at a time, each step calling that node's getNext( ) function, which returns the address of the next node in the chain.

As soon as the getNext( ) you are at returns null, you know you are at the end of the list, i.e., the Tail. This is because only the Tail points nowhere. It is to the tail that you will "push" onto the stack your new Node.

So you make a new Node, and then have the Tail's setNext( ) function set the "next" to be the new Node. Keeping in mind that technically the new Node is an address. So now, that new Node is the last in the chain, able to be found all the way from the Head with a series of getNext( )s.

 

Queue Dequeue (from the head) In Words

Compared to the other stack/queue algorithms, this is the easiest, in that no traversal to the end of the List is needed. What we are looking to work with and remove from the List is actually the Head - the Node that has been there the longest.

So we first do what we want to do with the data at the Head, while we still have access to it - so for example print(Head.getData( ).getName( )).

And then we effectively orphan that Node by making the Head to be the Node that it is pointing to - i.e., the second in line, with (Head = Head.getNext( )).

Now the List, which ever only has direct access to the Head, can no longer work with the former Head; that Node has beed dequeued!

 

Queue isEmpty in Words

(This is the same for any list, including stack.)

Recall that as a data structure, a List is actually a reference type. And the address it keeps, that it references is the Head of the list. We will know that the List is empty is the Head is null.

In the above diagram, there are two situations; one in which there is a one-Node list; i.e. there is a Head, though nothing else. Note that this is not an empty list. And so, the List will indeed point to a Head. But in the empty list, the one and only pointer is null; in other words, the Head attribute of the List is null.