Home Topic 5 Last Next


Construct algorithms using the access methods of a stack.


Teaching Note:

Access methods:

- push
- pop
- isEmpty.

LINK Connecting computational thinking and program design.


Sample Question:


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"...for Topic 5, but yes for the OOP Option.

Below is a full movie of stacks and queues.


(backup link of video)

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

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

Stacking Works With Head or Tail - it's LIFO that matters

Finally, before launching into these algorithmic diagrams, note that the ways shown here to push and pop ****are not the most efficient ways*** to do so. To push and pop, you can use either end of the list, and using the head is actually the easiest and most efficient. Never-the-less, you actually are also responsible for understanding how to work with the other end of the list, and furthermore, working with the "top" of this list can seem more natural - we push onto the top of a stack, and "pop" off the top.

Though, 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.

JSR Teaching Note: Considering this, an alternative way to teach all of this is "vertically", with diagrams going up and down, rather than side-to-side. In that case, the stacks themselves look more natural, with a head that is popped & pushed & enqueued at the top. It's just that the construction of diagrams themselves is not as natrual; not left to right, and side-to-side, as arrays more seem to be.


Stack Push (onto the tail) In Words

(Remember that this is exactly the same as a queue's enqueue, just a different name with a different connotation; on a stack, say for example a stack of plates, you want to push on top the newest plate to be added to the stack.)

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.


Stack Pop (from tail) in Words

From a stack, you want to "pop" off what is effectively the top of the stack. But remember that you only directly have access to the Head, not the Tail (i.e. top). So you first have to navigate your way to the top (i.e. Tail) from the Head.

So with the address of the Head that the List itself has, you access the Head, and then, in turn, access all of the other Nodes in the list with one getNext( ) at a time. As with push/enqueue, you know you have reached the Tail when the getNext( ) of that Node you are at is null.

(For reasons that will become clear a couple of steps down, during this process, you not only want to keep track of where you are, you want to keep track of the "Previous" Node also.)

Once at the Tail, you will want to do something with the data there; this might be simply printing out the data, or it could be anything else that needs to be done with the data. And then in terms of the stack, with a pop operation, you are assumed to be done with that Node, and want to get rid of it. (Note that often times you will want to only access the data there, but keep the Node as part of this list; this is called "peeking".)

To "get rid" of the Node, i.e. to "pop" it off the top of the stack, you will be effectivley orphaning it by breaking the link to it. The way you do this is by changing the link of the "Previous" Node; i.e. the one before the Tail - recalling that you have been keeping track of the Previous at each step through your traversal of the List. You change the getNext( ) of Previous to be null. This effectively make it, not the former Tail (which you have used/popped) the Tail. And the former Tail is now no loger accessible; it has been popped!





Stack isEmpty in Words

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

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.




Note that actual Java implementation details of all this are expected in the OOP extension later on in the curriculum.