Java Array representation of queue data structure

Question

I am trying to make a queue by representing it with a one dimensional array. I know people might suggest I will have an easier time by using a list or even the default java queue object but I am here to learn so I do not want to resort to such easy solutions. I have come across a few problems with my implementation so far:

1. If the queue is full objects cannot be added.
2. Shifting objects.

E.g. QueueArray -> [ ], [A], [B] Shift it so that it ends up like this: QueueArray -> [A], [B], [ ]

Now hear me out, for problem number 1#. My logical thinking tells me to somehow increase the size of the queue array to be able to take in more objects, thing is I'm not sure how to do that without saving all the objects into another temporary array then copying them over to a new array with a bigger size. I'm not even sure if this is a sensible and feasible way to carry this out.

Problem 2# I was thinking of possibly just checking for null objects in the queue array and if they were found, just shift the elements by one index.

Here is my code, I'm also open to other improvements.

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);
    }
}

Answer 1

So, you're right that there are data structures that do exactly what you want, but since this is more of an exercise than application, here's what I'd say.

#1

Your solution of copying the entire n-length array to an n+1-length array would work. But there are two other ways to do this that are typically used, neither of which involve copying the entire array.

The first is to pre-allocate the maximum size when you create the queue. This is similar to how you have to pre-allocate memory for arrays in C if you're familiar with that. This is by far the easiest of the 3 solutions, and the fastest.

I'll point out that if you use this solution, you'll often see what is called a "circular buffer" or "ring buffer"[1] used to implement a Queue. You should read up on the linked article on this topic.

The second is to use some sort of linked list[2], where instead of storing just values, you store a (value, next-address) pair. You can then dynamically add items. But to do this in Java is pretty difficult. The linked article provides more insight on linked lists.

#2

Don't shift. Depending on the size of your Queue and the size of your elements, it could take much longer -- shifting would be O(n) -- see [3] if you don't know what this means.

Instead of shifting, use something like a circular buffer [1]. Keep track of a head and tail (or head and size).

If you do something like this using a ring buffer insertion would be O(1) -- much better.

Aside

Learning about data structures is very important in my opinion, so goodonya for that. But (again, also my opinion) a language like Java makes understanding the basics of data structures much more difficult than something like, say, C or C++. Not impossible, mind you, but the managed-memory aspect of Java obfuscates some of the finer points of data structure implementation that C doesn't. If you really want to understand these data structures, I strongly suggest implementing them in C/C++ at some point, just to see what is necessary and how it works.

[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

Answer 2

Internally, I believe most Java list objects actually have an just an immutable array at some point, which is what you're running into.

What they do to resize, then is at some full % threshold (say 75%), they will create a new array at double the size. So if you had an a 4 item array, and inserted three items, the structure would internally update its storage array to be size 8, and do this again when there were 6 items, etc.

As far as doing the actual copy, look at System.arraycopy, which allows you to specify your source and destination array.

In terms of shifting, why shift? Why not just keep a pointer to the current index?

For example, look at this operation chain...

Queue Object, Queue Object, Dequeue Object, Queue Object.

Your structure might then look like

[,,,] - 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

Using this method, and as described by the other answers, you could also wrap your indexes around for elements that are still available. In the above example, if you added two more elements, since the first two are no longer in use, you could begin replacing them with new elements.

Obviously you would still need to handle resizing when enough objects weren't dequeued to allow for more being queued.