Queue Introduction - 队列简介

Made by Mike_Zhang

---

数据结构与算法主题：

---

1 Introduction to Queue

Queue (队列) is another fundamental data structure, which is similar to the Stack

A queue is a collection of objects that are inserted and removed according to the first-in, first-out (FIFO) principle, while Stack is LIFO.

[Example]
Like the queue in the real life:
the first person got in the queue will first get the ticket and leave the queue, while the last person in the queue will be the last one get the ticket.

Image: Goodrich, M., Tamassia, R., & O’reilly, A. (2014). Data Structures and Algorithms in Java, 6th Edition. John Wiley & Sons.

---

2 Queue Abstract Data Type

See what is the Abstract Data Type

enqueue(e): Add an element e to the back of the queue;
dequeue(): Remove and return the first element of the queue, or null if the queue is empty;

first(): Return but NOT remove the first element of the queue, or null if the queue is empty;
size(): Return the number of elements in the queue;
isEmpty(): Return a boolean value indicating whether the queue is empty.

Define the Queue interface:

public interface Queue<E> {
    int size();
    boolean isEmpty();
    void enqueue(E e);
    E dequeue();
    E first();
}

---

3 java.util.Queue Interface

Queue - Java SE 17

Queue ADT	java.util.Queue throws exceptions	java.util.Queue returns special value
enqueue(E e)	add(E e)	offer(E e)
dequeue()	remove(E e)	poll()
first()	element()	peek()
size()	size()	size()
isEmpty()	isEmpty()	isEmpty()

---

4 Queue ADT Implementations

4.1 Implement Queue Using Array

• Using an array data to store the elements in the stack, with fixed size of the array, $N$.
• Using the array circularly by indicating 2 variables:
  • f: indicate the index of the first element of Queue in the array, (f + 1) % data.length; indicates the new front of the Queue in the array when calling dequeue();
  • size: indicate the number of elements in the Queue, using (f + sz) % data.length to indicate the index of the tail of the Queue in the array when calling enqueue(E e).

Java implementation:

// implements the above Queue Interface
public class ArrayQueue<E> implements Queue<E> { 

    private E[] data; // Using array to store elements in the Queue
    private static final int CAPACITY = 100; // Default capacity 100
    private int f = 0; // indicate the index of the first element of Queue in the array
    private int size = 0; // indicate the number of elements in the Queue

    public ArrayQueue() {
        this(CAPACITY);
    }
    public ArrayQueue(int inSize) {
        data = (E[]) new Object[inSize];
    }

    public int size() { // return the size of the Queue
        return size;
    }

    public boolean isEmpty() { // check whether the Queue si empty or not
        return (size == 0);
    }

    public void enqueue(E e) throws IllegalStateException{ // Add an element to the back of the queue
        if (size == data.length) { // check whether the queue is full
            throw new IllegalStateException("The queue is full!");
        }
        else {
            int pos = (f + size) % data.length; // get the position of the tail
            data[pos] = e;
            size ++;
        }
    }

    public E dequeue(){ // Remove and return the first element of the queue
        if (isEmpty()) { // Check whether the queue is empty or not
            return null;
        }
        else {
            E out = data[f];
            data[f] = null;
            f = (f + 1) % data.length; // let the front point to the next position
            size --;
            return out;
        }
    }

    public E first() { // return the front element of the queue
        if (isEmpty()) {
            return null;
        }
        else {
            return data[f];
        }
    }

    public String toString() {
        String outString = "front -> ";
        for (int i = 0; i < size; i++) {
            int ind = (i+f)% data.length;
            outString = outString + data[ind] + " ";
        }
        outString = outString + "<- tail";
        return outString;
    }
}

Test:

public static void main(String[] arg) {
    Queue<Integer> queue = new ArrayQueue<Integer>();
    System.out.println(queue.isEmpty()); // true
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    System.out.println(queue.size()); // 3
    System.out.println(queue.toString()); // 1 2 3
    System.out.println(queue.first()); // 1
    System.out.println(queue.dequeue()); // 1
    System.out.println(queue.first()); // 2
    queue.enqueue(4);
    System.out.println(queue.toString()); // 2 3 4
}

Result:

true
3
front -> 1 2 3 <- tail
1
1
2
front -> 2 3 4 <- tail

---

Advantages of using an array to implement the Queue:

• Simple and efficient;

  • Each method just includes some primitive operations, which is easy to understand and implement.

  • Running time of each method:

Method	Running time
size()	$O(1)$
isEmpty()	$O(1)$
enqueue(e)	$O(1)$
dequeue()	$O(1)$
first()	$O(1)$

• Therefore, using Array to implement the Queue is efficient, for each method runs in constant time, $O(1)$ time.

---

Drawbacks of using an array to implement the Queue:

• It is based on a fixed size of the array, $N$, which means the size of the Queue is fixed, limited and unchangeable, while the the actual size of the Queue is dynamic.
  • If we needs much less space than the reserved size, memory is wasted.
  • If we try to enqueue an element into the Queue when the array storage is full, the program will throw an exception, and we cannot enqueue any more elements into the Queue.

