A stack is a linear data structure.
-
All additions to and deletions from a stack occur at the top of the stack. The last item pushed onto the stack will be the first item removed. A stack is sometimes referred to as a LIFO
("Last-In, First-Out") structure.
-
Two of the more important stack operations involve pushing data onto a stack and popping data off the stack.
- Diagram 31-1 (below) illustrates the push operation:
Diagram 31-1: Push Operation
- Diagram 31-2 illustrates the pop operation:
Diagram 31-2: Pop Operation
- Stacks are very useful for implementing recursion. The local values of a method are placed on a stack each time the method calls itself. When the method returns, the stack is popped to restore the local values for that call. Another example of using a stack structure is when a web browser stores the URLs that are visited. When a new URL is visited it is placed on a stack. When the back button is used, the stack is popped.