4.3   Stacks and Queues


This section under major construction.


Stacks and queues.

In this section, we introduce two closely-related data types for manipulating arbitrarily large collections of objects: the stack and the queue. Each is defined by two basic operations: insert a new item, and remove an item. When we insert an item, our intent is clear. But when we remove an item, which one do we choose? The rule used for a queue is to always remove the item that has been in the collection the most amount of time. This policy is known as first-in-first-out or FIFO. The rule used for a stack is to always remove the item that has been in the collection the least amount of time. This policy is known as last-in first-out or LIFO.

Pushdown stacks.

A pushdown stack (or just a stack) is a collection that is based on the last-in-first-out (LIFO) policy. When you click a hyperlink, your browser displays the new page (and inserts it onto a stack). You can keep clicking on hyperlinks to visit new pages. You can always revisit the previous page by clicking the back button (remove it from a stack). The last-in-first-out policy offered by a pushdown stack provides just the behavior that you expect.

Pushdown stack

By tradition, we name the stack insert method push() and the stack remove operation pop(). We also include a method to test whether the stack is empty. The following API summarizes the operations:

API for a stack of strings
The asterisk indicates that we will be considering more than one implementation of this API.

Array implementation.

Representing stacks with arrays is a natural idea. The first problem that you might encounter is implementing the constructor ArrayStackOfStrings(). An instance variable a[] with an array of strings to hold the stack items is clearly needed, but how big should it be? For the moment, We will finesse this problem by having the client provide an argument for the constructor that gives the maximum stack size. We keep the items in reverse order of their arrival. This policy allows us to add and remove items at the end without moving any of the other items in the stack.

We could hardly hope for a simpler implementation of ArrayStackOfStrings.java: all of the methods are one-liners! The instance variables are an array a[] that hold the items in the stack and an integer N that counts the number of items in the stack. To remove an item, we decrement N and then return a[N]; to insert a new item, we set a[N] equal to the new item and then increment N. These operations preserve the following properties: the items in the array are in their insertion order the stack is empty when the value of N is 0 the top of the stack (if it is nonempty) is at a[N-1]

Trace of ArrayStackOfStrings test client
The primary characteristic of this implementation is that the push and pop operations take constant time. The drawback of this implementation is that it requires the client to estimate the maximum size of the stack ahead of time and always uses space proportional to that maximum, which may be unreasonable in some situations.

Linked lists.

For classes such as stacks that implement collections of objects, an important objective is to ensure that the amount of space used is always proportional to the number of items in the collection. Now we consider the use of a fundamental data structure known as a linked list that can provide implementations of collections (and, in particular, stacks) that achieves this important objective.

A linked list is a recursive data structure defined as follows: a linked list is either empty (null) or a reference to a node having a reference to a linked list. The node in this definition is an abstract entity that might hold any kind of data in addition to the node reference that characterizes its role in building linked lists. With object-oriented programming, implementing linked lists is not difficult. We start with a simple example of a class for the node abstraction:

class Node { 
   String item; 
   Node next; 
} 
A Node has two instance variables: a String and a Node. The String is a placeholder in this example for any data that we might want to structure with a linked list (we can use any set of instance variables); the instance variable of type Node characterizes the linked nature of the data structure. Now, from the recursive definition, we can represent a linked list by a variable of type Node just by ensuring that its value is either null or a reference to a Node whose next field is a reference to a linked list.

We create an object of type Node by invoking its (no-argument) constructor. This creates a reference to a Node object whose instance variables are both initialized to the value null. For example, to build a linked list that contains the items "to", "be", and "or", we create a Node for each item:

linking together a linked list

Node first  = new Node(); 
Node second = new Node(); 
Node third  = new Node(); 
and set the item field in each of the nodes to the desired item value:
first.item  = "to"; 
second.item = "be"; 
third.item  = "or";
and set the next fields to build the linked list:
first.next  = second; 
second.next = third; 
third.next  = null;
When tracing code that uses linked lists and other linked structures, we use a visual representation of the changes where we draw a rectangle to represent each object we put the values of instance variables within the rectangle we depict references as arrows that point to the referenced object This visual representation captures the essential characteristic of linked lists and allows us to focus on the links. These two operations take constant time (independent of the length of the list).

