Logout

Home Topic 5 Last Next

5.1.7

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:

sdfsdfsf

JSR Notes:

Firstly, remember that for Topic 5, "This will be examined at the level of diagrams and pseudocode.". But at the same time, remember that actual programmiing implementations will be necessary for the OOP Option.

In terms of whether or not you should, at this point, understand how the various methods work (pop( ), enqueue( ) etc.), it should not be necessary for Topic 5, but an appreciation of it at this point will help overall understanding of self referential systems, and the more sophisticated part of OOP. So it's worth looking at it ere. (*Though it's not so necessary for the class of 2021, with Paper 2 being dropped.)

Stack Algorithms


Remember that stacks are lists that work in a Last In, First Out (LIFO) manner. Note that for stacks both adding and taking away happen at the SAME end.

(And keep in mind stacking can work with head or tail, but it's LIFO that matters.)

 

Stacking Algorithm Functions
push( ), pop( ), and isEmpty( )

 

Java Stack Algorithms Examples


public class MainForStacksAndQueues { 
    static LinkedList<String> listAsStack = new LinkedList<String>(); 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
 
    public static void main(String[] args) throws Exception{ 
        boolean keepAdding = true; 
        while(keepAdding){ 
            System.out.println("What do you want to add to the stack?"); 
            String s = br.readLine(); 
            listAsStack.push(s); //so being built as a queue 
            System.out.println("Another item? true/false"); 
            keepAdding = Boolean.parseBoolean(br.readLine()); 
        } 
        if(!listAsStack.isEmpty()) { 
            System.out.println("The first item to be dequeued off is: " + listAsStack.pop()); 
            //so taking the one that just got put there - thereby treating it in stack fashion 
        } 
 
        if(!listAsStack.isEmpty()) { 
            System.out.println("The second item to be dequeued off is: " + listAsStack.pop()); 
        } 
    } 
} 

IB Pseudocode Stack Algorithms Examples

stack LIST_AS_STACK
KEEP_ADDING = true

loop while KEEP_ADDING is true

output "What do you want to add to the stack?"
S = input
LIST_AS_STACK.push(S)
output "Another item? true/false"
KEEP_ADDING = input

end loop

if not LIST_AS_STACK.isEmpty( ) then

output "The first item to be dequed off is" + LIST_AS_STACK.pop( )

end if

if not LIST_AS_STACK.isEmpty( ) then

output "The first item to be dequed off is" + LIST_AS_STACK.pop( )

end if

 

More Java Tracing Examples

Example A - Straight-forward Stack Example

48 
53     public static void stackExample(){
54         LinkedList<Integer> intList = new LinkedList<Integer>();
55         intList.push(62);                         //62
56         intList.push(55);                         //62  55
57         intList.push(44);                         //62  55  44
58         intList.push(88);                         //62  55  44  88
59         intList.push(99);                         //62  55  44  88  99
60         System.out.println(intList.pop());         //62  55  44  88    Output 99
61         System.out.println(intList.pop());         //62  55  44        Output 88
62         System.out.println(intList.pop());         //62  55            Output 44 
63     }
64 

Q1. What is the output after the following code is run?

 1 import java.util.LinkedList;
 2 
 3 public class MoreLinkedListQs {
 4     public static void main(String[] args) {
 5         LinkedList<String> countries = new LinkedList<String>();
 6         countries.push("Canada");
 7         countries.push("USA");
 8         System.out.println(countries.pop());
 9         countries.push("Malaysia");
10         countries.push("Madagascar");
11         System.out.println(countries.pop());
12         System.out.println(countries.pop());
13         countries.push("Zimbabwe");
14         System.out.println(countries.pop());
15         for(int i = 0; i < countries.size(); i++){
16             System.out.println(countries.get(i));
17         }
18     }
19 }

Q2. What is the output after the following code is run?
This is a bit harder, and throws in at least one other LinkedList method, so the output 
of the following code is done for you by way of comments to the side.
 1 
 2 import java.util.LinkedList;
 3 
 4 public class UsingLinkedList {
 5     public static void main(String[] args) {
 6         stackOfStrings();
 7     }
 8     public static void stackOfStrings(){
 9         LinkedList<String> namesList = new LinkedList<String>();
10         namesList.push("Joe");                   //Joe
11         namesList.push("Betty");                 //Betty Joe  //***Note that here 
                              //we depict the last one in as going at the front.
                              //(unlike example A above, where it got pushed on the back)
                              //but front or back doesn't matter - it's the LIFO that matters
12         namesList.push("Phil");                  //Phil Betty Joe
13         System.out.println(namesList.pop());      //Betty Joe         //Phil output
14         System.out.println(namesList.getFirst()); //Betty Joe         //Betty output
15         namesList.pop();                         //Joe               //(no output)
16         namesList.push("Sue");                   //Sue Joe
17         namesList.push("Charles");               //Charles Sue Joe
18         namesList.pop();                         //Sue Joe           //(no output)
19         namesList.push("Chisanga");              //Chisanga Sue Joe
20         System.out.println(namesList.pop());      //Sue Joe           //Chisanga output
21     }
22 }

 

Actual Ways Stacks Work (more Option than Topic 5)

 

So here they are, in diagramatic and word form, the algorithms for stacks. Remember that for stacks, they always work in a Last In First Out (LIFO) manner.

(And, note that you could also add to the "tail", and not bother to shift the head, but that would make things inefficient, since each time for both push and pop, you would have to traverse the whole list. **)

Pushing onto a stack algorithm in words

 

 

Popping from a stack algorithm in words

 

Stack isEmpty( ) in words

Recall that all a list is, is a Node attribute for keeping track of head. So if that head attribute points to no head at all, i.e. it's head attribute is null, then isEmpty( ) returns false. Otherwise, it returns true.

 

** Working with the head vs. the tail

Do note with these diagrams above, both the push and the pop work with the head, and is the most efficient way to do so, since you don't have to loop through to the end of the stack in either case. Refer to the OPTIONAL part of the notes below to see diagrams of a pop and push that work with the tail.

About the only reason you may actually choose to work with the tail instead of the head, is just that it mimics the particular real-world LIFO situation you are modelling better. But for sure, working with the tail (at least the way shown below) is inefficient.

 

 

---------------- OPTIONAL, AT LEAST HERE, TOPIC 5; -------------------

-----------THE OOP OPTION INCLUDES WORKING WITH TAILS -------

 

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.

 

Re-cap

Below is a full movie of stacks and queues. You will note that they are done slightly differently than the diagrams below. In fact, there are quite a few variations with how you can implement stack and queue ADTs. But, both the stacks in both the video and the diagrams work in a FIFO manner (as do the queues in a FIFO manner.)

And with this, keep in mind that these are indeed ADTs, abstrat data types, which we, as the programmer can choose to implement any way we want, as long as they keep the main features of what we describe them as; again, in the case of stacks, the LIFO way of working.

(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.