Home



2019/07 - DS&A #4: Queues

Hey folks,

Next in this series is the amazing QUEUE data structure... And the metaphor we'll be using this time shall be an escalator! A queue is again exactly what it sounds like: A 'queue' of 'things'.

Basically, we have a list of nodes and a number of actions that can be performed on said list. Mainly adding to the queue and removing form the queue, but we'll only be adding to the front of the list and removing from the back. So it operates kinda like an escalator; where for a list of people, the first person on the escalator is the first person to get off, and the last person to get on is the last person to get off. For our example, we're going to forget about how people walk ahead of others while on some escalators (See London Undergrounds escalators), and we'll also be ignoring how you used to run backwards down escalators when you were a child (Don't lie, everyone did it).

So what are the methods that can be called on a queue?

So lets have a look at what the code for a queue should look like...

Standard setup:

public class Queue {

    //Head removed first, tail last.

    //Due to type erasure in Java, we cannot make a generic array
    Object[] queueOfNodes = new Object[1];
    int queueOfNodesHeadIndex = 0;
    int queueOfNodesTailIndex = 0;
    int size = 0;

    public Queue() {

    }

 

Next we have out peek method. This method is used to look at the top of the queue

    public Object peek() {
        return queueOfNodes[queueOfNodesHeadIndex];
    }

 

Standard empty and full check methods:

    public boolean isEmptyArray() {
        boolean isEmptyArray = true;
        for(int i = 0; i < queueOfNodes.length; i++) {
            if(queueOfNodes[i] != null) {
                isEmptyArray = false;
            }
        }

        return isEmptyArray;
    }

    public boolean isFullArray() {
        boolean isFullArray = true;
        for(int i = 0; i < queueOfNodes.length; i++) {
            if(queueOfNodes[i] == null) {
                isFullArray = false;
            }
        }

        return isFullArray;
    }

 

Our enqueue method, where we see our first queue-specific code. As you can see, we only add to the front of the queue (And check for the size of the array before copying and resizing it if necessary):    

public void enQueue(Object node) {
        if(isEmptyArray()) {
            queueOfNodes[0] = node;
            size++;
        }
        else {
            size++;
            if(size >= queueOfNodes.length && this.isFullArray()) {
                copyArrayAndResize();
            }
            if(queueOfNodesTailIndex == queueOfNodes.length - 1) {
                queueOfNodesTailIndex = 0;
            }
            else {
                queueOfNodesTailIndex++;
            }

            queueOfNodes[queueOfNodesTailIndex] = node;

        }
    }

 

A copy and resize method. Note that we never resize the array by reducing it here (But you can add in that code if you want to give it a shot):

    public void copyArrayAndResize() {
        Object[] oldCopy = queueOfNodes;
        int sizeNew = size*2;
        Object[] newArray = new Object[sizeNew];

        int newArrayIndex = 0;
        int newTailIndex = 0;

        for(int i = queueOfNodesHeadIndex; i < queueOfNodesTailIndex;i++, newArrayIndex++) {
            newArray[newArrayIndex] = oldCopy[i];    
        }

        for(int i = queueOfNodesTailIndex; i < queueOfNodes.length;i++, newArrayIndex++) {
            newArray[newArrayIndex] = oldCopy[i];
            newTailIndex = newArrayIndex;
        }

        queueOfNodesHeadIndex = 0;
        queueOfNodesTailIndex = newTailIndex;

        queueOfNodes = newArray;

    }

 

Dequeue works by removing the end of the queue, if possible. Pretty straightforward:    

public void deQueue() {
        if(size <= 1) {
            if(size == 1) {
                queueOfNodes[queueOfNodesHeadIndex] = null;
                size--;
            }
            
            queueOfNodesHeadIndex = 0;
            queueOfNodesTailIndex = 0;

        }
        else {
            queueOfNodes[queueOfNodesHeadIndex] = null;

            if(queueOfNodesHeadIndex == queueOfNodes.length -1) {
                queueOfNodesHeadIndex = 0;
            }
            else {
                queueOfNodesHeadIndex++;    
            }


            size--;
        }
    }

 

A simple main method to run the program, and a bunch of test data for you to see the queue in action. You can remove this if you don't want to see exactly what the list looks like after a lot of queuing and dequeuing:

    public static void main(String[] args) {
        Queue testQueue = new Queue();

        testQueue.enQueue(new Integer(1));
        testQueue.enQueue(new Integer(2));
        testQueue.enQueue(new Integer(3));
        testQueue.enQueue(new Integer(4));
        testQueue.enQueue(new Integer(5));

        testQueue.deQueue();
        testQueue.deQueue();
        testQueue.deQueue();
        testQueue.deQueue();


        testQueue.enQueue(new Integer(6));
        testQueue.enQueue(new Integer(7)); 
        testQueue.enQueue(new Integer(8));
        testQueue.enQueue(new Integer(9));

        testQueue.deQueue();

        testQueue.enQueue(new Integer(10));
        testQueue.enQueue(new Integer(11));
        testQueue.enQueue(new Integer(12));
        testQueue.enQueue(new Integer(13));
        testQueue.enQueue(new Integer(14));

        testQueue.deQueue();

        testQueue.deQueue();
        testQueue.deQueue();
        testQueue.deQueue();
        testQueue.deQueue();
        testQueue.deQueue();
        testQueue.deQueue();

        testQueue.enQueue(new Integer(15));
        testQueue.deQueue();
        testQueue.deQueue();
        testQueue.deQueue();

        testQueue.enQueue(new Integer(16));
        testQueue.enQueue(new Integer(17));
        testQueue.enQueue(new Integer(18));
        testQueue.enQueue(new Integer(19));
        testQueue.enQueue(new Integer(20));
        testQueue.enQueue(new Integer(21));
        testQueue.enQueue(new Integer(22));

        testQueue.deQueue();
        testQueue.deQueue();
        testQueue.deQueue();
        testQueue.deQueue();
        testQueue.deQueue();
        testQueue.deQueue();

        testQueue.enQueue(new Integer(23));
        testQueue.deQueue();
        testQueue.enQueue(new Integer(24));
        testQueue.enQueue(new Integer(25));
        testQueue.deQueue();
        testQueue.deQueue();
        testQueue.enQueue(new Integer(26));
        testQueue.deQueue();
        testQueue.deQueue();
        
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < testQueue.queueOfNodes.length ; i++) {
            sb.append(testQueue.queueOfNodes[i] + ", ");
        }

        System.out.println("End: ");
        System.out.println(sb);
        System.out.println("Tail: " + testQueue.queueOfNodesTailIndex);
        System.out.println("Head: " + testQueue.queueOfNodesHeadIndex);
        System.out.println("Size: " + testQueue.size);

    }

}

 

So you might have noticed that this performs kinda similarly to a stack (Because it kinda does). The main difference here is that we're taking from the bottom of the stack, as opposed to the top. This means that the queue is FIFO (First-in, first-out) whereas the stack is LIFO (Last-in, first-out). If you picture stacks of plates and queues at an escalator, you've pretty much nailed the concept!

Good luck!