Implementing stacks with linked lists.

Program LinkedStackOfStrings.java uses a linked list to implement a stack of strings. The implementation is based on a nested class Node like the one we have been using. Java allows us to define and use other classes within class implementations in this natural way. The class is private because clients do not need to know any of the details of the linked lists.

trace of stack implementation using a linked list of strings

List traversal.

One of the most common operations we perform on collections is to iterate through the items in the collection. For example, we might wish to implement the toString() method to facilitate debugging our stack code with traces. For ArrayStackOfStrings, this implementation is familiar:
public String toString() { 
   String s = ""; 
   for (int i = 0; i < N; i++) 
      s += a[i] + " "; 
   return s; 
} 
As usual, this solution is intended for use only when N is small - it takes quadratic time because string concatenation takes linear time. Our focus now is just on the process of examining every item. There is a corresponding idiom for visiting the items in a linked list: We initialize a loop index variable x that references the the first Node of the linked list. Then, we find the value of the item associated with x by accessing x.item, and then update x to refer to the next Node in the linked list assigning to it the value of x.next, repeating this process until x is null (which indicates that we have reached the end of the linked list). This process is known as traversing the list, and is succinctly expressed in this implementation of toString() for LinkedStackOfStrings:
public String toString() { 
   String s = ""; 
   for (Node x = first; x != null; x = x.next) 
      s += x.item + " "; 
   return s; 
} 

Array doubling.

Next, we consider an approach to accommodating arbitrary growth and shrinkage in a data structure that is an attractive alternative to linked lists. As with linked lists, The idea is to modify the array implementation to dynamically adjust the size of the array a[] so that it is (i) both sufficiently large to hold all of the items and (ii) not so large as to waste an excessive amount of space. Program DoublingStackOfStrings.java is a modification of ArrayStackOfStrings.java that achieves these objectives.

First, in push(), we check whether the array is too small. In particular, we check whether there is room for the new item in the array by checking whether the stack size N is equal to the array size a.length. If not, we just insert it with a[N++] = item as before; if so, we double the size of the array, by creating a new array of twice the size, copying the stack items to the new array, and resetting the a[] instance variable to reference the new array. Similarly, in pop(), we begin by checking whether the array is too large, and we halve its size if that is the case.

Pushdown stack

Parameterized data types.

We have developed one stack implementation that allows us to build a stack of one particular type (String). In other applications we might need a stack of integers or a stack of oranges or a queue of customers.

Autoboxing.

We have designed our stacks so that they can store any generic object type. We now describe the Java language feature, known as auto-boxing and auto-unboxing, that enables us to reuse the same code with primitive types as well. Associated with each primitive type, e.g. int, is a full blown object type, e.g., Integer. When we assign a primitive to the corresponding object type (or vice versa), Java automatically performs the transformation. This enables us to write code like the following.
Stack<Integer> stack = new Stack<Integer>();
stack.push(17);            // auto-boxing   (converts int to Integer)
int a = stack.pop();       // auto-unboxing (converts Integer to int)

The value 17 is automatically cast to be of type Integer when we pass it to the push() method. The pop() method returns an Integer, and this value is cast to an int when we assign it to the variable a. We should be aware of what is going on behind the scenes since this can affect performance.

Java supplies built-in wrapper types for all of the primitive types: Boolean, Byte, Character, Double, Float, Integer, Long, and Short. These classes consist primarily of static methods (e.g., Integer.parseInt(), Integer.reverse()), but they also include some non-static methods (compareTo(), equals(), doubleValue()).

Queue.

A queue supports the insert and remove operations using a FIFO discipline. By convention, we name the queue insert operation enqueue and the remove operation dequeue. Lincoln tunnel. Student has tasks that must be completed. Put on a queue. Do the tasks in the same order that they arrive.

