java - 如何用 Java 编写队列代码

Question

我正在尝试用java创建一个队列。

问题是我不知道如何从数组中删除(？)一个值，即我出列的索引值。

这是我的代码。front() 方法是出队部分。我使用 iter_ 设置当前索引位置。但正如您所看到的，它使正确的值出列，尽管该值仍然保留在数组中:(

public class IntQueue {

    private int[] items_;
    private int top_;
    private int capacity_;
    private int iter_;

    public IntQueue(int capacity)
    {
        if(capacity <=0) capacity = 10;

        capacity_ = capacity;
        top_=0;
        count_ = 0;
        iter_=0;

        items_= new int[capacity_];
    }

    public void push_back(int value)
    {
        if(top_>= capacity_)
            overflow();

        items_[top_++]=value;
        count_++;
    }

    public int front()
    {
        if(top_<=0)
            return 0;

        int temp=0;
        temp=items_[iter_];

        count_--;
        iter_++;
        return temp;

    }

    public IntQueue clone()
    {
        IntQueue result = new IntQueue(capacity_);

        for(int i=0 ; i<top_; ++i)
        {
            result.push_back(items_[i]);

        }

        /*for(int i=0 ; i<top_ ; ++i)
        {

            result.items_[i] = items_[i];
        }*/

        return result;

    }

    public void log()
    {

        for(int i=0 ; i <top_; ++i)
        {
            System.out.print(items_[i]);
            if(i<top_ -1)
                System.out.print(", ");
        }
        System.out.println();
        }

    }

    private void overflow()
    {
        int[] newItem = new int[capacity_*2];

        for(int i=0 ; i <top_; ++i)
            newItem[i] = items_[i];
        items_=newItem;
        capacity_ *=2;

    }

    public static void main(String args[])
    {
        IntQueue queue = new IntQueue(2);

        System.out.println("queue push 3: "); queue.push_back(3);
        System.out.println("queue push 2: "); queue.push_back(2);
        System.out.println("queue push 1: "); queue.push_back(1);

        System.out.print("queue log: "); queue.log();

        System.out.println("front " + queue.front());
        System.out.println("front " + queue.front());

        System.out.print("queue log: "); queue.log();

        System.out.println("queue push 12: "); queue.push_back(12);
        System.out.println("queue push 11: "); queue.push_back(11);
        System.out.println("queue push 21: "); queue.push_back(21);
        System.out.println("queue push 31: "); queue.push_back(31);

        System.out.print("queue log: "); queue.log();

        System.out.println("front " + queue.front());
        System.out.println("front " + queue.front());

        System.out.print("clone queue log: "); queue.clone().log();


    }

}

Answer 1

我对您的实现不了解的是:

• 在前面的方法中，您使用了 iter_，但没有在其他地方使用。它有什么好处？
• 如果您没有使用某种变量来跟踪删除的内容而不实际删除它，从技术上讲，您需要将数组的所有项目向左移动一个位置，这样第一个项目离开了。然而，这是一个 O(N) 操作。
• 使用链表而不是数组来实现队列更容易。