java——链表实现队列

日常生活中所能见到的队列举例:

队列正如日常生活中的排队取餐一样,?先排队的先取餐出队,?后排队的后取餐出队.?先进先出(FIFO:first?in first out).

使用链表实现队列,?就需要确定队头和队尾在链表中所对应的位置:?可以选择链表表头作队头,?表尾作队尾;?也可以选择链表表尾作队头,?表头作队尾.?在对表尾操作时,?有n个元素就循环n次将结点向后移动,?时间复杂度O(n);?对表头操作时直接对头结点进行操作,?时间复杂度O(1).?由于队列既需要对链表表头操作也需要对链表表尾操作,?队列中会用到能获取队头元素的方法,?所以且认为对队头操作较多,?则把链表表头作队头.

知道了怎么用链表实现队列,?方法实现起来就简单很多,?直接调用链表中已经完成的方法即可

代码演示:

队列接口:

public interface QueueInterface<V> {
    // 入队
    void offer(V v);

    // 出队
    V poll();

    // 队列是否为空
    boolean isEmpty();

    // 查看队元头素
    V peek();

    // 获取队列中元素个数
    int getSize();
}

链表队列代码:

public class MyLinkedQueue<V> implements QueueInterface<V> {
    private MyLinkedList<V> linkedList;

    // 链表队列的构造器
    public MyLinkedQueue() {
        this.linkedList = new MyLinkedList<>();
    }

    @Override
    public void offer(V v) {
        linkedList.add(v);
    }

    @Override
    public V poll() {
        return linkedList.removeHead();
    }

    @Override
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    @Override
    public V peek() {
        return linkedList.getFirst();
    }

    @Override
    public int getSize() {
        return linkedList.getSize();
    }

    @Override
    public String toString() {
        return linkedList.toString();
    }
}

链表的实现参考:链表的实现