Stacks (Abstract Data Type)
Stacks (Abstract Data Type)
Pushdown (LIFO) stacks
public class Stack<Item> implements Iterable<Item>
Stack() - create an empty stack
void push(Item item) - add an item
Item pop() - remove the most recently added item
boolean isEmpty() - is the stack empty?
int size() - number of items in the stack
| Operations Provided | Efficiency |
|---|---|
| Push item | O(1) |
| Pop item | O(1) |
Implemented by Stack, LinkedList, and ArrayDeque in Java
The only differences between the APIs for Stack and Queue are their names and the names of the methods. This observation highlights the idea that we cannot easily specify all of the characteristics of a data type in a list of method signatures. In this case, the true specification has to do with the English-language descriptions that specify the rules by which an item is chosen to be removed (or to be processed next in the foreach statement). Differences in these rules are profound, part of the API, and certainly of critical importance in developing client code.
A queue is appropriate because it puts the numbers into the array in the order in which they appear in the file (we might use a Bag if that order is immaterial). This code uses autoboxing and auto-unboxing to convert between the client’s double primitive type and and the queue’s Double wrapper type.
A pushdown stack (or just a stack) is a collection that is based on the last-in-first-out (LIFO) policy. When you keep your mail in a pile on your desk, you are using a stack. You pile pieces of new mail on the top when they arrive and take each piece of mail from the top when you are ready to read it. People do not process as many papers as they did in the past, but the same organizing principle underlies several of the ap- plications that you use regularly on your computer. For example, many people organize their email as a stack they push messages on the top when they are received and pop them from the top when they read them, with most recently received first (last in, first out). The ad- vantage of this strategy is that we see interesting email as soon as possible; the disadvantage is that some old email might never get read if we never empty the stack. You have likely encountered another common example of a stack when surfing the web. When you click a hyperlink, your browser displays the new page (and pushes onto a stack). You can keep clicking on hyperlinks to visit new pages, but you can always revisit the previous page by clicking the back button (popping it from the stack). The LIFO policy offered by a stack provides just the be- havior that you expect. When a client iterates through the items in a stack with the foreach construct, the items are processed in the reverse of the order in which they were added. A typical reason to use a stack iterator in an application is to save items in a collection while at the same time reversing their relative order . For example, the client Reverse at right (TODO : implement) reverses the or- der of the integers on standard input, again without having to know ahead of time how many there are. The importance of stacks in computing is fundamental and profound, as indicated in the detailed example that we consider next.
See FullyParenthesizedArithmeticExpressionEvaluation.java