Блог

Работал над реализацией для классов очереди и стека связанных списков для назначения. Я протестировал оба из них, и они, похоже, работают, но я обеспокоен тем, что некоторые части реализации могут быть выполнены лучше, чем я настроил в настоящее время, и я не хочу снимать баллы за неэффективный код.

Вот классы, которые я настроил:

Узел

 public class Node {
Node next;
Car car;

/**
 * A node object, used for the creation of LinkedLists.
 * @param car
 */
public Node(Car car)
{
    next = null;
    this.car = car;
}
}
  

Стек

 public class LStack {
Node head = null;

/**
 * Adds a car object to the list
 * @param car = the car object to be added
 */
public void push(Car car)
{
    Node oldHead = head;
    head = new Node(car);
    head.next = oldHead;
}

/**
 * Removes the top car from the list
 * @return the car at the top of the list
 */
public Car pop()
{
    Car headCar = head.car;
    head = head.next;
    return headCar;
}

/**
 * Checks if the list is empty
 * @return whether or not the list is empty
 */
public boolean isEmpty()
{
    return (head == null);
}

/**
 * 
 * @return the size of the list
 */
public int size()
{
    Node nextNode = head;
    int count = 0;
    while (nextNode != null)
    {
        count  ;
        nextNode = nextNode.next;
    }
    return count;
}

/**
 * Displays the list of car license plate information
 */
public void display()
{
    Node nextNode = head;
    while (nextNode != null)
    {
        System.out.print(nextNode.car.getLicense()   "|");
        nextNode = nextNode.next;
    }
    System.out.println();
}

/**
 * 
 */
public void reverseStack()
{
    // not implemented yet
}
}
  

Очередь

 public class LQueue {
Node head = null;

/**
 * Adds a car object to the list
 * 
 * @param car
 *            = the car object to be added
 */
public void insert(Car car) {
    Node current = head;
    if (current != null) {
        while (current.next != null) {
            current = current.next;
        }
        current.next = new Node(car);
    }
    else
    {
        head = new Node(car);
    }
}

/**
 * Removes the top car from the list
 * 
 * @return the car at the top of the list
 */
public Car remove() {
    Car headCar = head.car;
    head = head.next;
    return headCar;
}

/**
 * Checks if the list is empty
 * 
 * @return whether or not the list is empty
 */
public boolean isEmpty() {
    return (head == null);
}

/**
 * 
 * @return the size of the list
 */
public int size() {
    Node nextNode = head;
    int count = 0;
    while (nextNode != null) {
        count  ;
        nextNode = nextNode.next;
    }
    return count;
}

/**
 * Displays the list of car license plate information
 */
public void display() {
    Node nextNode = head;
    while (nextNode != null) {
        System.out.print(nextNode.car.getLicense()   "|");
        nextNode = nextNode.next;
    }
    System.out.println();
}

/**
 * 
 */
public void reverseQueue() {

}
}
  

и класс Car на самом деле не важен, он просто хранит информацию о номерном знаке в строке.

В основном меня беспокоят те, которые я настроил с циклами While, я не уверен, есть ли более эффективный способ их реализации с использованием памяти. Есть ли более стандартизированный способ их настройки, который я, возможно, пропустил?

Одна вещь, которую я бы изменил, это то, что я бы LQueue сохранил ссылки как на начало, так и на конец очереди. Таким образом, вы сможете insert() выполнять это в постоянное время, без необходимости перебирать все существующие элементы.

Кроме того, size() при желании оба метода можно заставить выполняться в постоянное время: отслеживать текущий размер в переменной-члене, увеличивать insert() и уменьшать remove() .

Единственные две вещи, о которых я могу думать::

1. Отслеживайте количество элементов в списке с помощью int, которое увеличивается при добавлении и уменьшается при удалении. Это сделало бы метод size() мгновенным. Все, что вам нужно будет сделать, это вернуть это значение int.

2. Для очереди следите за хвостом со ссылкой на узел так же, как вы делаете head. Таким образом, вам не нужно перебирать список, чтобы найти конец списка. Хвост всегда будет последним добавленным узлом. Это позволило бы вам не перебирать список каждый раз, когда вы хотите что-то добавить; вместо этого вы могли бы просто добавить это в конец этого хвоста.