Logout

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.

- Since they are 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 the "tail" end of the stack.

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

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

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