java.util.queue如何使用LIFO实现？

Question

在Java文档中:

"[...] 其中有些例外是优先级队列，它根据提供的比较器或元素的自然排序来排序元素，以及LIFO队列（或栈），它按照LIFO（后进先出）的顺序对元素进行排序"

Java.util.queue的实现如何使用后进先出（LIFO）而不是先进先出（FIFO）？

- celsowm

---

你有什么问题吗？队列作为一种数据结构通常是先进先出，而栈作为一种数据结构通常是后进先出。 - Marcelo

你想使用LIFO数据结构来实现FIFO队列吗？ - user802421

在我的书中，我遇到了以下令人困惑的引用：“队列是容器的基本接口，用于保存要处理的元素序列。例如，实现队列的类可以是LIFO（后进先出——如堆栈数据结构）或FIFO（先进先出——如队列数据结构）。” - gstackoverflow

https://docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html - Stanislav Machel

Answer 1

您可以使用Collections.asLifoQueue方法将任何Deque用作LIFO队列：

Queue<Integer> arrayLifoQueue = Collections.asLifoQueue(new ArrayDeque<Integer>());
Queue<Integer> linkedListLifoQueue = Collections.asLifoQueue(new LinkedList<Integer>());

- ZhekaKozlov

Answer 2

您可以使用 java.util.LinkedList，并使用pop()和push()方法将其作为栈使用，它就像是一个后进先出的队列（LIFO队列）。

- Oscar Gomez

Answer 3

队列的实现可以基于FIFO、优先级和LIFO，这是官方文档所说的。

当程序员第一次看到“Queue”时，他会自动想到“它一定是FIFO顺序”（或者可能是按优先级排序）。但正如官方文档所述，必须有可能使用队列接口进行LIFO排序。让我解释一下如何实现它。

// FIFO queue usage
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);

queue.remove(); // returns 1
queue.remove(); // returns 2

// LIFO queue usage
Queue<Integer> queue = Collections.asLifoQueue(new ArrayDeque<>());
queue.add(1);
queue.add(2);

queue.remove(); // returns 2
queue.remove(); // returns 1

正如您所看到的，根据实现方式，队列接口也可以用作后进先出（LIFO）。

- Adrian Malik

Answer 4

Deque可以作为LIFO或FIFO使用

- dan

Answer 5

这里提供的Stack和LinkedList只是集合。Queue不是一个集合，它是并发包的一部分，并且可以与线程池一起使用。

我刚刚再次验证并阅读了您引用的javadoc。我认为使用LIFO队列的唯一选项是使用具有自定义比较器的优先级队列，该比较器根据插入时间按相反顺序比较元素。

- AlexR

Answer 6

队列是一种使用先进先出技术的数据结构。

这里有一个有用的链接：magi.toolkit.util.queue类LIFOQueue

“后进先出”队列的实现。基本上，LIFO队列就是一个栈。

- Saurabh Gokhale

---

你能再检查一下链接吗？我觉得可能有人已经购买了这个域名。 - Funny Geeks

Answer 7

我使用有限大小的LIFO队列。通过用新条目替换最旧的条目来维护有限的大小。该实现基于LinkedList。

package XXXX;

import java.util.LinkedList;

public class LIFOQueueLimitedSize<E> extends LinkedList<E> {


/**
 * generated serial number
 */
private static final long serialVersionUID = -7772085623838075506L;

// Size of the queue
private int size;

// Constructor
public LIFOQueueLimitedSize(int crunchifySize) {

    // Creates an ArrayBlockingQueue with the given (fixed) capacity and default access policy
    this.size = crunchifySize;
}

// If queue is full, it will remove oldest/first element from queue like FIFO
@Override
synchronized public boolean add(E e) {

    // Check if queue full already?
    if (super.size() == this.size) {
        // remove element from queue if queue is full
        this.remove();
    }
    return super.add(e);
}
}

- ulyssis2