Java Reference
In-Depth Information
The principle behind this technique is worth remembering, as it has
many applications. The following code fragment will swap the contents
of two variables without using a temporary variable (at the cost of three
arithmetic operations).
a=a+b;
b=a-b;//Nowbcontainsoriginalvalueofa
a=a-b;//Nowacontainsoriginalvalueofb
A similar effect can be had by using the exclusive-or operator. This fact
is widely used in computer graphics. A region of the computer screen can
be highlighted by XORing the outline of a box around it. XORing the box
outline a second time restores the original contents of the screen.
4.2
Stacks
The stack is a list-like structure in which elements may be inserted or removed
from only one end. While this restriction makes stacks less flexible than lists, it
also makes stacks both efficient (for those operations they can do) and easy to im-
plement. Many applications require only the limited form of insert and remove
operations that stacks provide. In such cases, it is more efficient to use the sim-
pler stack data structure rather than the generic list. For example, the freelist of
Section 4.1.2 is really a stack.
Despite their restrictions, stacks have many uses. Thus, a special vocabulary
for stacks has developed. Accountants used stacks long before the invention of the
computer. They called the stack a “LIFO” list, which stands for “Last-In, First-
Out.” Note that one implication of the LIFO policy is that stacks remove elements
in reverse order of their arrival.
The accessible element of the stack is called the top element. Elements are not
said to be inserted, they are pushed onto the stack. When removed, an element is
said to be popped from the stack. Figure 4.18 shows a sample stack ADT.
As with lists, there are many variations on stack implementation. The two ap-
proaches presented here are array-based and linked stacks, which are analogous
to array-based and linked lists, respectively.
4.2.1
Array-Based Stacks
Figure 4.19 shows a complete implementation for the array-based stack class. As
with the array-based list implementation,
listArray
must be declared of fixed
size when the stack is created. In the stack constructor,
size
serves to indicate
this size. Method
top
acts somewhat like a current position value (because the
“current” position is always at the top of the stack), as well as indicating the number
of elements currently in the stack.
