Universidad Carlos III de Madrid

Solución

La solución se puede ver en el siguiente listado:

/*
 * LinkedStack.java
 *
 */

public class LinkedStack {

  class Node {
    Object elem;
    Node Next;

    public Node(Object o) {
      elem = o;
      Next = null;
    }
  }

  Node end;
  int size;

  public LinkedStack() {
    end = null;
    size = 0;
  }

  public void push(Object o) {
    Node new_node = new Node(o);
    if (end == null)
      end = new_node;
    else {
      new_node.Next = end;
      end = new_node;
    }
    size++;
  }; // inserts an object onto the stack

  public Object pop() {
    if (end == null)
      return null;
    ;
    Object o = end.elem;
    end = end.Next;
    size--;
    return o;
  }// Gets the object from the stack

  public boolean isEmpty() {

    return (size == 0);
  }

  public int size() {

    return size;
  }

  public Object end() {

    if (end == null)
      return null;
    else
      return end.elem;
  }

} // class LinkedStack

	  

Solución

La solución se puede ver en el siguiente listado:

	      /*
 * LinkedQueue.java
 *
 */

public class LinkedQueue {

  class Node {
    Object elem;
    Node Next;

    public Node(Object o) {
      elem = o;
      Next = null;
    }
  }

  Node first;
  Node end;
  int size;

  public LinkedQueue() {
    end = null;
    size = 0;
  }

  public void enqueue(Object o) {
    Node new_node = new Node(o);
    if (first == null) {
      first = new_node;
      end = new_node;
    } else {
      end.Next = new_node;
      end = new_node;
    }
    size++;
  }; // inserts an object onto the queue

  public Object dequeue() {
    if (first == null)
      return null;
    ;
    Object o = first.elem;
    first = first.Next;
    size--;
    return o;
  } // gets the object from the queue

  public boolean isEmpty() {
    return (size == 0);
  }

  public int size() {
    return size;
  }

  public Object first() {
    if (first == null)
      return null;
    else
      return first.elem;
  }

} // class LinkedQueue

	  

Solución

La solución se puede ver en el siguiente listado:

/**
 * <p>Universidad Carlos III de Madrid</p>
 *
 * @author Departamento de Ingenieria Telematica. UC3M.
 * @version 1.0
 */

/**
 * 
 * <p>
 * 'Playing' with double linked list
 * </p>
 * 
 * 
 * @author Departamento de Ingenieria Telematica. UC3M.
 * @version 1.0
 */

public class List {

  // nested class
  public class Node {
    Node next;
    Node previous;
    Object data;

    public Node(Node next, Object data) {
      this.next = next;
      this.data = data;
    }

    public Node(Object elem) {
      this(null, elem);
    }
  }

  private Node first;
  private Node currentPosition;

  /**
   * Increments current position -numPositions-
   */
  public void forward(int numPositions) {
    if (numPositions > 0 && first != null) {
      int positionsForward = numPositions;
      if (currentPosition == null) {
        currentPosition = first;
        positionsForward--;
      }
      while (currentPosition.next != null && positionsForward > 0) {
        currentPosition = currentPosition.next;
        positionsForward--;
      }
    }
  }

  /**
   * Inserts an object in --currentPosition-.
   */
  public void insert(Object data) {
    Node node = new Node(data);

    if (currentPosition == null) {
      // inserts in first node
      node.next = first;
      if (first != null) {
        first.previous = node;
      }
      first = node;
    } else {
      // the node isn't the first.
      node.next = currentPosition.next;
      node.previous = currentPosition;
      if (currentPosition.next != null) {
        currentPosition.next.previous = node;
      }
      currentPosition.next = node;
    }

    // updates current position
    currentPosition = node;
  }

  /**
   * Delete the node referenced by -currentPosition-.
   * 
   * @return The object to delete
   */
  public Object extract() {
    Object data = null;

    if (currentPosition != null) {
      data = currentPosition.data;

      // 'delete' the node
      if (first == currentPosition) {
        first = currentPosition.next;
      } else {
        currentPosition.previous.next = currentPosition.next;
      }

      if (currentPosition.next != null) {
        currentPosition.next.previous = currentPosition.previous;
      }

      // next position
      currentPosition = currentPosition.next;
    }
    return data;
  }

  /** testing program */
  public String toString() {
    Node aux = first;
    StringBuffer sb = new StringBuffer();
    while (aux != null) {
      sb.append(aux.data);
      aux = aux.next;
    }
    return sb.toString();
  }

  /**
   * Go back -numPositions-
   */
  public void back(int numPositions) {
    if (numPositions <= 0 || first == null || currentPosition == null)
      return;
    int positionsBack = numPositions;
    while (currentPosition != null && positionsBack > 0) {
      currentPosition = currentPosition.previous;
      positionsBack--;
    }
  }

