CHAPTER 3
Lists, Stacks, and Queues
3.1 public static <AnyType> void printLots(List<AnyType> L,
List<Integer> P)
{
Iterator<AnyType> iterL = L.iterator();
Iterator<Integer> iterP = P.iterator();
}
}
3.2 (a) For singly linked lists:
// beforeP is the cell before the two adjacent cells that are to be
swapped.
// Error checks are omitted for clarity.
(b) For doubly linked lists:
// p and afterp are cells to be switched. Error checks as before.
}
3.3 public boolean contains( AnyType x )
}
3.4 public static <AnyType extends Comparable<? super AnyType>>
void intersection(List<AnyType> L1, List<AnyType> L2,
List<AnyType> Intersect)
{
ListIterator<AnyType> iterL1 = L1.listIterator();
ListIterator<AnyType> iterL2 = L2.listIterator();
AnyType itemL1=null, itemL2=null;
3.5 public static <AnyType extends Comparable<? super AnyType>>
void union(List<AnyType> L1, List<AnyType> L2,
List<AnyType> Result)
{
ListIterator<AnyType> iterL1 = L1.listIterator();
ListIterator<AnyType> iterL2 = L2.listIterator();
}
else if ( compareResult < 0 )
{
Result.add(itemL1);
itemL1 = iterL1.hasNext()?iterL1.next():null;
}
3.6 A basic algorithm is to iterate through the list, removing every Mth item. This can be improved by two
observations. The first is that an item M distance away is the same as an item that is only M mod N away.
direction. This improvement is useful when M is more than N/2 (half the list). The solution shown below uses
these two observations. Note that the list size changes as items are removed. The worst case running time is
O(Nmin(M, N)), though with the improvements given the algorithm might be significantly faster. If M = 1,
the algorithm is linear.
public static void pass(int m, int n)
for (i=0; i<n; i++)
{
mPrime = m % numleft;
if (mPrime <= numLeft/2)
{
if (iter.hasNext())
item = iter.next();
}
}
System.out.print(“Removed ” + item + ” “);
iter.remove();
3.7 O(N2). The trim method reduces the size of the array, requiring each add to resize it. The resize takes O(N)
time, and there are O(N) calls.
3.8 (a) Because the remove call changes the size, which would affect the loop.
3.9 public void addAll( Iterable<? extends AnyType> items )
{
3.10 public void removeAll( Iterable<? extends AnyType> items )
{
AnyType item, element;
Iterator<? extends AnyType> iterItems = items.iterator();
This runs in O(MN), where M is the size of the items, and N is the size of the list.
3.11 import java.util.*;
public class SingleList
{
SingleList()
{ init(); }
boolean add( Object x )
{
if (!contains(x))
return false;
else
{
Node<Object> p = head.next;
Node<Object> trailer = head;
while (!p.data.equals(x))
{
Node<Object> p = head.next;
while (p != null)
{
System.out.print(p.data + ” “);
p = p.next;
}
System.out.println();
}
return true;
else
p = p.next;
private Node<Object> head;
private int theSize;
private class Node<Object>
{
Node()
{
this(null, null);
}
}
3.12 import java.util.*;
public class SingleListSorted
{
SingleListSorted()
{ init(); }
trailer.next = new Node<Comparable>(x);
trailer.next.next = p;
theSize++;
}
return true;
}
boolean remove(Comparable x)
{
}
int size()
{ return theSize; }
void print()
}
boolean contains( Comparable x )
{
Node<Comparable> p = head.next;
while (p != null && p.data.compareTo(x) <= 0)
{
if (x.equals(p.data))
head = new Node<Comparable>();
head.next = null;
}
private Node<Comparable> head;
private int theSize;
private class Node<Comparable>
{
Node()
{
}
3.13 public java.util.Iterator<AnyType> iterator()
{ return new ArrayListIterator( ); }
public java.util.ListIterator<AnyType> listIterator()
{ return new ArrayListIterator( ); }
}
public boolean hasPrevious()
{ return current > 0; }
public AnyType previous()
{
if ( !hasPrevious() )
throw new java.util.NoSuchElementException();
backwards = true;
return theItems[ –current ];
}
public void add( AnyType x )
{ MyArrayList.this.add( current++, x ); }
public void remove()
{
}
}
3.14 public java.util.Iterator<AnyType> iterator()
{
return new LinkedListIterator( );
}
public java.util.ListIterator<AnyType> listIterator()
{
return new LinkedListIterator( );
}
current = current.next;
okToRemove = true;
return nextItem;
}
}
public void add( AnyType x )
{
if ( modCount != expectedModCount )
throw new java.util.ConcurrentModificationException();
MyLinkedList.this.addBefore( current.next, x );
}
public void remove()
{
if( modCount != expectedModCount )
throw new java.util.ConcurrentModificationException( );
if( !okToRemove )
throw new IllegalStateException( );
}
}
}
3.16 Iterator<AnyType> reverseIterator()
{ return new ArrayListReverseIterator( ); }
private class ArrayListReverseIterator implements
java.util.Iterator<AnyType>
{
}
3.18 public void addFirst( AnyType x )
{ addBefore( beginMarker.next, x ); }
public void addLast( AnyType x )
3.19 Without head or tail nodes the operations of inserting and deleting from the end becomes an O(N) operation
3.20 (a) The advantages are that it is simpler to code, and there is a possible saving if deleted keys are
subsequently reinserted (in the same place). The disadvantage is that it uses more space, because each cell
needs an extra bit (which is typically a byte), and unused cells are not freed.
3.22 The following function evaluates a postfix expression, using + ,–, *, /, and ^ ending in =. It requires spaces
between all operators and =.
}
catch (Exception e)
{
isNumber = false;
}
if (isNumber)
s.push(result);
else
{
}
}
3.23 (a, b) This function will read in from standard input an infix expression of single lower case characters and
the operators +, –, /, *, ^, and ( ), and outputs a postfix expression.
static void InFixToPostFix()
{
Stack<Character> s = new Stack<Character>();
String expression;
{
case ’)’: while ( !s.empty() && s.peek() != ’(’ )
{ System.out.print(s.pop() + ” “); }
s.pop();
break;
case ’(’: s.push(token);
break;
case ’^’: while ( !s.empty() && !(s.peek() == ’^’ ||
}
3.24 Two stacks can be implemented in an array by having one grow from the low end of the array up, and the
other from the high end down.
3.25 (a) Let E be our extended stack. We will implement E with two stacks. One stack, which we’ll call S, is used
to keep track of the push and pop operations, and the other M, keeps track of the minimum. To implement
3.26 Three stacks can be implemented by having one grow from the bottom up, another from the top down and a
third somewhere in the middle growing in some (arbitrary) direction. If the third stack collides with either of
the other two, it needs to be moved. A reasonable strategy is to move it so that its center (at the time of the
move) is halfway between the tops of the other two stacks.
3.27 Stack space will not run out because only 49 calls will be stacked. However, the running time is exponential,
as shown in Chapter 2, and thus the routine will not terminate in a reasonable amount of time.
3.28 Since the LinkedList class supports adding and removing from the first and end of the list, the Deque
class shown below simply wraps these operations.
}
3.29 Reversal of a linked list can be done recursively using a stack, but this requires O(N) extra space. The
following solution is similar to strategies employed in garbage collection algorithms. At the top of the while
loop, the list from the start to previousPos is already reversed, whereas the rest of the list, from currentPos to
the end is normal. This algorithm uses only constant extra space. This solution reverses the list which can
then be printed in reverse order.
void reverseList()
{
3.30 (c) This follows well-known statistical theorems. See Sleator and Tarjan’s paper in Chapter 11 for references.
3.31 public class SingleStack<AnyType>
{
SingleStack()
{
return head.data;
}
void pop()
{
head = head.next;
}
3.32 public class SingleQueue<AnyType>
{
SingleQueue()
{
front = null;
rear = null;
}
void enqueue(AnyType x)
{
private class Node<AnyType>
{
Node()
{ this(null, null); }
3.33 import java.util.*;
public class SingleQueueArray<AnyType>
{
SingleQueueArray()
{ this(101); } // note: actually holds one less than given size
SingleQueueArray(int s)
rear = (rear + 1) % max Size;
}
}
AnyType dequeue()
return temp;
}
}
3.34 (b) Use two iterators p and q, both initially at the start of the list. Advance p one step at a time, and q two
steps at a time. If q reaches the end there is no cycle; otherwise, p and q will eventually catch up to each other
in the middle of the cycle.
3.35 (a) Does not work in constant time for insertions at the end.