LIFO queue

public class Queue<Item> {
   public boolean isEmpty();
   public void enqueue(Item item);
   public Item dequeue();
}

Iteration.

Sometimes the client needs to access all of the items of a collection, one at a time, without deleting them. To maintain encapsulation, we do not want to reveal the internal representation of the queue (array or linked list) to the client. "Decouple the thing that needs to traverse the list from the details of getting each element from it." We solve this design challenge by using Java's java.util.Iterator interface:
public interface Iterator<Item> {
    boolean hasNext();
    Item next();
    void remove();      // optional
}
That is, any data type that implements the Iterator interface promises to implement two methods: hasNext() and next(). The client uses these methods to access the list elements one a time using the following idiom.
Queue<String> queue = new Queue<String>();
...
Iterator<String> i = queue.iterator();
while (i.hasNext()) {
   String s = i.next();
   StdOut.println(s);
}

Stack and queue applications.

Stacks and queues have numerous useful applications.

Q + A.

Q. When do I use new with Node?

A. Just as with any other class, you should only use new when you want to create a new Node object (a new element in the linked list). You should not use new to create a new reference to an existing Node object. For example, the code

Node oldfirst = new Node(); 
oldfirst = first; 
creates a new Node object, then immediately loses track of the only reference to it. This code does not result in an error, but it is a bit untidy to create orphans for no reason.

Q. Why declare Node as a nested class? Why private?

A. By declaring the subclass Node to be private we restrict access to methods within the enclosing class. One characteristic of a private nested class is that its instance variables can be directly accessed from within the enclosing class, but nowhere else, so there is no need to declare them public or private. Note : A nested class that is not static is known as an inner class, so technically our Node classes are inner classes, though the ones that are not generic could be static.

Q. Why does javac LinkedStackOfStrings.java creates a file LinkedStackOfStrings$Node.class as well as LinkedStackOfStrings.class?

A. That file is for the nested class Node. Java's naming convention is to use $ to separate the name of the outer class from the nested class.

