12.3

public int pop ()
{
   if (top == null)
      throw new RuntimeException("pop: empty stack");
   else
   {
      int result = top.info;
      top = top.link;
      return result;
   }
}

public boolean isEmpty ()
{
   if (top == null)
      return true;
   else
      return false;
}

public int peek ()
{
   if (rear == null)
      throw new RuntimeException("peek: empty queue");
   else
      return front.info;
}

public int dequeue ()
{
   if (rear == null)
      throw new RuntimeException("dequeue: empty queue");
   else
   {
      int result = front.info;
      front = front.link;
      return result;
   }
}

It would be possible to insert items efficiently since they are simply added to the end of the queue. Simply have the new item’s link point to the current ’rear’ item. It would not, however, be possible to efficiently delete items. In order to delete the first item, head must be moved to the second item and the second item’s link must be set to null. In order to access the second item’s link, the entire list must be traversed starting from the rear (since the links are facing from rear to front), and this is not very efficient, especially with long lists.

1. 123, 132, 213, 231, 321
2. 1234, 1243, 1324, 1342, 1432, 2134, 2143, 2314, 2341, 2431, 3214, 3241, 3421, 4321