  /** Test method */
  public static void main(String[] args) {
    List list = new List();
    list.insert("Node1");
    list.insert("Node2");
    System.out.println("Initial list: " + list.toString());
    System.out
        .println("Data in current position: " + list.currentPosition.data);
    System.out.println("Add Node: ");
    list.insert("Node3");
    System.out
        .println("Data in current position: " + list.currentPosition.data);
    System.out.println("List: " + list.toString());
    list.back(1);
    System.out.println("Go back one position");
    System.out
        .println("Data in current position: " + list.currentPosition.data);
    System.out.println("List: " + list.toString());
    list.insert("Node4");
    System.out
        .println("Data in current position: " + list.currentPosition.data);
    System.out.println("List: " + list.toString());
    list.extract();
    System.out.println("delete... ");
    System.out
        .println("Data in current position: " + list.currentPosition.data);
    System.out.println("List: " + list.toString());
    System.out.println("Go forward 7 ");
    list.forward(7);
    System.out
        .println("Data in current position: " + list.currentPosition.data);
    System.out.println("List: " + list.toString());
    list.back(1);
    list.extract();
    System.out
        .println("Data in current position: " + list.currentPosition.data);
    System.out.println("List: " + list.toString());
    list.extract();
    System.out.println("Current position: " + list.currentPosition);
    System.out.println("List: " + list.toString());
    list.forward(1);
    list.extract();
    System.out.println("Current position: " + list.currentPosition);
    System.out.println("List: " + list.toString());
    list.extract();
    System.out.println("Current position: " + list.currentPosition);
    System.out.println("List: " + list.toString());
  }
}
	  

/**
 * Interface for a Deque.
 * 
 * @author DIT-UC3M
 * 
 */
public interface Dqueue {

  void insertFirst(Object obj);

  void insertLast(Object obj);

  Object removeFirst();

  Object removeLast();

  int size();
}

Solución

Las soluciones se pueden ver en los siguientes listados:

/**
 * An Implementation of a Double Linked List Node
 * 
 * @author DIT-UC3M
 * 
 */
public class DNode {

  DNode next, prev;
  Object val;

  public DNode() {

    this.next = null;
    this.prev = null;
    this.val = null;
  }

  public DNode(Object val, DNode first, DNode last) {

    this.next = first;
    this.prev = last;
    this.val = val;
  }

  public DNode getNext() {
    return next;
  }

  public void setNext(DNode next) {
    this.next = next;
  }

  public DNode getPrev() {
    return prev;
  }

  public void setPrev(DNode prev) {
    this.prev = prev;
  }

  public Object getVal() {
    return val;
  }

  public void setVal(Object val) {
    this.val = val;
  }

}
	  

/**
 * Class that implements a Deque with a Double Linked List.
 * 
 * @author DIT-UC3M
 * 
 */
public class DLDqueue implements Dqueue {
  DNode head, tail;
  int size;

  public DLDqueue() {
    head = new DNode();
    tail = new DNode();
    head.setNext(tail);
    tail.setPrev(head);
    size = 0;
  }

  public void insertFirst(Object obj) {
    DNode h = head;
    DNode node = new DNode();
    node.setVal(obj);
    node.setNext(h);
    h.setPrev(node);
    head = node;
    if (size == 0)
      tail = node;
    size++;

  }

  public void insertLast(Object obj) {
    DNode t = tail;
    DNode node = new DNode();
    node.setVal(obj);
    node.setPrev(t);
    t.setNext(node);
    tail = node;
    if (size == 0)
      head = node;
    size++;
  }

  public Object removeFirst() {
    if (head == null)
      return null;
    Object val = head.getVal();
    head = head.getNext();
    size--;
    return val;
  }

  public Object removeLast() {
    if (tail == null)
      return null;
    Object val = tail.getVal();
    tail = tail.getPrev();
    size--;
    return val;
  }

  public int size() {
    return size;
  }

  public String toString() {
    String s = "head [";
    DNode aux = head;
    for (int i = 0; i < size; i++) {
      s += aux.getVal();
      if (aux == tail) {
        break;
      }
      s += "-";
      aux = aux.getNext();
    }
    return s + "] tail";
  }

}
	  

Solución

Las soluciones se pueden ver en los siguientes listados:

/**
 * Interface for a Stack.
 * 
 * @author DIT-UC3M
 * 
 */
public interface Stack {

  void push(Object obj);

  Object pop();

  int size();
}
	  

/**
 * Interface for a Queue.
 * 
 * @author DIT-UC3M
 * 
 */
public interface Queue {

  public void enqueue(Object obj);

  public Object dequeue();

  int size();
}

	  

/*
 * Class that implements a Stack with a Deque
 *  
 * @author DIT-UC3M 
 *
 */
public class DQStack implements Stack {

  private Dqueue data;

  public DQStack() {
    data = new DLDqueue();
  }

  public void push(Object obj) {
    data.insertFirst(obj);
  }

  public Object pop() {
    return data.removeFirst();
  }

  public int size() {
    return data.size();
  }

  public String toString() {
    return data.toString();
  }

  public static void main(String[] args) {
    DQStack stack = new DQStack();
    for (int i = 0; i < 5; i++) {
      stack.push(i);
    }
    System.out.println("Printing stack: " + stack);

    int s = stack.size();
    System.out.println("Printing size: " + stack.size());

    Object o = stack.pop();
    System.out.println("Pop element = " + o);

    System.out.println("Printing stack: " + stack);

  }
}
	  

/*
 * Class that implements a Queue with a Deque
 *  
 * @author DIT-UC3M 
 *
 */
public class DQQueue implements Queue {

  private Dqueue data;

  public DQQueue() {
    data = new DLDqueue();
  }

  public void enqueue(Object obj) {
    data.insertFirst(obj);
  }

  public Object dequeue() {
    return data.removeLast();
  }

  public int size() {
    return data.size();
  }

  public String toString() {
    return data.toString();
  }

  public static void main(String[] args) {
    DQQueue queue = new DQQueue();
    for (int i = 0; i < 5; i++) {
      queue.enqueue(i);
    }
    System.out.println("Printing queue: " + queue);

    int s = queue.size();
    System.out.println("Printing size: " + queue.size());

    Object o = queue.dequeue();
    System.out.println("Deque element = " + o);

    System.out.println("Printing queue: " + queue);

  }
}