Q. Should a client be allowed to insert null items onto a stack or queue? A. This question arises frequently when implementing collections in Java. Our implementation (and Java's stack and queue libraries) do permit the insertion of null values.

Q. Are there Java libraries for stacks and queues?

A. Yes and no. Java has a built in library called java.util.Stack, but you should avoid using it when you want a stack. It has several additional operations that are not normally associated with a stack, e.g., getting the ith element. It also allows adding an element to the bottom of the stack (instead of the top), so it can implement a queue! Although having such extra operations may appear to be a bonus, it is actually a curse. We use data types not because they provide every available operation, but rather because they allow us to precisely specify the operations we need. The prime benefit of doing so is that the system can prevent us from performing operations that we do not actually want. The java.util.Stack API is an example of a wide interface, which we generally strive to avoid.

Q. I want to use an array representation for a generic stack, but code like the following will not compile. What is the problem?

private Item[] a = new Item[max]; 
oldfirst = first; 

A. Good try. Unfortunately, creating arrays of generics is not allowed in Java 1.5. Experts still are vigorously debating this decision. As usual, complaining too loudly about a language feature puts you on the slippery slope towards becoming a language designer. There is a way out, using a cast: you can write:

private Item[] a = (Item[]) new Object[max]; 
oldfirst = first; 
The underlying cause is that arrays in Java are covariant, but generics are not. In other words, String[] is a subtype of Object[], but Stack<String> is not a subtype of Stack<Object>. To get around this defect, you need to perform an unchecked cast as in DoublingStack.java. Many programmers consider covariant arrays to be a defect in Java's type system (and this resulted in the need for "reifiable types" and "type erasure"). However, in a world without generics, covariant arrays are useful, e.g., to implement Arrays.sort(Comparable[]) and have it be callable with an input array of type String[].

Q. Can I use the foreach construction with arrays?

A. Yes (even though arrays do not implement the Iterator interface). The following prints out the command-line arguments:

public static void main(String[] args) {
   for (String s : args)
      StdOut.println(s);
} 

Q. Is iterating over a linked list more efficient with a loop or recursion?

A. An optimizing compiler will likely translate a tail-recursive function into the equivalent loop, so there may be no observable performance overhead of using recursion.

Q. How does auto-boxing handle the following code fragment?

Integer a = null;
int b = a;

A. It results in a run-time error. Primitive type can store every value of their corresponding wrapper type except null.

Q. Why does the first group of statements print true, but the second two print false?

Integer a1 = 100;
Integer a2 = 100;
System.out.println(a1 == a2);   // true

Integer b1 = new Integer(100);
Integer b2 = new Integer(100);
System.out.println(b1 == b2);   // false

Integer c1 = 150;
Integer c2 = 150;
System.out.println(c1 == c2);   // false

A. The second prints false because b1 and b2 are references to different Integer objects. The first and third code fragments rely on autoboxing. Surprisingly the first prints true because values between -128 and 127 appear to refer to the same immutable Integer objects (presumably there is a pool of them that are reused), while Java creates new objects for each integer outside this range. Lesson: as usual, don't use == to compare whether two objects have the same value.

Q. Are generics solely for auto-casting?

A. No, but this will be the only thing we use them for. This is known as "pure generics" or "concrete parameterized types." Concrete parameterized types work almost like normal types with a few exceptions (array creation, exception handling, with instanceof, and in a class literal). More advanced uses of generics, including "wildcards", are are useful for handling subtypes and inheritance. Here is a Java generics tutorial.

Q. Why do I get an incompatible types compile-time error with the following code?

Stack stack = new Stack<String>();
stack.push("Hello");
String s = stack.pop();

A. You forgot to specify the concrete type when declaring stack. It should be Stack<String>.

Q. Why do I get a uses unchecked or unsafe operations compile-time warning with the following code?

Stack<String> stack = new Stack();
stack.push("Hello");
String s = stack.pop();

A. You forgot to specify the concrete type when calling the constructor. It should be new Stack<String>().


Exercises

  1. Add a method isFull() to ArrayStackOfStrings.java.
  2. Give the output printed by java ArrayStackOfStrings 5 for the input
    it was - the best - of times - - - it was - the - -  
    
  3. Suppose that a client performs an intermixed sequence of (stack) push and pop operations. The push operations put the integers 0 through 9 in order on to the stack; the pop operations print out the return value. Which of the following sequence(s) could not occur?
    (a)  4 3 2 1 0 9 8 7 6 5
    (b)  4 6 8 7 5 3 2 9 0 1 
    (c)  2 5 6 7 4 8 9 3 1 0
    (d)  4 3 2 1 0 5 6 7 8 9
    (e)  1 2 3 4 5 6 9 8 7 0 
    (f)  0 4 6 5 3 8 1 7 2 9 
    (g)  1 4 7 9 8 6 5 3 0 2 
    (h)  2 1 4 3 6 5 8 7 9 0 
    
  4. Write a stack client Reverse.java that reds in strings from standard input and prints them in reverse order.
  5. Assuming that standard input has some unknown number N of double values. Write a method that reads all the values and returns an array of length N containing them, in the other they appear on standard input.
  6. Write a stack client Parentheses.java that reads in a text stream from standard input and uses a stack to determine whether its parentheses are properly balanced. For example, your program should print true for [()]{}{[()()]()} and false for [(]). Hint : Use a stack.
  7. What does the following code fragment print when N is 50? Give a high-level description of what the code fragment does when presented with a positive integer N.
    Stack stack = new Stack();
    while (N > 0) {
       stack.push(N % 2);
       N = N / 2;
    }
    while (!stack.isEmpty())
        StdOut.print(stack.pop());
    StdOut.println();
    

    Answer: prints the binary representation of N (110010 when N is 50).

  8. What does the following code fragment do to the queue q?
    Stack stack = new Stack();
    while (!q.isEmpty())
       stack.push(q.dequeue());
    while (!stack.isEmpty())
       q.enqueue(stack.pop());
    
  9. Add a method peek() to Stack.java that returns the most recently inserted element on the stack (without popping it).
  10. Give the contents and size of the array for DoublingStackOfStrings with the input
    it was - the best - of times - - - it was - the - - 
    
  11. Add a method length() to Queue.java that returns the number of elements on the queue. Hint: Make sure that your method takes constant time by maintaining an instance variable N that you initialize to 0, increment in enqueue(), decrement in dequeue(), and return in length().
  12. Draw a memory usage diagram in the style of the diagrams in Section 4.1 for the three-node example used to introduce linked lists in this section.
  13. Write a program that takes from standard input an expression without left parentheses and prints the equivalent infix expression with the parentheses inserted. For example, given the input
     1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) ) 
    
    your program should print
     ( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) 
    
  14. Write a filter InfixToPostfix.java that converts an arithmetic expression from infix to postfix.
  15. Write a program EvaluatePostfix.java that takes a postfix expression from standard input, evaluates it, and prints the value. (Piping the output of your program from the previous exercise to this program gives equivalent behavior to Evaluate.java.)
  16. Suppose that a client performs an intermixed sequence of (queue) enqueue and dequeue operations. The enqueue operations put the integers 0 through 9 in order on to the queue; the dequeue operations print out the return value. Which of the following sequence(s) could not occur?
    (a)  0 1 2 3 4 5 6 7 8 9 
    (b)  4 6 8 7 5 3 2 9 0 1 
    (c)  2 5 6 7 4 8 9 3 1 0 
    (d)  4 3 2 1 0 5 6 7 8 9 
    
  17. Write an iterable Stack client that has a static methods copy() that takes a stack of strings as argument and returns a copy of the stack. Note: This ability is a prime example of the value of having an iterator, because it allows development of such functionality without changing the basic API.
  18. Develop a class DoublingQueueOfStrings.java that implements the queue abstraction with a fixed-size array, and then extend your implementation to use array doubling to remove the size restriction.
  19. Write a Queue.java client that takes a command-line argument k and prints the kth from the last string found on standard input.
  20. (For the mathematically inclined.) Prove that the array in DoublingStackOfStrings.java is never less than one-quarter full. Then prove that, for any DoublingStackOfStrings client, the total cost of all of the stack operations divided by the number of operations is a constant.
  21. Modify MD1Queue.java to make a program MM1Queue.java that simulates a queue for which both the arrival and service times are Poisson processes. Verify Little's law for this model.
  22. Develop a class StackOfInts.java that uses a linked-list representation (but no generics). Write a client that compares the performance of your implementation withStack<Integer> to determine the performance penalty from autoboxing on your system.


