ArrayList 模拟队列 - Java

ArrayList to emulate a queue - Java

提问by Rakim

I want to use an ArrayList in Java and implement it as a queue. Adding to the queue should be fairly easy using queue.add("element"). Although, removing popping items out it a bit trickier. The way I thought of doing it is the following:

我想在 Java 中使用 ArrayList 并将其实现为队列。添加到队列应该很容易使用queue.add("element")。虽然，删除弹出项目有点棘手。我想到的方法如下：

public String pop(){
    String s = queue.get(0);
    queue.remove(0);
    queue.trimToSize();
    return s;
}

is this the right way? will I be getting the next element of the queue next time I invoke the pop() method?

这是正确的方法吗？下次我调用 pop() 方法时会获取队列的下一个元素吗？

采纳答案by Anderson Vieira

If you really need to use an ArrayList, remove()already does everything you want. You should be able to implement a queue just using add()and remove(0). Your pop()method could be implemented as:

如果你真的需要使用ArrayList，remove()已经做了你想做的一切。您应该能够仅使用add()and来实现队列remove(0)。您的pop()方法可以实现为：

public String pop() {
    return queue.remove(0);
}

From the documentation:

从文档：

remove

public E remove(int index)

Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).

Returns: the element that was removed from the list

消除

公共 E 删除（整数索引）

移除此列表中指定位置的元素。将任何后续元素向左移动（从它们的索引中减去一个）。

返回：从列表中删除的元素

Though, as others have suggested, an ArrayDequewould be a better fit for a queue.

不过，正如其他人所建议的那样， anArrayDeque更适合排队。

回答by Om.

Try below mention implementation using ArrayDeque

尝试使用 ArrayDeque 下面提到的实现

import java.util.ArrayDeque;
import java.util.Collection;
import java.util.Iterator;

public class QueueImpl<E>
{
    private ArrayDeque<E> arrayDeque;

    /**
     * Constructs an empty array deque with an initial capacity sufficient to
     * hold 16 elements.
     **/
    public QueueImpl()
    {
        arrayDeque = new ArrayDeque<E>();
    }

    /**
     * Constructs a deque containing the elements of the specified collection,
     * in the order they are returned by the collection's iterator.
     **/
    public QueueImpl(Collection<? extends E> c)
    {
        arrayDeque = new ArrayDeque<E>(c);
    }

    /**
     * Constructs an empty array deque with an initial capacity sufficient to
     * hold the specified number of elements.
     **/
    public QueueImpl(int numElements)
    {
        arrayDeque = new ArrayDeque<E>(numElements);
    }

    /** Inserts the specified element at the tail of this queue. **/
    public boolean add(E e)
    {
        return arrayDeque.add(e);
    }

    /** Atomically removes all of the elements from this queue. **/
    public void clear()
    {
        arrayDeque.clear();
    }

    /** Returns true if this queue contains the specified element. **/
    public boolean contains(Object o)
    {
        return arrayDeque.contains(o);
    }

    /** Returns an iterator over the elements in this queue in proper sequence. **/
    public Iterator<E> iterator()
    {
        return arrayDeque.iterator();
    }

    /**
     * Inserts the specified element at the tail of this queue if it is possible
     * to do so immediately without exceeding the queue's capacity, returning
     * true upon success and false if this queue is full.
     **/
    public boolean offer(E e)
    {
        return arrayDeque.offer(e);
    }

    /**
     * Retrieves, but does not remove, the head of this queue, or returns null
     * if this queue is empty.
     **/
    public E peek()
    {
        return arrayDeque.peek();
    }

    /**
     * Retrieves and removes the head of this queue, or returns null if this
     * queue is empty.
     **/
    public E poll()
    {
        return arrayDeque.poll();
    }

    /**
     * Removes a single instance of the specified element from this queue, if it
     * is present.
     **/
    public boolean remove(Object o)
    {
        return arrayDeque.remove(o);
    }

    /** Returns the number of elements in this queue. **/
    public int size()
    {
        return arrayDeque.size();
    }

    /**
     * Returns an array containing all of the elements in this queue, in proper
     * sequence.
     **/
    public Object[] toArray()
    {
        return arrayDeque.toArray();
    }

    /**
     * Returns an array containing all of the elements in this queue, in proper
     * sequence; the runtime type of the returned array is that of the specified
     * array.
     **/
    public <T> T[] toArray(T[] a)
    {
        return arrayDeque.toArray(a);
    }

    /** Returns a string representation of this collection. **/
    public String toString()
    {
        return arrayDeque.toString();
    }

    /** Inserts the specified element at the front of this deque. **/
    public void addFirst(E e)
    {
        arrayDeque.addFirst(e);
    }

    /** Inserts the specified element at the end of this deque. **/
    public void addLast(E e)
    {
        arrayDeque.addLast(e);
    }

    /** Retrieves, but does not remove, the first element of this deque. **/
    public void getFirst()
    {
        arrayDeque.getFirst();
    }

    /** Retrieves, but does not remove, the last element of this deque. **/
    public void getLast()
    {
        arrayDeque.getLast();
    }

    /** Inserts the specified element at the front of this deque. **/
    public boolean offerFirst(E e)
    {
        return arrayDeque.offerFirst(e);
    }

    /** Inserts the specified element at the end of this deque. **/
    public boolean offerLast(E e)
    {
        return arrayDeque.offerLast(e);
    }

    /**
     * Retrieves, but does not remove, the first element of this deque, or
     * returns null if this deque is empty.
     **/
    public E peekFirst()
    {
        return arrayDeque.peekFirst();
    }

    /**
     * Retrieves, but does not remove, the last element of this deque, or
     * returns null if this deque is empty.
     **/
    public E peekLast()
    {
        return arrayDeque.peekLast();
    }

    public static void main(String... arg)
    {
        QueueImpl<Integer> arrayDeque = new QueueImpl<Integer>();
        arrayDeque.add(300);
        arrayDeque.add(200);
        arrayDeque.add(600);
        arrayDeque.add(-400);
        arrayDeque.add(240);

        System.out.println("the elements of the arrayDeque is ");
        Iterator<Integer> itr = arrayDeque.iterator();
        while (itr.hasNext())
        {
            System.out.print(itr.next() + "\t");
        }
        System.out.println();
        arrayDeque.offer(600);
        arrayDeque.offer(700);
        arrayDeque.offerFirst(3);
        arrayDeque.offerLast(10);

        System.out.println("the peak element of the arrayDeque is(by peeking) " + arrayDeque.peek());
        System.out.println("the peak element of the arrayDeque is(by polling) " + arrayDeque.poll());
        System.out.println("the last element of arrayDeque is (peeking)" + arrayDeque.peekLast());
        System.out.println("element 300 removed " + arrayDeque.remove(300));
        System.out.println("the arrayDeque contains 400 :" + arrayDeque.contains(400));
        System.out.println("the arrayDeque contains 600 :" + arrayDeque.contains(600));
        System.out.println("the size of the arrayDeque is " + arrayDeque.size());
        System.out.println(arrayDeque);
    }
}

Result:

结果：

the elements of the arrayDeque is 
300 200 600 -400    240 
the peak element of the arrayDeque is(by peeking) 3
the peak element of the arrayDeque is(by polling) 3
the last element of arrayDeque is (peeking)10
element 300 removed true
the arrayDeque contains 400 :false
the arrayDeque contains 600 :true
the size of the arrayDeque is 7
[200, 600, -400, 240, 600, 700, 10]