[알고리즘] JAVA programming language - 2: Queue data structure

Introduction

Queue data structure follows First In First Out (FIFO) order. Not like Stack data structure, Queue allows the least recently added value to be freed the earliest. Thus, Queue data structure is more in accordance with common sense in reality familiar to us.

Implementation

Since Queue takes out the value pushed the earliest above all, two pointers are required for tracking the working principle. These pointers are called rear() and front(). When inserting a new value to a queue, namely a behaviour "Enqueue", only rear() of a queue is referred and changed. On the other hand, for "Dequeue", which is as expected a deletion of a value from a queue, front() of a queue is always modified. This is how Queue data structure behaves not only on Java but in general.

Methods

Some of the methods with which Java Queue class provides include the following:

 

1. offer(value) / add(value)

import java.util.Queue;
import java.util.LinkedList;
    
public class QueueDataStructure {
    public static void main(String[] args) {
	Queue<Integer> queue = new LinkedList<>();
	queue.offer(2);
        queue.add(5);
        System.out.println(queue);
    }
}

code block 1-1: Code snippets that add integer values 2 and 5 to Queue data structure and print.

 

As shown above, LinkedList class is utilised to initalise Queue. Both offer() and add() introduce a new element to a structure (Enqueue), add() throws exception to confirm the failure of insertion while offer() returns boolean value false. The output of code snippets above is as below:

[2, 5]

2. remove() / poll()

import java.util.Queue;
import java.util.LinkedList;
    
public class QueueDataStructure {
    public static void main(String[] args) {
	Queue<Integer> queue = new LinkedList<>();
    	int element1 = 0;
        int element2 = 0;
    
	queue.offer(2);
        queue.add(5);
        element1 = queue.remove();
        element2 = queue.poll();
        System.out.println(queue);
        System.out.println();
        System.out.println("Element erased: " + element1);
        System.out.println();
        System.out.println("Element erased: " + element2);
    }
}

code block 1-2: Code snippets that delete integer values 5 and 2 from Queue data structure and print a state of Queue and a value just deleted using poll().

 

Either remove() or poll() may be a method that dequeues data value from Queue. Since Queue only allows the value to be deleted from "front()", no parameter is required for the methods. Both behave similarly, while the returned values are distinct. poll() returns null when Queue.isEmpty() is true, and remove() throws exception. The code snippets above outputs as below, here we can observe that queue was dequeued in a same order it has been enqueued:

[]

Element erased: 2

Element erased: 5

Conclusion

Queue data structure follows FIFO order, thus more appropriate in a situation where early birds take advantages. Not like Stack, there are two methods each for inserting and deleting values from structure.

Queue is useful in:
1. Realising Breadth first search algorithm
2. Computer buffer for lining up waiting inputs