Convert Queue Dequeue to Link list format

[Jeremy Tan]

Hi I'm new to data structures and I just bought a book in Amazon called Object-Oriented Data Structures Using Java by Nell Dale to accompany the required book my professor gave to us. We just recently covered linklist, and I'm trying to convert some of the examples in the book. One particular question I'm stuck with is converting the War game's queue dequeue class into a custom made linklist.

Here is the example code I got from the authors website:

War Game pp:

// WarGameApp.java         by Dale/Joyce/Weems                Chapter 5

import java.util.Scanner;

public class WarGameApp 
{
  public static void main(String[] args)
  {
    Scanner conIn = new Scanner(System.in);

    WarGame game;

    int numGames;         // number of games to simulate
    int maxNumBattles;    // maximum number of battles allowed for a game
    
    int numDiscont = 0;   // number of dicontinued games
    int numCompleted = 0; // number of completed games
    
    int totBattles = 0;   // total number of battles so far in completed games

    System.out.println("How many games should be simulated? ");
    numGames = conIn.nextInt();
    
    System.out.println("What is the maximum number of battles per game? ");
    maxNumBattles = conIn.nextInt();
    
    game = new WarGame(maxNumBattles);

    for (int i = 0; i < numGames; i++)
    {
      if (game.play())
      {
        numCompleted = numCompleted + 1;
        totBattles = totBattles + game.getNumBattles();
      }
      else
        numDiscont = numDiscont + 1;
    }
    
    // Output results.
    System.out.println("Number of Games Simulated:    "+ numGames);
    System.out.println("Number of Discontinued Games: "+ numDiscont);
    System.out.println("Number of Completed Games:    "+ numCompleted);
    System.out.println();
    
    if (numCompleted > 0)
    {
      System.out.println("In the completed games");
      System.out.println("  Total Number of Battles "+ totBattles);
      System.out.println("  Average Number of Battles "+ totBattles/numCompleted);
    }
    
    System.out.println("\nProgram completed.");
  }
}

War Game:
[code=java]
//---------------------------------------------------------------------
// WarGame.java             by Dale/Joyce/Weems               Chapter 5
//
// Models the card game War. 
// Tracks how many battles are played.
//---------------------------------------------------------------------

import ch05.queues.*;
import support.*;      // for RankCardDeck

public class WarGame 
{
  BoundedQueueInterface<Integer> player1;   // player 1's hand
  BoundedQueueInterface<Integer> player2;   // player 2's hand

  int maxNumBattles;            // maximum number of battles allowed before
                                // game is discontinued

  int numBattles = 0;           // number of battles played in current game

  RankCardDeck deck;            // deck of cards

  BoundedQueueInterface<Integer> prize;  // cards for current battle
    
  static final int numCards = 52;  // number of cards in a deck
  
  public WarGame(int maxNumBattles)
  {
    this.maxNumBattles = maxNumBattles;
    deck = new RankCardDeck();
  }
       
  public int getNumBattles()
  {
    return numBattles;
  }
    
  public boolean play()
  // Simulates one game. If number of battles played 
  // reaches maxNumBattles, the game is discontinued.
  // Returns true if game finishes normally; returns false
  // if game is discontinued.
  {
    // instantiate players' hands
    player1 = new ArrayBndQueue<Integer>(numCards);
    player2 = new ArrayBndQueue<Integer>(numCards);
    
    // instantiate prize pile
    prize = new ArrayBndQueue<Integer>(numCards);
    
    boolean gameOver = false;  // becomes true when the game is over
    boolean gameOK = true;     // becomes false if game is discontinued
    
    // deal original hands
    deck.shuffle();
    while (deck.hasMoreCards())
    {
      player1.enqueue(deck.nextCard());
      if (deck.hasMoreCards())
        player2.enqueue(deck.nextCard());
    }  
    
    // play game until somebody runs out of cards or
    // reach the maximum number of battles
    numBattles = 0;
    while (!gameOver)
    {
      try
      {
        numBattles = numBattles + 1;
        battle();
      }
      catch (QueueUnderflowException exceptionVar)
      {
        gameOver = true;
      }
      
      if (numBattles == maxNumBattles)
      {
        gameOver = true;
        gameOK = false;
      }
    }
    return gameOK;
  }
  
  private void battle()
  // Models a battle between player1 and player2. If the battle
  // results in a war, three cards from each player are placed
  // in the prize queue and the battle is continued recursively.
  {
    // cards for this battle
    int p1card;
    int p2card;
    
    // get cards from players and place in prize queue
    p1card = player1.dequeue();
    prize.enqueue(p1card);
    p2card = player2.dequeue();
    prize.enqueue(p2card);
    
    // determine and handle result of battle
    if (p1card > p2card)           // player 1 wins
      while (!prize.isEmpty())
        player1.enqueue(prize.dequeue());
    else
    {
      if (p2card > p1card)         // player 2 wins
        while (!prize.isEmpty())
          player2.enqueue(prize.dequeue());
      else                        
      {
        // it's a war ...
        // each player places 3 cards in prize pile
        for (int i = 0; i < 3; i++)
        {
          prize.enqueue(player1.dequeue());
          prize.enqueue(player2.dequeue());
        }
        // now continue the battle to determine who wins prize
        battle();
      } 
    }
  }
}
[code=java]
Rank Deck:


//----------------------------------------------------------------------
// RankCardDeck.java        by Dale/Joyce/Weems                Chapter 5
//
// Models a deck of cards. 
// Returns a random card upon request.
// Cards are represented by rank only .. an integer between 0 and 12.
//----------------------------------------------------------------------

