Java Reference
In-Depth Information
To illustrate the stack idea, we will use a stack of integers. Our goal is to define a data type called Stack so that a
user can declare variables of this type and manipulate them in various ways. What are some of these ways?
As indicated earlier, we will need to add an item to the stack; the term commonly used is push . We will also need
to take an item off the stack; the term commonly used is pop .
Before we attempt to take something off the stack, it is a good idea to ensure that the stack has something on it, in
other words, that it is not empty . We will need an operation that tests whether a stack is empty.
Given these three operations— push , pop , and empty —let's illustrate how they can be used to read some numbers
and print them in reverse order. For example, say we have these numbers:
36 15 52 23
And say we want to print the following:
23 52 15 36
We can solve this problem by adding each new number to the top of a stack, S . After all the numbers have been
placed on the stack, we can picture the stack as follows:
23 (top of stack)
52
15
36 (bottom of stack)
Next, we remove the numbers, one at a time, printing each as it is removed.
We will need a way of telling when all the numbers have been read. We will use 0 to end the data. The logic for
solving this problem can be expressed as follows:
create an empty stack, S
read(num)
while (num != 0) {
push num onto S
read(num)
}
while (S is not empty) {
pop S into num //store the number at the top of S in num
print num
}
We now show how we can implement a stack of integers and its operations.
4.2.1 Implementing a Stack Using an Array
To simplify the presentation of the basic principles, we will work with a stack of integers. Later, we will see how to
implement a stack for a general data type.
In the array implementation of a stack (of integers), we use an integer array ( ST , say) for storing the numbers and
an integer variable ( top , say) that contains the subscript of the item at the top of the stack.
Since we are using an array, we will need to know its size in order to declare it. We will need to have some
information about the problem to determine a reasonable size for the array. We will use the symbolic constant
MaxStack . If we attempt to push more than MaxStack elements onto the stack, a stack overflow error will be reported.
 
Search WWH ::




Custom Search