Logout

Home Topic 5 Last Next

5.1.6

Describe the characteristics and applications of a stack.

 

Teaching Note:

Characteristics:

- Last in, first out (LIFO).

Examples of the applications of stacks may include running recursive processes, return memory addresses.

LINK Recursive thinking; connecting computational thinking and program design.


 

Sample Question:

sdfsdfsf

JSR Notes:

 

Features of the Stack ADT:

Characteristics

- Stacks are particular implementation of lists, which operate in a LIFO manner - the Last In is the First Out.

- As lists, stacks (like queues) are made of a "chain" of self-referencing nodes; i.e. nodes of the same type that point to each other.

- Items can be added, or "pushed" onto either end of the list (though pushing onto the head is the least number of steps).

- Items can be taken from, or "popped" from that same end of the list, and so operating in a LIFO basis (Last In, Last Out).

- Note that this processing, then, is always happening at the SAME END of the list (again, usually the end with the head).

- When pushing or popping, it is important that checks can be made to see if the stack is empty, thus preventing the error of trying to access something that is not there.


Simple Summary Diagram

Applications

General:

- Any process in which the last one on the stack should be the first one that is next dealt with, and so taken off the stack.

Analogies:

- A conventional analogy is when plates are stacked on top of each other in a cafeteria; it is impossible to take from the bottom of the stack, and so we always take the top plate off of the stack.

- In fact stacking of physical objects, like magazines on the coffee table of the living room.

Computing:

- 1. Errors, which can interrupt events, including other errors, result in the stacking of the unfinished, interrupted processes. The unfinished errors and other unfinished events, stack up in a LIFO manner. So once any given error situation has been properly handled, it is popped off the stack, and the computer can go back to the last thing that was interruped, and so on, and so on, down through the stack.

- 2. Method calls in the middle of other methods cause stacking of the unfinished methods. In this case the unfinished method that has made the call goes on a stack, and waits for the called method to be finished. This can go many levels deep; for example, main( ) calls method1( ), and method1( ) calls method2( ), and method2( ) calls println( ). When println( ) is being executed, all of the method calls before it are on a LIFO stack waiting to be finished. Here is that example

public static void main(String args[ ]){
method1();
//plus, likely, other stuff...
}

public static void method1(){
method2();
//plus, likely, other stuff...
}

public static void method2(){
System.out.println("Inside method2."); //When println() is called, method2()
} //the stack of unfinished method1()
//methods looks like this: main()

//It will be worked on down from top to bottom, after println() is finished.

- 3. Recursion. Recursion is a process in which a method is interrupted by calls to other instances of itself. This accomplishes repetition without the use of a conventional structure such as a for or while loop. Since functions get interrupted, they are not finished, and so they have to be put some place, on a "stack", where they wait to be handled. Once the other method, that they themselves called, gets finished, they can then also finish.

Note that all three of the above situations are generally "putting unfinished business on a stack to get back to later one".

- 4. History/Undos. Most user software applications keep track of the commands executed, and allow users to work their way back through those things to undo them. This is a classic example of a stack, in that the last thing done is the first thing that should be undone.