package support;

import java.util.Random;

public class RankCardDeck
{
  private static final int numCards = 52;
  
  protected int[] carddeck = new int[numCards];
  protected int curCardPos = 0;           // position of the next card to be dealt
  
  protected Random rand = new Random();   // to generate random numbers 

  public RankCardDeck()
  {
    for (int i = 0; i < numCards; i++)
      carddeck[i] = i / 4;     // there are 4 cards of each rank
  }

  public void shuffle()
  // Randomizes the order of the cards in the deck and resets the
  // position of the current card to card 0.
  {
    int randLoc;  // random location in card deck
    int temp;     // for swap of cards
    
    for (int i = (numCards - 1); i > 0; i--)
    {
      randLoc = rand.nextInt(i);  // random integer between 0 and i - 1
      temp = carddeck[randLoc];
      carddeck[randLoc] = carddeck[i];
      carddeck[i] = temp;
    }
   
    curCardPos = 0;
  }
  
  public boolean hasMoreCards()
  // Returns true if there are still cards left to be dealt; 
  // otherwise, returns false.
  {
    return (curCardPos != numCards);
  }
  
  public int nextCard()
  // Precondition:  curCardPos != numCards
  //
  // Models a card being dealt by returning an integer representing 
  // its rank and incrementing the position of the current card.
  {
    curCardPos = curCardPos + 1;
    return (carddeck[curCardPos - 1]);
  }
}
 

I'm not also sure how to convert ArrayBoundQueues and Bounded queue interface into link list. Any idea or example to help me jup start this problem?

[Campbell Ritchie]

Are they interfaces? Do you mean ArrayBlockingQueue? That is a class which implements the Queue interface and also can block a thread so as to help with the producre-consumer problem, which you can find about by googling.
A linked list can implement Queue, too, but it does not normally block threads awaiting the availability of objects.
I think they have their own classes, which you would have to find the details of from their website or API documentation. We can’t help any more without that information.

[Jeremy Tan]

Is this what you are looking for?

//---------------------------------------------------------------------------
// ArrayBndQueue.java          by Dale/Joyce/Weems                  Chapter 5
//
// Implements BoundedQueueInterface with an array to hold the queue elements.
//
// Two constructors are provided: one that creates a queue of a default
// capacity and one that allows the calling program to specify the capacity.
//---------------------------------------------------------------------------

package ch05.queues;

public class ArrayBndQueue<T> implements BoundedQueueInterface<T>
{
  protected final int DEFCAP = 100; // default capacity
  protected T[] queue;              // array that holds queue elements
  protected int numElements = 0;    // number of elements n the queue
  protected int front = 0;          // index of front of queue
  protected int rear;               // index of rear of queue

  public ArrayBndQueue() 
  {
    queue = (T[]) new Object[DEFCAP];
	 rear = DEFCAP - 1;
  }

  public ArrayBndQueue(int maxSize) 
  {
    queue = (T[]) new Object[maxSize];
	 rear = maxSize - 1;
  }

  public void enqueue(T element)
  // Throws QueueOverflowException if this queue is full;
  // otherwise, adds element to the rear of this queue.
  {  
    if (isFull())
      throw new QueueOverflowException("Enqueue attempted on a full queue.");
    else
    {
      rear = (rear + 1) % queue.length;
      queue[rear] = element;
      numElements = numElements + 1;
    }
  }

  public T dequeue()
  // Throws QueueUnderflowException if this queue is empty;
  // otherwise, removes front element from this queue and returns it.
  {   
    if (isEmpty())
      throw new QueueUnderflowException("Dequeue attempted on empty queue.");
    else
    {
      T toReturn = queue[front];
      queue[front] = null;
      front = (front + 1) % queue.length;
      numElements = numElements - 1;
      return toReturn;
    }
  }

  public boolean isEmpty()
  // Returns true if this queue is empty; otherwise, returns false
  {              
    return (numElements == 0);
  }

  public boolean isFull()
  // Returns true if this queue is full; otherwise, returns false.
  {              
    return (numElements == queue.length);
  }
}

//----------------------------------------------------------------------------
// QueueInterface.java           by Dale/Joyce/Weems                 Chapter 5
//
// Interface for a class that implements a queue of T.
// A queue is a "first in, first out" structure.
//----------------------------------------------------------------------------

package ch05.queues;

public interface QueueInterface<T>

{
  T dequeue() throws QueueUnderflowException;
  // Throws QueueUnderflowException if this queue is empty;
  // otherwise, removes front element from this queue and returns it.

  boolean isEmpty();
  // Returns true if this queue is empty; otherwise, returns false.
}

package ch05.queues;

public interface BoundedQueueInterface<T> extends QueueInterface<T>

{
  void enqueue(T element) throws QueueOverflowException;
  // Throws QueueOverflowException if this queue is full;
  // otherwise, adds element to the rear of this queue.

  boolean isFull();
  // Returns true if this queue is full; otherwise, returns false.
}

Here you go.

[Campbell Ritchie]

That is a common-or-garden queue based on a circular array. A circular array is not one that joins up with itself, but one where you go back to the beginning from the end. You can tell that from the use of the % operator.
It would be quite easy to build a queue atop a linked list, which would have identical functionality, except that there is no limit to the size of your queue. You would still have to throw Exceptions if the queue is empty.
To enqueue something, add it at the beginning of your linked list, and to dequeue something, remove the last item in the list.
I presume you know how to build your own linked list?