Java 使用链表来实现队列功能

时间:2022-09-05 17:37:37
/**
 * 链表元素定义
 * Create by zxb on 2017/8/27
 */
public class Element<T> {

    private Element<T> next;

    private T value;

    public Element<T> getNext() {
        return next;
    }

    public void setNext(Element<T> next) {
        this.next = next;
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }
}

/**
 * 列表模板接口
 * Created by zhengxb on 2017/8/27.
 */
public interface IList<T> {

    boolean pushBack(T newElement);

    boolean popFront();

    Element<T> front();

    int size();
}

/**
 * 链表实现
 * Create by zxb on 2017/8/27
 */
public class ListImpl<T> implements IList<T> {

    private Element<T> first = null;

    private Element<T> last = null;

    private int size = 0;

    @Override
    public boolean pushBack(T newElement) {
        Element<T> element = new Element<>();
        element.setValue(newElement);
        if (size == 0) {
            first = element;
            size++;
            return true;
        }
        if (last == null) {
            last = new Element<>();
            last.setValue(newElement);
            first.setNext(last);
        } else {
            last.setNext(element);
            last = element;
        }
        size++;
        return true;
    }

    @Override
    public boolean popFront() {
        if (size == 0) {
            return false;
        }
        first = first.getNext();
        size--;
        return true;
    }

    @Override
    public Element<T> front() {
        return first;
    }

    @Override
    public int size() {
        return size;
    }
}

/**
 * 队列接口
 * Create by zxb on 2017/8/27
 */
public interface IQueue<R> {

    boolean push(R newElement);

    boolean pop();

    R front();

    int size();

    boolean display();
}

/**
 * 队列实现
 * Create by zxb on 2017/8/27
 */
public class QueueImpl<R> implements IQueue<R> {

    private ListImpl<R> list;

    @Override
    public boolean push(R newElement) {
        if (list == null) {
            list = new ListImpl<>();
        }
        list.pushBack(newElement);
        return true;
    }

    @Override
    public boolean pop() {
        if (list == null) {
            list = new ListImpl<>();
        }
        list.popFront();
        return true;
    }

    @Override
    public R front() {
        return list.front().getValue();
    }

    @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean display() {
        Element<R> front = list.front();
        System.out.println("列表元素:");
        Element<R> temp = front;
        while (temp != null) {
            System.out.print(temp.getValue());
            temp = temp.getNext();
            System.out.println("\t");
        }
        return true;
    }
}

/**
 * Create by zxb on 2017/8/27
 */
public class Test {

    public static void main(String[] args) {
        IQueue<String> queue = new QueueImpl<>();
        queue.push("one");
        queue.push("two");
        queue.push("three");
        queue.pop();
        queue.display();
    }
}

执行结果:

Java 使用链表来实现队列功能