Stacks and Queues

We now present the LinkedStack and LinkedQueue classes, which respectively implement the Stack and Queue interfaces from Chapter 4.

The LinkedStack Class

A (nonempty) LinkedStack contains (a reference to) a ListNode, which in turn contains an element and perhaps another ListNode. In UML class diagrams, this relationship may be illustrated in any of several levels of detail, depending on what is being emphasized (Figure 6-9).

Figure 6-9. Three different UML class diagrams showing the relationship between the LinkedStack and ListNode classes and the class of the element type E. The most precise diagram (top) indicates that a LinkedStack may contain a ListNode, which contains an E and possibly another ListNode. The middle diagram indicates that a LinkedStack contains 0 or more ListNodes, each of which contains an E. The fact that some of these ListNodes are only indirectly contained in the LinkedStack is left out. The bottom diagram omits the ListNode class altogether, merely indicating that a LinkedStack contains 0 or more instance of E.

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

The activity of a LinkedStack is shown in Figure 6-10.

Figure 6-10. Activity of a LinkedStack. These are the same operations shown in Figure 4-1. Again, type parameters have been omitted for clarity.

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

Like any linked structure, a LinkedStack always has just enough room for its elements. It is never necessary to stretch a linked structure by copying the elements.

The code for the LinkedStack class is very short (Figure 6-11).

In an empty LinkedStack, including a newly created one, top is null. The isEmpty() method only has to check for this.

The push() method splices a new node onto the beginning of the chain. As shown in Figure 6-12, each time we push something onto the Stack, a new node is created, but the old nodes don't change. The next field of the new ListNode gets the old value of topthat is, a reference to the rest of the chain. The other nodes aren't affected.

It is important to realize that the rightmost LinkedStack in Figure 6-12 is not in any sense "full." The positions of the nodes on paper or in memory are completely arbitrary. We could have drawn the top of the Stack at the bottom of the diagram. Whichever node is referred to by top is the top one, regardless of where it is drawn. All that matters is the chain of references. In fact, as we'll see in Chapter 16, Java can sometimes move things around in memory without telling us. This doesn't cause a problem, because the reference chains (which node refers to which other node) are unaffected.

Figure 6-11. The LinkedStack class.

 1 /** A linked Stack. */
 2 public class LinkedStack implements Stack {
 3
 4 /** The top ListNode in the Stack. */
 5 private ListNode top;
 6
 7 /** The Stack is initially empty. */
 8 public LinkedStack() {
 9 top = null;
10 }
11
12 public boolean isEmpty() {
13 return top == null;
14 }
15
16 public E peek() {
17 if (isEmpty()) {
18 throw new EmptyStructureException();
19 }
20 return top.getItem();
21 }
22
23 public E pop() {
24 if (isEmpty()) {
25 throw new EmptyStructureException();
26 }
27 E result = top.getItem();
28 top = top.getNext();
29 return result;
30 }
31
32 public void push(E target) {
33 top = new ListNode(target, top);
34 }
35
36 }

The pop() method is the complement of push(). It splices a node out, as described in Section 6.1. This method is longer for a couple of reasons. First, if the Stack is empty, we have to throw an exception. Second, we have to store the element from the node we are removing in a variable. We have to do this before we remove the node, because the node becomes unreachable once we change the value of top (Figure 6-13).

Figure 6-12. Pushing a series of elements onto a LinkedStack. At each step, modified references and newly created nodes are shown in grey. The value of next in the new node is always the same as the previous value of top.

Figure 6-13. Repeated popping of a LinkedStack. Once top changes, the node to which it used to point becomes unreachable.

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

The reader with an eye to tidiness may wonder, "What happens to these unreachable nodes? Are they taking up memory?" In a language like C, the answer is yes. In Java, on the other hand, any object which can no longer be reached (because there are no references to it) magically disappears. This will be explained in Chapter 16.

The peek() method is easy, although we must be careful not to confuse top (the top node) and top.getItem() (the element contained in that node).

The LinkedQueue Class

The LinkedQueue class implements the Queue interface. Because we add elements to the back and remove them from the front, we have to keep track of both ends of the chain of nodes. This is illustrated in Figure 6-14.

Figure 6-14. Activity of a LinkedQueue. These are the same operations shown in Figure 4-29. The references from the ListNodes are all the next fields.

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

The code for the LinkedQueue class is given in Figure 6-15.

Figure 6-15. The LinkedQueue class.

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

 1 /** A linked Queue. */
 2 public class LinkedQueue implements Queue {
 3
 4 /** The front ListNode in the Queue. */
 5 private ListNode front;
 6
 7 /** The back ListNode in the Queue. */
 8 private ListNode back;
 9
10 /** The Queue is initially empty. */
11 public LinkedQueue() {
12 front = null;
13 back = null;
14 }
15
16 public void add(E target) {
17 ListNode node = new ListNode(target);
18 if (isEmpty()) {
19 front = node;
20 back = node;
21 } else {
22 back.setNext(node);
23 back = node;
24 }
25 }
26
27 public boolean isEmpty() {
28 return front == null;
29 }
30
31 public E remove() {
32 if (isEmpty()) {
33 throw new EmptyStructureException();
34 }
35 E result = front.getItem();
36 front = front.getNext();
37 return result;
38 }
39
40 }

The isEmpty() method looks just like the one from LinkedStack, with front standing in for top.

The add() method creates a new ListNode and adds it to the back of the Queue. An empty Queue needs special treatment, because the new node also becomes the front of the Queue. If the Queue is not empty, we simply splice the new node onto the back by setting the next field in the last node (Figure 6-16).

Figure 6-16. In a newly created LinkedQueue (top), both front and back are null. When the first element is added to the Queue (middle), the new node becomes both the front and the back of the Queue. Subsequent nodes are simply spliced onto the back of the Queue (bottom).

The remove() method is like pop() from LinkedStack. If we remove the last node, front becomes null (Figure 6-17). It does not matter that back still points to the node that was just removed. No method does anything with back without first checking whether front is null.

Figure 6-17. If there is only one element in a LinkedQueue, front and back are references to the same ListNode (top). The remove() method changes front, but leaves back pointing at this node (bottom).

Exercises

6.4	Draw a UML class diagram showing the relationship between Stack, ArrayStack, and LinkedStack.
6.5	The pop() method from the LinkedStack class (Figure 6-11) stores the element being popped in a temporary variable result. Why doesn't the pop() method from ArrayStack (Figure 5-16) need to do this?
6.6	Modify the Idiot's Delight program from Chapter 4 to use LinkedStacks instead of ArrayStacks.
6.7	Java automatically reclaims the memory used by objects and arrays which are no longer reachable. In Figure 6-17, the ListNode removed from the LinkedQueue is still reachable through the field back. Is there a danger that a great deal of memory could be taken up by such ListNodes? Explain.

The LinkedList Class