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 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 (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 other events, including other errors cause stacking of those other errors and other events. This is the case because if anything, including an error itself, is interrupted by a new error, it's that last error that has to be handled first, before the other ones can be.

- 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();
}

public static void method1(){
method2();
}

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 get finished, they can then also finish.

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