To solve the above problem, we can use a LinkedList to implement the Queue.

---

4.2 Implement Queue Using LinkedList

• Using a singly linked list to store the elements in the queue;
• The memory usage is always associated with the actual number of elements in the Queue, without a capacity limitation;
• According to the queue ADT, we can adapt our SinglyLinkedList class to define a new LinkedQueue class:

Methods in Queue	Method in SingleLinkedList
size()	getSize()
isEmpty()	isEmpty()
enqueue(e)	addAtTail(e)
dequeue()	deleteAtHead()
first()	getHead()

Java implementation:

(Import the SingleLinkedList class from the post-Linked List Introduction - 链表简介)

public class LinkedQueue<E> implements Queue<E> {
    private SinglyLinkedList<E> list = new SinglyLinkedList<E>();
    public LinkedQueue() {}
    public int size() {
        return list.getSize();
    }
    public boolean isEmpty() {
        return list.isEmpty();
    }
    public void enqueue(E element) {
        list.addAtTail(element);
    }
    public E dequeue() {
        return list.deleteAtHead();
    }
    public E first() {
        return list.getHead();
    }
    public String toString() {
        return "first ->"+list.toString()+"<- tail";
    }
}

Test:

public static void main(String[] arg) {
    Queue<Integer> queue = new LinkedQueue<>();
    System.out.println(queue.isEmpty()); // true
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    System.out.println(queue.size()); // 3
    System.out.println(queue.toString()); // 1 2 3
    System.out.println(queue.first()); // 1
    System.out.println(queue.dequeue()); // 1
    System.out.println(queue.first()); // 2
    queue.enqueue(4);
    System.out.println(queue.toString()); // 2 3 4
}

Result:

true
3
first ->1 2 3 <- tail
1
1
2
first ->2 3 4 <- tail

---

5 Circular Queue

We have discussed Circularly Linked List in the post - Linked List Introduction - 链表简介.

Similarly, there is CircularQueue interface extends from Queue with a useful rotate() method:

public interface CircularQueue<E> extends Queue<E> {
    void rotate();
}

CircularQueue can be implemented by using CircularlyLinkedList to generate the LinkedCircularQueue:

(Import the CircularlyLinkedList class from the post-Linked List Introduction - 链表简介)

public class LinkedCircularQueue <E> implements CircularQueue<E> {
    private CircularlyLinkedList<E> list = new CircularlyLinkedList<>();
    public LinkedCircularQueue() {}
    public int size() {
        return list.getSize();
    }
    public boolean isEmpty() {
        return list.isEmpty();
    }
    public void enqueue(E element) {
        list.addAtTail(element);
    }
    public E dequeue() {
        return list.deleteAtHead();
    }
    public E first() {
        return list.getHeadData();
    }

    public void rotate() {
        list.rotate();
    }

    public String toString() {
        return "first ->"+list.toString()+"<- tail";
    }
}

---

5.1 Circular Queue Application - Josephus Problem

I have studied and discussed Josephus Problem in the post - Python对约瑟夫问题(Josephus Problem)的高效解决方法 with Python implementation.

Now, it is also easy and efficient to solve this problem with Circular Queue because the basic of Josephus Problem is rotate and dequeue, which can be easily implemented by Circular Queue.

public class Josephus {
    public static <E> E Josephus(CircularQueue<E> queue, int m) {
        if (queue.isEmpty()) {
            return null;
        }
        while (queue.size() > 1) {
            for (int i=0; i < m-1; i++) {
                // Rotate the queue to pass to the next person
                queue.rotate(); 
            }
            // Remove the target one
            E out = queue.dequeue();
            System.out.println(out+" OUT");
        }
        // The last one is the winner
        return queue.dequeue();
    }

    // Build CircularQueue from Array
    public static <E> CircularQueue<E> buildCircularQueue(E inList[]) {
        CircularQueue<E> queue = new LinkedCircularQueue<>( );
        for (int j=0; j<inList.length;j++) {
            queue.enqueue(inList[j]);
        }
        return queue;
    }
}

Test:

public static void main(String[] arg) {
    String[] players = {"Alice", "Bob", "Cindy", "Doug", "Ed", "Fred"};
    System.out.println(Josephus(buildCircularQueue(players),2)+" WIN");
}

Result:

Bob OUT
Doug OUT
Fred OUT
Cindy OUT
Alice OUT
Ed WIN

The result is correct and can be verified by the UltraFish Plus - Python对约瑟夫问题的高效解决方法 Josephus Problem with Python

---

References

Goodrich, M., Tamassia, R., & O’reilly, A. (2014). Data Structures and Algorithms in Java, 6th Edition. John Wiley & Sons.

---

写在最后

Queue 相关的知识会继续学习，继续更新.
最后，希望大家一起交流，分享，指出问题，谢谢！

---

原创文章，转载请标明出处
Made by Mike_Zhang

感谢你的支持