4

我试图通过用一维数组表示它来创建一个队列。我知道人们可能会建议我使用列表甚至默认的 java 队列对象会更轻松，但我是来学习的，所以我不想求助于如此简单的解决方案。到目前为止，我的实现遇到了一些问题：

  1. 如果队列已满，则无法添加对象。
  2. 移动物体。

例如 QueueArray -> [ ], [A], [B] 移动它，使其最终如下： QueueArray -> [A], [B], [ ]

现在听我说，问题编号 1#。我的逻辑思维告诉我以某种方式增加队列数组的大小以便能够接收更多对象，事情是我不确定如何在不将所有对象保存到另一个临时数组然后将它们复制到新的更大尺寸的数组。我什至不确定这是否是一种明智可行的方式来执行此操作。

问题 2# 我在想可能只是检查队列数组中的空对象，如果找到它们，只需将元素移动一个索引。

这是我的代码，我也愿意接受其他改进。

import java.util.Scanner;

public class Queue {
    Object[] q;
    int head, tail;
    Scanner in;

    public Queue(int size){ 
        q = new Object[size];
        menu();
    }

    public void menu(){
        System.out.println("\t");   
        System.out.println("1. add(x) - Adds the object x to end of the queue");
        System.out.println("2. remove() - Removes the first object in the queue");
        System.out.println("3. view - Shows contents in queue");
        System.out.println("4. exit - Exits program");
        System.out.println("Select your operation:"+"\t");  

        while(true){
            in = new Scanner(System.in);
            int userInput = in.nextInt();

            if(userInput == 1){
                System.out.println("Give value of object");
                in = new Scanner(System.in);
                Object userIn = in.next();
                add(userIn);
                menu();
            }

            if(userInput == 2){
                remove();
                menu();
            }

            if(userInput == 3){
                peek();
                menu();
            }

            if(userInput == 4){
                System.exit(0);
            }
        }
    }

    // Adds the object to the end of the queue
    Object add(Object letter){

        // If the queue is not full, add to back of queue
        if(tail >= q.length){
            System.out.println("Queue is full");
            return null;
        } else {
            q[tail] = letter;
            tail++;
        }
        return tail;
    }

    // Removes the first object in the queue
    Object remove(){
        if(q.length == 0){
            return null;
        } else {
            q[head] = null;
            head++;
        }
        return head;
    }

    // Returns the head, tail and all other objects in the queue
    void peek(){
        System.out.println("Head: "+q[head]);
        System.out.println("Tail: "+q[tail-1]);
        System.out.println(q[0]+", "+q[1]+", "+q[2]+", "+q[3]+", "+q[4]+".");
    }

    public static void main(String[] args){
        new Queue(5);
    }
}
4

2 回答 2

2

在内部，我相信大多数 Java 列表对象在某些时候实际上只有一个不可变数组，这就是您所遇到的。

他们所做的调整大小，然后是在某个完整的百分比阈值（比如 75%），他们将创建一个两倍大小的新数组。因此，如果您有一个 4 项数组，并插入了三个项，该结构将在内部将其存储数组更新为大小 8，并在有 6 个项时再次执行此操作，依此类推。

至于实际复制，请查看 System.arraycopy，它允许您指定源和目标数组。

在转移方面，为什么要转移？为什么不只保留一个指向当前索引的指针？

比如看这个操作链……

队列对象，队列对象，出队对象，队列对象。

你的结构可能看起来像

[,,,] - head at 0, tail at 0
[obj1,,,] - head at 0, tail at 1
[obj1,obj2,,] - head at 0, tail at 1
[obj1,obj2,,] - head at 1, tail at 1
[obj1,obj2,obj3,] - head at 1, tail at 2
[obj1,obj2,obj3,] - head at 2, tail at 2

使用此方法，并且如其他答案所述，您还可以将索引包装在仍然可用的元素上。在上面的示例中，如果您再添加两个元素，由于前两个不再使用，您可以开始用新元素替换它们。

显然，当没有足够的对象出列以允许更多对象排队时，您仍然需要处理调整大小。

于 2012-09-27T16:24:14.840 回答
2

所以，你是对的，有一些数据结构可以完全按照你的要求做，但是由于这更像是一个练习而不是应用程序，这就是我要说的。

#1

您将整个n长度数组复制到n +1 长度数组的解决方案将起作用。但是还有另外两种通常使用的方法来做到这一点，这两种方法都不涉及复制整个数组。

第一个是在创建队列时预先分配最大大小。如果您熟悉的话，这类似于您必须为 C 中的数组预先分配内存的方式。这是迄今为止 3 种解决方案中最简单的，也是最快的。

我会指出，如果您使用此解决方案，您会经常看到用于实现队列的所谓“循环缓冲区”或“环形缓冲区”[1]。您应该阅读有关此主题的链接文章。

第二种是使用某种链表[2]，而不是只存储值，而是存储一个 (value, next-address) 对。然后，您可以动态添加项目。但是在 Java 中做到这一点是相当困难的。链接的文章提供了有关链接列表的更多见解。

#2

不要转移。 根据队列的大小和元素的大小，它可能需要更长的时间——移位将是O (n)——如果你不知道这意味着什么，请参阅 [3]。

而不是移位，使用类似循环缓冲区的东西 [1]。跟踪头部和尾部（或头部和大小）。

如果你使用环形缓冲区插入来做这样的事情，那么O (1) 会好得多。

在旁边

在我看来，学习数据结构非常重要，所以很好。但是（同样，我也认为）像 Java 这样的语言使得理解数据结构的基础知识比诸如 C 或 C++ 之类的语言要困难得多。请注意，并非不可能，但 Java 的托管内存方面混淆了 C 没有的数据结构实现的一些更精细的点。如果你真的想了解这些数据结构，我强烈建议在某个时候用 C/C++ 来实现它们，只是为了看看什么是必要的以及它是如何工作的。

[1] http://en.wikipedia.org/wiki/Circular_buffer
[2] http://en.wikipedia.org/wiki/Linked_list
[3] http://en.wikipedia.org/wiki/Big_O_notation

于 2012-09-27T16:27:40.600 回答