Stacks and Queues - Advanced Topics in Java: Core Concepts in Data Structures - page 137

public Node(NodeData d) {
data = d;
next = null;
}
} //end class Node
class Queue {
Node head = null, tail = null;
public boolean empty() {
return head == null;
}
public void enqueue(NodeData nd) {
Node p = new Node(nd);
if (this.empty()) {
head = p;
tail = p;
}
else {
tail.next = p;
tail = p;
}
} //end enqueue
public NodeData dequeue() {
if (this.empty()) {
System.out.printf("\nAttempt to remove from an empty queue\n");
System.exit(1);
}
NodeData hold = head.data;
head = head.next;
if (head == null) tail = null;
return hold;
} //end dequeue
} //end class Queue
The following is a sample run of Program P4.8:
Enter a positive integer: 192837465
Digits in reverse order: 564738291
Stacks and queues are important to systems programmers and compiler writers. We have seen how stacks
are used in the evaluation of arithmetic expressions. They are also used to implement the “calling” and “return”
mechanism for functions. Consider the situation where function A calls function C , which calls function B , which calls
function D . When a function returns, how does the computer figure out where to return to? We show how a stack can
be used to do this.