Problem #2

Problem: Write your own implementation of a queue data structure. The structure must support a constant time add and remove operations as well as a constant time concatenate. Note: a queue is runs under a first in first out (FIFO) algorithm.

Algorithm: The queue could be implemented in two ways: as a linked list or as an array. I choose to use the linked list approach. A linked list is a data structure that consists of a series of linked node classes. My node class consisted of 2 instance variables a string storing the item at the node and a pointer object to the next node in the sequence

Here is the code for my node class:

  class Node

  {

    String item;

    Node next;

  }

Pretty simple, no? I used this class to maintain a linked list.

http://www.cs.usfca.edu/~srollins/courses/cs112-f07/web/notes/linkedlists/ll2.gif

In order to make the linked list behave like a queue, I kept track of two pointer objects to the head and tail of the list. This way when calling the add function, the new item would be added to the tail of the list and then the tail would be update. If the remove function is called the item is removed from the head of the list and the head variable is updated. To add and remove simply involve pointer changes.

To handle the concat function in constant time, I took the lazy route...as we all know lazy is the best way to go. I simply set the next variable in the tail of the first queue to point to the head of the second queue. Then I updated the tail of the first queue to the second queue's tail. This effectively mashes the two queues together.

Full Code:

public class MyQueue

{

  // helper class for the queue

  class Node

  {

    String item;

    Node next;

  }

  

  private Node head = null;

  private Node tail = null;

  // keep track of the number of entries

  private int n = 0;

  

  // add the string to the end of the queue

  public void add(String s)

  {

    Node newNode = new Node();

    newNode.item = s;

    // if this is first entry set it to the head

    if (this.n == 0){

      this.head = newNode;

      this.tail = newNode;

    }

    else if (this.n == 1){

      this.head.next = newNode;

      this.tail = newNode;

    }

    else{

      // update the end of the queue

      this.tail.next = newNode;

      this.tail = newNode;

    }

    // update the number of items in the queue

    this.n++;

  }

  

  // remove and return the string at the head

  public String remove()

  {

    if (this.head == null)

      return null;

    String s = this.head.item;

    // update the head of the queue

    this.head = this.head.next;

    this.n--;

    // return the first string

    return s;

  }

  

  

  // concatenates another queue to this one

  public MyQueue concat(MyQueue other)

  {

    if (this.size() == 0){

      // if the queue is emtpy just set it equal to the other 

      this.tail = other.tail;

      this.head = other.head;

      this.n = other.n;

    }

    else{

      // connect the head of other to the tail of this

      this.tail.next = other.head;

      // update the size

      this.n =  this.n + other.size();

      // update the tail of this

      this.tail = other.tail;

    }

      // empty the other queue

      other.head = null;

      other.tail = null;

      return this;

  }

  

  

  // return the number of items in the queque

  public int size()

  {

    return this.n;

  }

}

Happy Coding!