We now have all the tools we need to implement the Stack and Queue interfaces from Chapter 4.

The ArrayStack Class

The ArrayStack class, which implements the Stack interface, is very similar to Deck. It contains an array `data` and an int `size`. When we create a new ArrayStack, `data` has room for one element and `size` is 0 (Figure 5-14). The Java wart involving generics and arrays comes up again on line 12. We can't allocate `new E[1]`, so we have to allocate `new Object[1]` and cast it to `E[]`. This causes a warning, but there's no way around it.

Figure 5-14. The generic ArrayStack class is similar to Deck.

1 /** An array-based Stack. */ 2 public class ArrayStack implements Stack { 3 4 /** Array of items in this Stack. */ 5 private E[] data; 6 7 /** Number of items currently in this Stack. */ 8 private int size; 9 10 /** The Stack is initially empty. */ 11 public ArrayStack() { 12 data = (E[])(new Object[1]); // This causes a compiler warning 13 size = 0; 14 } 15 16 } |

The `isEmpty()` method (Figure 5-15) is identical to the one from Deck.

Figure 5-15. It's easy to determine if an ArrayStack is empty.

1 public boolean isEmpty() { 2 return size == 0; 3 } |

The `pop()` method (Figure 5-16) is similar to `deal()`, although we throw an exception if the Stack is empty.

Figure 5-16. The `pop()` method can throw an EmptyStructureException.

1 public Object pop() { 2 if (isEmpty()) { 3 throw new EmptyStructureException(); 4 } 5 size--; 6 return data[size]; 7 } |

The `peek()` method (Figure 5-17) is even easier because it doesn't change the Stack. We do have to be careful to return the element at position `size - 1`, which is the top item on the Stack, rather than at position `size`, which is the next available position in `data`.

Figure 5-17. The `peek()` method returns the top element on the Stack.

1 public Object peek() { 2 if (isEmpty()) { 3 throw new EmptyStructureException(); 4 } 5 return data[size - 1]; 6 } |

All that remains is `push()`. If we try to push something onto a full Stack, the array is stretched, as described in Section 5.1. The code is given in Figure 5-18.

Figure 5-18. The `push()` method and associated protected methods. The reason for doubling the length of `data`, rather than merely increasing it by 1, is explained in Chapter 7.

1 /** Return true if data is full. */ 2 protected boolean isFull() { 3 return size == data.length; 4 } 5 6 public void push(Object target) { 7 if (isFull()) { 8 stretch(); 9 } 10 data[size] = target; 11 size++; 12 } 1314 /** Double the length of data. */ 15 protected void stretch() { 16 E[] newData = (E[])(new Object[data.length * 2]); // Warning 17 for (int i = 0; i < data.length; i++) { 18 newData[i] = data[i]; 19 } 20 data = newData; 21 } |

Figure 5-19 shows the effects of `push()` and `pop()` operations on an ArrayStack.

Figure 5-19. Instance diagram showing operations on an ArrayStack. These are the same operations shown in Figure 4-1. The shaded portions of `data` are not in use.

The ArrayQueue Class

The ArrayQueue class, which implements the Queue interface, makes further use of the idea of using only part of an array. There are, of course, complications.

We choose to make higher array indices correspond to elements closer to the back of the Queue. Thus, adding something to an ArrayQueue is exactly like pushing it onto an ArrayStack (Figure 5-20).

Figure 5-20. Adding something into an ArrayQueue is exactly like pushing it onto an ArrayStack. For brevity, we leave out the ArrayStack object and show only the array.

(This item is displayed on page 130 in the print version)

The problem comes when we remove an element from the queue. The first time we do this, the front of the queue is clearly at position 0. Afterward, the front of the queue is at index 1 (Figure 5-21).

Figure 5-21. Removing an element causes the front of the queue to move along the array.

(This item is displayed on page 130 in the print version)

We solve this problem with another field, an int `front`, which specifies where the queue starts. Whenever we remove, `front` is incremented, so we know where to find the first element the next time we remove. The next available position for adding is `front + size`.

There is one more issue. After a series of insertions and deletions, the "in use" portion of the array runs up against the right end of the array. Once this happens, we can't add anything else to the queue, even though there are unused positions.

The solution is for the queue to wrap around, so that the next element added goes at position 0. This is illustrated in Figure 5-22.

Figure 5-22. After hitting the right end of the array, the queue wraps around to the beginning.

When we add an element, it should normally be placed at position

front + size

but it should instead be placed at position

front + size - data. length

if the first expression would produce an index beyond the end of the array. We could compute the position with an `if` statement:

int index = front + size; if (index >= data.length) { index -= data.length; }

A more elegant solution uses the `%` operator. Recall that this operator gives the remainder of a division. If we divide `front + size` by the capacity of the queue, the quotient is either 0 or 1. If it is 0, the `%` operator has no effect. If it is 1, the `%` operator subtracts the capacity one time. The single expression

(front + size) % data.length

therefore always produces the right index.

The code for the ArrayQueue class is given in Figure 5-23.

Figure 5-23. The ArrayQueue class.

1 /** An array-based Queue. */ 2 public class ArrayQueue implements Queue { 3 4 /** Array of items in this Queue. */ 5 private E[] data; 6 7 /** Index of the frontmost element in this Queue. */ 8 private int front; 9 10 /** Number of items currently in this Queue. */ 11 private int size; 12 13 /** The Queue is initially empty. */ 14 public ArrayQueue() { 15 data = (E[])(new Object[1]); // This causes a compiler warning 16 size = 0; 17 front = 0; 18 } 19 20 public void add(E target) { 21 if (isFull()) { 22 stretch(); 23 } 24 data[(front + size) % data.length] = target; 25 size++; 26 } 27 28 public boolean isEmpty () { 29 return size == 0; 30 } 31 32 /** Return true if data is full. */ 33 protected boolean isFull() { 34 return size == data.length; 35 } 36 37 public E remove() { 38 if (isEmpty()) { 39 throw new EmptyStructureException(); 40 } 41 E result = data[front]; 42 front = (front + 1) % data.length; 43 size--; 44 return result; 45 } 46 47 /** Double the length of data. */ 48 protected void stretch() { 49 E[] newData = (E[])(new Object[data.length * 2]); // Warning 50 for (int i = 0; i < data.length; i++) { 51 newData[i] = data[(front + i) % data.length]; 52 } 53 data = newData; 54 front = 0; 55 } 56 57 } |

The operation of an ArrayQueue is illustrated in Figure 5-24.

Figure 5-24. Operations on an ArrayQueue. These are the same operations shown in Figure 4-29.

Exercises

5.7 |
Suppose we modified line 12 of Figure 5-14 so that, in a new ArrayStack, |

5.8 |
Show that, when playing Idiot's Delight, there will never be more than 13 cards in any one stack. We can avoid stretching the stacks if we allocate an array this large when each ArrayStack is first constructed. Write a second, overloaded constructor for the ArrayStack class which takes one argument |

5.9 |
Can Deck be written as a subclass of ArrayStack? If so, is it a good idea? If not, why not? |

5.10 |
Draw an instance diagram of an ArrayStack as it would look if, immediately after pushing D in Figure 5-19, we pushed E. |

5.11 |
Write a |

5.12 |
What would happen if we were to add something to a full ArrayQueue without stretching the array? |

5.13 |
Why is the |

5.14 |
Write a |

Part I: Object-Oriented Programming

Encapsulation

Polymorphism

Inheritance

- Inheritance
- Extending a Class
- The Object Class
- Packages and Access Levels
- Summary
- Vocabulary
- Problems
- Projects

Part II: Linear Structures

Stacks and Queues

- Stacks and Queues
- The Stack Interface
- The Call Stack
- Exceptions
- The Queue Interface
- Summary
- Vocabulary
- Problems
- Projects

Array-Based Structures

- Array-Based Structures
- Shrinking and Stretching Arrays
- Implementing Stacks and Queues
- The List Interface
- Iterators
- The Java Collections Framework: A First Look
- Summary
- Vocabulary
- Problems
- Projects

Linked Structures

- Linked Structures
- List Nodes
- Stacks and Queues
- The LinkedList Class
- The Java Collections Framework Revisited
- Summary
- Vocabulary
- Problems
- Projects

Part III: Algorithms

Analysis of Algorithms

- Analysis of Algorithms
- Timing
- Asymptotic Notation
- Counting Steps
- Best, Worst, and Average Case
- Amortized Analysis
- Summary
- Vocabulary
- Problems
- Projects

Searching and Sorting

- Searching and Sorting
- Linear Search
- Binary Search
- Insertion Sort
- The Comparable Interface
- Sorting Linked Lists
- Summary
- Vocabulary
- Problems
- Projects

Recursion

- Recursion
- Thinking Recursively
- Analyzing Recursive Algorithms
- Merge Sort
- Quicksort
- Avoiding Recursion
- Summary
- Vocabulary
- Problems
- Projects

Part IV: Trees and Sets

Trees

Sets

- Sets
- The Set Interface
- Ordered Lists
- Binary Search Trees
- Hash Tables
- The Java Collections Framework Again
- Summary
- Vocabulary
- Problems
- Projects

Part V: Advanced Topics

Advanced Linear Structures

- Advanced Linear Structures
- Bit Vectors
- Sparse Arrays
- Contiguous Representation of Multidimensional Arrays
- Advanced Searching and Sorting
- Summary
- Vocabulary
- Problems
- Projects

Strings

Advanced Trees

- Advanced Trees
- Heaps
- Disjoint Set Clusters
- Digital Search Trees
- Red-Black Trees
- Summary
- Vocabulary
- Problems
- Projects

Graphs

- Graphs
- Terminology
- Representation
- Graph Traversal
- Topological Sorting
- Shortest Paths
- Minimum Spanning Trees
- Summary
- Vocabulary
- Problems
- Projects

Memory Management

Out to the Disk

- Out to the Disk
- Interacting with Files
- Compression
- External Sorting
- B-Trees
- Summary
- Vocabulary
- Problems
- Projects

Part VI: Appendices

A. Review of Java

- A. Review of Java
- A.1. The First Program
- A.2. Variables and Types
- A.3. Loops
- A.4. Interacting with the User
- A.5. Branching
- A.6. Methods and Breaking Out
- A.7. Constants
- A.8. Operators
- A.9. Debugging
- A.10. Coding Conventions

B. Unified Modeling Language

C. Summation Formulae

- C. Summation Formulae
- C.1. Sum Notation
- C.2. Sum of Constants
- C.3. Sum of First n Integers
- C.4. Sums of Halves and Doubles
- C.5. Upper Limit on Sum of a Function
- C.6. Constant Factors

D. Further Reading

Index

Data Structures and Algorithms in Java

ISBN: 0131469142

EAN: 2147483647

EAN: 2147483647

Year: 2004

Pages: 216

Pages: 216

Authors: Peter Drake

Flylib.com © 2008-2020.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net