Java中如何用LinkedList实现队列和栈-Java-PHP中文网

Java中如何用LinkedList实现队列和栈

穿越時空

发布： 2025-06-24 14:16:02

原创

768人浏览过

java中linkedlist实现队列和栈的方法如下：1.使用addlast()和removefirst()实现队列的入队和出队；2.使用addfirst()和removefirst()实现栈的入栈和出栈。为提升代码可读性，建议将队列封装为独立类，如myqueue，并实现enqueue、dequeue、peek等方法。对于线程安全的栈，可通过collections.synchronizedlist()包装linkedlist，或使用concurrentlinkeddeque，后者更适合生产环境。linkedlist的优势在于添加和删除操作时间复杂度为o(1)，但空间利用率低且缓存命中率差。相比arraydeque等结构，其性能较低，因此实际推荐优先使用arraydeque。此外，避免内存泄漏需及时清空不再使用的元素，并释放对象持有的外部资源。

Java中如何用LinkedList实现队列和栈

Java中，LinkedList凭借其双向链表的特性，可以轻松实现队列和栈这两种数据结构。关键在于理解它们各自的操作特点，并巧妙地利用LinkedList提供的方法。

解决方案

LinkedList实现队列，主要利用其addLast()方法进行入队，removeFirst()方法进行出队。实现栈，则使用addFirst()方法进行入栈，removeFirst()方法进行出栈。

立即学习“Java免费学习笔记（深入）”；

如何使用LinkedList实现一个高效的队列？

LinkedList本身就提供了队列所需的基本操作，但为了代码的可读性和维护性，建议封装成一个独立的Queue类。

import java.util.LinkedList;

public class MyQueue<T> {
    private LinkedList<T> list = new LinkedList<>();

    public void enqueue(T element) {
        list.addLast(element);
    }

    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return list.removeFirst();
    }

    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return list.getFirst();
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

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

    public static void main(String[] args) {
        MyQueue<String> queue = new MyQueue<>();
        queue.enqueue("A");
        queue.enqueue("B");
        queue.enqueue("C");

        System.out.println("Queue size: " + queue.size()); // Output: Queue size: 3
        System.out.println("Dequeued: " + queue.dequeue()); // Output: Dequeued: A
        System.out.println("Peek: " + queue.peek()); // Output: Peek: B
    }
}

登录后复制

这里，enqueue对应入队，dequeue对应出队，peek用于查看队首元素，isEmpty判断队列是否为空，size获取队列大小。注意，dequeue和peek前需要判断队列是否为空，避免抛出异常。

如何利用LinkedList构建一个线程安全的栈？

虽然LinkedList本身不是线程安全的，但可以通过Collections.synchronizedList()方法或者使用java.util.concurrent包下的ConcurrentLinkedDeque来实现线程安全的栈。这里展示使用Collections.synchronizedList()的简单实现，实际生产环境建议使用ConcurrentLinkedDeque以获得更好的性能。

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class ThreadSafeStack<T> {
    private List<T> list = Collections.synchronizedList(new LinkedList<>());

    public void push(T element) {
        list.add(0, element); // 等同于 addFirst，但用于List
    }

    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return list.remove(0); // 等同于 removeFirst，但用于List
    }

    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return list.get(0);
    }

    public boolean isEmpty() {
        return list.isEmpty();
    }

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

    public static void main(String[] args) {
        ThreadSafeStack<Integer> stack = new ThreadSafeStack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("Stack size: " + stack.size()); // Output: Stack size: 3
        System.out.println("Popped: " + stack.pop()); // Output: Popped: 3
        System.out.println("Peek: " + stack.peek()); // Output: Peek: 2
    }
}

登录后复制

需要注意的是，使用Collections.synchronizedList()包装后的List，所有操作都需要在外部进行同步，否则仍然可能存在线程安全问题。例如，在迭代时需要手动加锁。

LinkedList实现的队列和栈在性能上有哪些优缺点？

LinkedList实现的队列和栈，在添加和删除元素时具有O(1)的时间复杂度，这是其优点。缺点在于，LinkedList需要额外的空间来存储节点之间的连接信息，相比数组实现的队列和栈，空间利用率较低。此外，由于LinkedList的元素在内存中不是连续存储的，CPU缓存命中率相对较低，可能影响性能。实际应用中，需要根据具体场景权衡选择。如果对性能要求非常高，且数据量可控，可以考虑使用数组实现的队列和栈。如果数据量变化频繁，且对空间利用率要求不高，LinkedList是一个不错的选择。

除了LinkedList，还有哪些Java集合类可以用来实现队列和栈？

除了LinkedList，ArrayDeque也可以用来实现队列和栈。 ArrayDeque基于循环数组实现，在性能上通常优于LinkedList。对于队列，还可以使用PriorityQueue实现优先级队列。对于栈，Vector也可以实现，但Vector是线程安全的，性能较低，不推荐使用。 Stack类继承自Vector，同样不推荐使用。总的来说，ArrayDeque是实现队列和栈的首选，LinkedList次之，其他集合类则根据具体需求选择。

使用LinkedList实现队列和栈时，如何避免内存泄漏？

在使用LinkedList实现队列和栈时，如果存储的是对象，需要注意避免内存泄漏。当队列或栈不再需要使用时，应该清空其中的元素，以便垃圾回收器可以回收这些对象占用的内存。可以通过循环调用removeFirst()或removeLast()方法，直到队列或栈为空来实现。另外，如果队列或栈中的对象持有外部资源的引用，需要在移除对象时释放这些资源，以防止资源泄漏。例如，如果对象持有文件句柄或网络连接，需要在移除对象时关闭这些句柄或连接。

以上就是Java中如何用LinkedList实现队列和栈的详细内容，更多请关注php中文网其它相关文章！