Stacks - Data Structures and Abstractions with Java - page 130

public T push(T item);
public T pop();
public T peek();
public boolean empty();

Stack also defines methods that enable you to search or traverse the entries in the stack, as well
as other methods not supported by a traditional stack ADT.

Note: The standard class java.util.Stack is now considered a legacy class. As you will
see in Chapter 10, you instead should use the class java.util.ArrayDeque when you do not
want to define your own class of stacks. However, you can use Stack for now, and we will
define our own stack classes in the next chapter.

C HAPTER S UMMARY

The ADT stack organizes its entries on a last-in, first-out basis. The entry at the top of the stack is the one
added most recently.

●

A stack's major operations— push , pop , and peek —deal only with the top of the stack. The method push
adds an entry to the top of the stack; pop removes and returns the top entry, and peek just returns it.

●

Arithmetic operators that have two operands are binary operators. When an operator such as + or - has one
operand, it is a unary operator.

●

An algebraic expression often contains parentheses, square brackets, and braces. You can use a stack to dis-
cover whether these delimiters are paired correctly.

●

Ordinary algebraic expressions are called infix expressions, because each binary operator appears between
its two operands. An infix expression requires rules of operator precedence and can use parentheses to over-
ride these rules.

●

In a postfix expression, each binary operator appears after its two operands. In a prefix expression, each
binary operator appears before its two operands. Postfix and prefix expressions use no parentheses and have
no rules of operator precedence.

●

You can use a stack of operators when forming a postfix expression that is equivalent to a given infix expression.

●

You can use a stack of values to evaluate a postfix expression.

●

You can use two stacks—one for operators and one for values—to evaluate an infix expression.

●

When a method is called, the Java run-time environment creates an activation record, or frame, to record the
status of the method. The record contains the method's arguments and local variables, along with the address
of the current instruction. The record is placed in a stack called the program stack.

●

P ROGRAMMING T IP

Methods such as peek and pop must behave reasonably when the stack is empty. For example, they could
return null or throw an exception.

●