Реализация стека и очереди связанного списка, и я не знаю, достаточно ли эффективен код, который я настроил - PullRequest
Новая
       27

Реализация стека и очереди связанного списка, и я не знаю, достаточно ли эффективен код, который я настроил

1 голос
/ 18 октября 2011

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

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

Node 

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;
}
}

Stack 

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
}
}

Queue 

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, я не уверен, есть ли более эффективный способ их реализации. Есть ли более стандартизированный способ их настройки, который я мог пропустить?

Ответы [ 2 ]

4 голосов
/ 18 октября 2011

Единственное, о чем я могу думать, это:

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

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

3 голосов
/ 18 октября 2011

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

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

...