How implementation of java.util.queue uses LIFO?

Question

In Java doc:

[...] Among the exceptions are priority queues, which order elements according to a supplied comparator, or the elements' natural ordering, and LIFO queues (or stacks) which order the elements LIFO (last-in-first-out)

How implementation of java.util.queue uses LIFO instead of FIFO?

Wellwisher

What is your question? Queue as a data structure is normally FIFO and Stack as a data structure is normally LIFO. – Serval

Do you want to implement FIFO queue using LIFO datastructure? – Glycogenesis

+1 for question. In my book I have met following confusing quote: Queue is a base interface for containers that holds a sequence of elements for processing. For example, the classes implementing Queue can be LIFO (last in, first out— as in stack data structure) or FIFO (first in, first out—as in queue data structure). – Villose

docs.oracle.com/javase/7/docs/api/java/util/ArrayDeque.html – Snowbird

Answer 1

Stack and LinkedList offered here are just a collections. Queue is not a collection. It is a part of concurrency package and can be used with threadpools.

I have just verified again and read javadoc that you have quoted. I think that the only option to use LIFO queue is to use priority queue with custom comparator that compare elements according to the insertion time in reverse order.

Majewski

Answer 2

You can use any Deque as a LIFO queue using Collections.asLifoQueue method:

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

Ope

Answer 3

You can use a java.util.LinkedList and use the pop() and push() methods and use it like a stack, which is a LIFO queue.

Faultless

Answer 4

Implementation of the Queue can base on FIFO, priorities and LIFO - that is what official documentation says.

When a programmer first sees "Queue" he automatically thinks "it must be FIFO order" (or eventually prioritized order). But as documentation says there must be possibility to use Queue interface for LIFO ordering. Let me explain you how it can be done.

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

As you can see depending on the implementation, Queue interface can be used also as a LIFO.

Geraldine

Answer 5

Deque can be used as LIFO or FIFO

Fowkes

Answer 6

Queue is a data structure that uses a technique of First-In-First-Out.

Here's a useful link : magi.toolkit.util.queue Class LIFOQueue

An implementation of a "Last In, First Out" Queue. Basically, a LIFO Queue is a Stack.

Prospectus

could you double check the link? I think someone else might have bought the domain. – Jussive

Answer 7

I made a LIFO queue with limited size. Limited size is maintained by replacing the oldest entries with the new ones. The implementation is based on 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);
}
}

Forras