Linked List Exercises

  1. Write a method delete() that takes an int argument k and deletes the kth element in a linked list, if it exists.

    Solution.

    // we assume that first is a reference to the first Node in the list
    public void delete(int k) {
        if (k <= 0) throw new RuntimeException("Invalid value of k");
    
        // degenerate case - empty linked list
        if (first == null) return;
    
        // special case - removing the first node
        if (k == 1) {
            first = first.next;
            return;
        }
    
        // general case, make temp point to the (k-1)st node
        Node temp = first;
        for (int i = 2; i < k; i++) {
            temp = temp.next;
            if (temp == null) return;   // list has < k nodes
        }
    
        if (temp.next == null) return;  // list has < k nodes
    
        // change temp.next to skip kth node
        temp.next = temp.next.next;
    }
    
  2. Write a method find() that takes a linked list and a string key as arguments and returns true if some node in the list has key as its item field, false otherwise.
  3. Suppose x is a linked-list node. What is the effect of the following code fragment?
    x.next = x.next.next;
    

    Answer: Deletes from the list the node immediately following x.

  4. Suppose that x is a linked-list node. What is the effect of the following code fragment?
    t.next = x.next;
    x.next = t;     
    

    Answer: Inserts node t immediately after node x.

  5. Why does the following code fragment not have the same effect as in the previous question?
    x.next = t;
    t.next = x.next;
    

    Answer: When it comes time to update t.next, x.next is no longer the original node following x, but is instead t itself!

  6. Write a method removeAfter() that takes a linked-list Node as argument and removes the node following the given one (and does nothing if the argument or the next field in the argument node is null).
  7. Write a method insertAfter() that takes two linked-list Node arguments and inserts the second after the first on its list (and does nothing if either argument is null).
  8. Write a method remove() that takes a linked list and a string key as arguments and removes all of the nodes in the list that have key as its item field.
  9. Write a method max() that a reference to the first node in a linked list as argument and returns the value of the maximum key in the list. Assume that all keys are positive integers, and return 0 if the list is empty.
  10. Develop a recursive solution to the previous exercise.
  11. Write a recursive method to print the elements of a linked list in reverse order. Do not modify any of the links. Easy: Use quadratic time, constant extra space. Also easy: Use linear time, linear extra space. Not so easy: Develop a divide-and-conquer algorithm that uses linearithmic time and logarithmic extra space.
  12. Write a recursive method to randomly shuffle the elements of a linked list by modifying the links. Easy: Use quadratic time, constant extra space. Not so easy: Develop a divide-and-conquer algorithm that uses linearithmic time and logarithmic extra space.

