Representation of Java Array Queue Data Structures

Question

I am trying to make a queue by representing it with a one-dimensional array. I know that people can offer me an easier time using the default list or even a java queue object, but I'm here to find out, so I don’t want to resort to such simple solutions. So far, I have encountered some problems with my implementation:

• If the queue is not full, objects cannot be added.
• Offset objects.

eg. QueueArray → [], [A], [B] Slide it so that it turns out like this: QueueArray → [A], [B], []

Now listen to me, for issue number 1 #. My logical thinking tells me to somehow increase the size of the queue array in order to be able to accept more objects. The fact is, I'm not sure how to do this without saving all the objects to another temporary array, and then rewriting them to a new array with a large size. I’m not even sure that this is a reasonable and feasible way to do this.

Problem 2 # I was thinking about the possibility of checking for null objects in the queue array, and if they were found, just shift the elements one index at a time.

Here is my code, I am 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

Inside, I believe that most Java list objects actually have at some point an immutable array, and that is what you are using.

What they do to resize, at the threshold of %% (say 75%), they will create a new array with doubled size. Therefore, if you have an array of 4 elements and three elements are inserted, the structure will internally update its storage array to size 8 and do it again when there were 6 elements, etc.

For the actual copy, look at System.arraycopy, which allows you to specify your source and target array.

As for the shift, why shift? Why not just keep a pointer to the current index?

For example, look at this chain of operations ...

Queue object, Queue object, Deactivation object, Queue object.

Your structure may 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 in other answers, you can also wrap your indexes on 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 can start replacing them with new elements.

Obviously, you still have to handle resizing when enough objects are not allocated to allow more queuing.

Answer 2

So, you are right that there are data structures that do exactly what you want, but since this is more an exercise than an application, that’s what I would say.

# 1

Your decision to copy the entire n-length array to an n + 1 length array will work. But there are two other ways to do this that are commonly used, none of which require copying the entire array.

First, pre-set the maximum size when creating the queue. This is similar to how you should preallocate memory for arrays in C if you are familiar with this. This is by far the easiest of the three solutions and the fastest.

I will point out that if you use this solution, you will often see what is called a "circular buffer" or "circular buffer" [1] used to implement the queue. You should read an article related to this topic.

Secondly, you need to use some kind of linked list [2], where instead of storing only the values ​​you store a pair (value, next address). Then you can add items dynamically. But doing this in Java is quite difficult. A related article gives more information about linked listings.

# 2

Do not move. Depending on the size of your queue and the size of your elements, this can take much longer - the shift will be O (n) - see [3] if you do not know what this means.

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

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

Besides

Studying the data structure is very important, in my opinion, so burying it for that. But (again, my opinion), a Java-like language greatly complicates the understanding of data fundamentals than something like C or C ++. It doesn’t matter, but the Java managed memory aspect confuses some of the more subtle data structure implementations that C does not. If you really want to understand these data structures, I highly recommend implementing them in C / C ++ at some point, just to see what is needed 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