Java Reference
In-Depth Information
The following is a sample run of Program P4.7:
Enter a positive integer: 192837465
Digits in reverse order: 564738291
4.5.2 Implementing a Queue Using a Linked List
As with stacks, we can implement a queue using linked lists. This has the advantage of us not having to decide
beforehand how many items to cater for. We will use two pointers, head and tail , to point to the first and last items in
the queue, respectively. Figure 4-9 shows the data structure when four items (36, 15, 52, and 23) are added to the queue.
Q
head
tail
36
15
52
23
Figure 4-9. Linked list representation of a queue
We will implement the queue so that it works with a general data type that we will call NodeData . Each node in the
queue will be created from a Node class, which we define as follows:
class Node {
NodeData data;
Node next;
public Node(NodeData d) {
data = d;
next = null;
}
} //end class Node
When the user defines the NodeData class, he will decide what kind of items will be stored in the queue.
The Queue class starts as follows:
public class Queue {
Node head = null, tail = null;
public boolean empty() {
return head == null;
}
...
 
Search WWH ::




Custom Search