Creative Exercises

  1. Deque A double-ended queue or deque (pronounced deck) is a combination of a stack and and a queue. It stores a parameterized collection of items and supports the following API:

    Deque API

    Write a data type Deque.java that implements the deque API using a singly linked list.

  2. Random queue. Create an abstract data type RandomizedQueue.java that supports the following operations: isEmpty(), insert(), random(), and removeRandom(), where the deletion operation deletes and returns a random object. Hint: maintain an array of objects. To delete an object, swap a random object (indexed 0 through N-1) with the last object (index N-1). Then, delete and return the last object.

    Randomized queue API
  3. Listing files. A Unix directory is a list of files and directories. Program Directory.java takes the name of a directory as a command line parameter and prints out all of the files contained in that directory (and any subdirectories) in level-order. It uses a queue.
  4. Josephus problem Program Josephus.java uses a queue to solve the Josephus problem.
  5. Delete ith element. Create an ADT that supports the following operations: isEmpty, insert, and remove(int i), where the deletion operation deletes and returns the ith least recently added object on the queue. Do it with an array, then do it with a linked list. See Exercise XYZ for a more efficient implementation that uses a BST.
  6. Dynamic shrinking. With the array implementations of stack and queue, we doubled the size of the array when it wasn't big enough to store the next element. If we perform a number of doubling operations, and then delete alot of elements, we might end up with an array that is much bigger than necessary. Implement the following strategy: whenever the array is 1/4 full or less, shrink it to half the size. Explain why we don't shrink it to half the size when it is 1/2 full or less.
  7. Ring buffer. A ring buffer or circular queue is a FIFO data structure of a fixed size N. It is useful for transferring data between asynchronous processes or storing log files. When the buffer is empty, the consumer waits until data is deposited; when the buffer is full, the producer waits to deposit data. A ring buffer has the following methods: isEmpty(), isFull(), enqueue(), and dequeue(). Write an generic data type RingBuffer using an array (with circular wrap-around for efficiency).
  8. Merging two sorted queues. Given two queues with strings in ascending order, move all of the strings to a third queue so that the third queues ends up with the strings in ascending order.
  9. Mergesort. Given N strings, create N queues, each containing one of the strings. Create a queue of the N queues. Then repeatedly apply the sorted merging operation to the first two queues and reinsert the merged queue at the end. Repeat until the queue of queues contains only one queue.
  10. Queue with two stacks. Show how to implement a queue using two stacks. Hint: If you push elements onto a stack and then pop them all, they appear in reverse order. If you repeat this process, they're now back in order.
  11. Move-to-front. Read in a sequence of characters from standard input and maintain the characters in a linked list with no duplicates. When you read in a previously unseen character, insert it at the front of the list. When you read in a duplicate character, delete it from the list and re-insert it at the beginning. This move-to-front strategy is useful for caching and data compression (Burrows-Wheeler) algorithms where items that have been recently accessed are more likely to be re-accessed.
  12. Text editor buffer. Implement an ADT for a buffer in a text editor. It should support the following operations:
    • insert(c): insert character c at cursor
    • delete(): delete and return the character at the cursor
    • left(): move the cursor one position to the left
    • right(): move the cursor one position to the right
    • get(i): return the ith character in the buffer

    Hint: use two stacks.

  13. Topological sort. You have to sequence the order of N jobs on a processor. Some of the jobs must complete before others can begin. Specifically, you are given a list of order pairs of jobs (i, j). Find a sequence of the jobs such that for each pair (i, j) job i is scheduled before job j. Use the following algorithm.... For each node, maintain a list of outgoing arcs using a queue. Also, maintain the indegree of each node. Finally, maintain a queue of all nodes whose indegree is 0. Repeatedly delete a node with zero indegree, and delete all of its outgoing arcs. Write a program TopologicalSorter.java to accomplish this.

    Alternate application: prerequisites for graduating in your major. Must take COS 126 and COS 217 before COS 341, etc. Can you graduate?

  14. PERT / CPM. Modify the previous exercise to handle weights (i, j, w) means job i is scheduled at least w units of time before job j.
  15. Set of integers. Create a data type that represents a set of integers (no duplicates) between 0 and N-1. Support add(i), exists(i), remove(i), size(), intersect, difference, symmetricDifference, union, isSubset, isSuperSet, and isDisjointFrom.
  16. Indexing a book. Write a program that reads in a text file from standard input and compiles an alphabetical index of which words appear on which lines, as in the following input. Ignore case and punctuation. Similar to FrequencyCount, but for each word maintain a list of location on which it appears.

    Reverse a linked list. Write a function that takes the first Node in a linked list, reverse it, and returns the first Node in the resulting linked list.

    Solution. To accomplish this, we maintain references to three consecutive nodes in the linked list, reverse, first, and second. At each iteration we extract the node first from the original linked list and insert it at the beginning of the reversed list. We maintain the invariant that first is the first node of what's left of the original list, second is the second node of what's left of the original list, and reverse is the first node of the resulting reversed list.

    Reverse a linked list
    public static Node reverse(Node list) {
       Node first   = list;
       Node reverse = null;
       while (first != null) {
          Node second = first.next;
          first.next  = reverse;
          reverse     = first;
          first       = second;
       }
       return reverse;
    }
    

    When writing code involving linked lists, we must always be careful to properly handle the exceptional cases (when the linked list is empty, when the list has only one or two nodes) and the boundary cases (dealing with the first or last items). This is usually the trickiest part, as opposed to handling the normal cases.

    Recursive solution. Assuming the linked list has N elements, we recursively reverse the last N-1 elements, then carefully append the first element to the end.

    public Node reverse(Node first) {
        if (first == null || first.next == null) return first;
        Node second = first.next;
        Node rest = reverse(second);
        second.next = first;
        first.next  = null;
        return rest;
    }
    

Web Exercises

  1. Quote. Develop a data type Quote.java that implements the following API:
    public class Quote
    -------------------------------------------------------------------------------
                 Quote()                      create an empty quote
            void addWord(String w)            add w to the end of the quote
             int count()                      return number of words in quote
          String getWord(int i)               return the ith word starting at 1
            void insertWord(int i, String w)  add w after the ith word
          String toString()                   return the entire quote as a String
    
    To do so, define a nested class Card that holds one word of the quote and a link to the next word:
    private class Card {
        private String word;
        private Card next;
    
        public Card(String word) {
            this.word = word;
            this.next = null;
        }
    }
    
  2. Circular quote. Repeated the previous exercise, but write a program CircularQuote.java that use a circular linked list.
  3. Write a recursive function that takes as input a queue, and rearranges it so that it is in reverse order. Hint: dequeue() the first element, recursively reverse the queue, and the enqueue the first element.
  4. Add a method Item[] multiPop(int k) to Stack that pops k elements from the stack and returns them as an array of objects.
  5. Add a method Item[] toArray() to Queue that returns all N elements on the queue as an array of length N.
  6. What does the following code fragment do?
    IntQueue q = new IntQueue();
    q.enqueue(0);
    q.enqueue(1);
    for (int i = 0; i < 10; i++) {
        int a = q.dequeue();
        int b = q.dequeue();
        q.enqueue(b);
        q.enqueue(a + b);
        System.out.println(a);
    }
    

    Fibonacci

  7. What data type would you choose to implement an "Undo" feature in a word processor?
  8. Suppose you have a single array of size N and want to implement two stacks so that you won't get overflow until the total number of elements on both stacks is N+1. How would you proceed?
  9. Suppose that you implemented push in the linked list implementation of StackList with the following code. What is the mistake?
    public void push(Object value) {
       Node second = first;
       Node first = new Node();
       first.value = value;
       first.next = second;
    }
    

    Answer: By redeclaring first, you are create a new local variable named first, which is different from the instance variable named first.

  10. Copy a queue. Create a new constructor so that LinkedQueue r = new LinkedQueue(q) makes r reference a new and independent queue. Hint: delete all of the elements from q and add to both q and this.
  11. Copy a stack. Create a new constructor for the linked list implementation of Stack.java so that Stack t = new Stack(s) makes t reference a new and independent copy of the stack s. You should be able to push and pop from s or t without influencing the other.

    Should it work if argument is null? Recursive solution: create a copy constructor for a Node and use this to create the new stack.

    Node(Node x) {
       item = x.item;
       if (x.next != null) next = new Node(x.next);
    }
    
    public Stack(Stack s) { first = new Node(s.first); }
    

    Nonrecursive solution (untested):

    Node(Node x, Node next) { this.x = x; this.next = next; }
    
    public Stack(Stack s) {
       if (s.first != null) {
          first = new Node(s.first.value, s.first.next) {
          for (Node x = first; x.next != null; x = x.next)
             x.next = new Node(x.next.value, x.next.next);
       }
    }
    
  12. Stack with one queue. Show how to implement a stack using one queue. Hint: to delete an item, get all of the elements on the queue one at a time, and put them at the end, except for the last one which you should delete and return.
  13. Listing files with a stack. Write a program that takes the name of a directory as a command line argument, and prints out all of the files contained in this directory and any subdirectories. Also prints out the file size (in bytes) of each file. Use a stack instead of a queue. Repeat using recursion and name your program DirectoryR.java. Modify DirectoryR.java so that it prints out each subdirectory and its total size. The size of a directory is equal to the sum of all of the files it contains or that its subdirectories contain.
  14. Stack + max. Create a data structure that efficiently supports the stack operations (pop and push) and also return the maximum element. Assume the elements are integers or reals so that you can compare them. Hint: use two stacks, one to store all of the elements and a second stack to store the maximums.
  15. Tag systems. Write a program that reads in a binary string from the command line and applies the following (00, 1101) tag-system: if the first bit is 0, delete the first three bits and append 00; if the first bit is 1, delete the first three bits and append 1101. Repeat as long as the string has at least 3 bits. Try to determine whether the following inputs will halt or go into an infinite loop: 10010, 100100100100100100. Use a queue.

  16. Reverse. Write a method to read in an arbitrary number of strings from standard input and print them in reverse order.
    public static void main(String[] args) {
       Stack<String> stack = new Stack<String>();
       while (!StdIn.isEmpty()) {
          String s = StdIn.readString();
          stack.push(s);
       }
       while (!stack.isEmpty()) {
          String s = stack.pop();
          StdOut.println(s);
       }
    }
    
  17. Add a method int size() to DoublingStack.java and Stack.java that returns the number of elements on the stack.
  18. Add a method reverse() to Queue that reverses the order of the elements on the queue.
  19. Add a method copy() to ArrayStackOfStrings.java