Data Structures (4) – Queue implementation

This is the 12th day of my participation in the First Challenge 2022

The concept of a Queue

A queue is a special linear table that allows operations only at the head and tail of the queue. EnQueue adds an element to the end of the queue. Removing an element from the head of a queue is a deQueue. The queue is First In First Out.

Queue method design

int size(a); // Get the number of elements in the queue
boolean isEmpty(a); // Check whether the queue is empty
void enQueue(T element); // add elements to the end of the column
T deQueue(a); // Remove the element in the header
T front(a); // Get the header element of the queue
void clear(a); // Clear the queue
Copy the code

Queue head and tail operations are frequent and can be implemented based on bidirectional linked lists

Second, the implementation of the queue

Create Module 05-queue in data-structures project, put bidirectional LinkedList LinkedList, abstract LinkedList AbstractList, interface List in com.citi. List package for queue reference. Copy the utility classes from Utils into the com.citi package. Create a new class queue.Queue and make LinkedList private

public class Queue<T> {

    // The private attribute LinkedList
    private List<T> list = new LinkedList<>();

    public int size(a){

        return 0;
    }
    public boolean isEmpty(a){
        return false;
    }
    public void enQueue(T element){}public T deQueue(a){
       return null;
    }
    public T front(a){
        return null;
    }
    public void clear(a){}}Copy the code

Size () and isEmpty() methods

public int size(a){
    return list.size();
}
public boolean isEmpty(a){
    return list.isEmpty();
}
Copy the code

EnQueue () joins the queue, adding elements to the end of the queue (adding elements to the end of the list)

public void enQueue(T element){
    list.add(element);
}
Copy the code

DeQueue () removes the element at the head of the queue (removes the linked header element, index 0)

public T deQueue(a){
   return list.remove(0);
}
Copy the code

Front (), gets the queue header element

public T front(){
    return list.get(0);
}
Copy the code

clear()

public void clear(a){
    list.clear();
}
Copy the code

Create a new test class QueueTest

public class QueueTest {

    Queue<Integer> queue = null;

    @Before
    public void init(a){
        queue = new Queue<>();
        queue.enQueue(10);
        queue.enQueue(20);
        queue.enQueue(30);
        System.out.println("Init Queue：" + queue);
    }

    @Test
    public void enQueue(a) {
        queue.enQueue(50);
        System.out.println("The enQueue Queue," + queue);
    }

    @Test
    public void deQueue(a) {
        queue.deQueue();
        System.out.println("To deQueue Queue," + queue);
    }

    @Test
    public void front(a) {
        System.out.println("Front Queue: "+ queue.front()); }}Copy the code

Let’s rewrite the toString method before we test it

@Override
public String toString(a) {
    return "Queue{" +
            "list=" + list +
            '} ';
}
Copy the code

Perform the test

Use Stack to implement Queue

public class QueueByStack {

    private Stack<Integer> inStack = new Stack<>();
    private Stack<Integer> outStack = new Stack<>();

    public void push(int x){
        inStack.push(x);
    }

    public int pop(a){
        checkOutStack();
        return outStack.pop();
    }

    public int peek(a){
        checkOutStack();
        return outStack.peek();
    }

    public boolean empty(a){
        return inStack.isEmpty() && outStack.isEmpty();
    }

    public void checkOutStack(a){
        if (outStack.isEmpty()){
            while(! inStack.isEmpty()){ outStack.push(inStack.pop()); }}}}Copy the code

Two – end queue

A double-ended queue is also a queue that can be added and removed at both ends.

Design of two – end queue method

int size(a); // Get the number of elements in the queue
boolean isEmpty(a); // Check whether the queue is empty
void enQueueRear(T element); // add elements to the end of the column
T deQueueFront(a); // Remove the element in the header
void enQueueFront(T element); // Enter the column from the head
T deQueueRear(a); // This tail deletes elements
T front(a); // Get the header element of the queue
T rear(a); // Get the tail element
void clear(a); // Clear the queue
Copy the code

Add a queue Deque based on LinkedList

public class Deque<T> {

    private List<T> list = new LinkedList<>();

    public int size(a){
        return list.size();
    }
    public boolean isEmpty(a){
        return list.isEmpty();
    }
    public void clear(a){ list.clear(); }}Copy the code

A double-ended queue adds and removes elements from the beginning to the end

public void enQueueRear(T element){
    list.add(element);
}

public T deQueueFront(a){
    return list.remove(0);
}

public void enQueueFront(T element){
    list.add(0, element);
}

public T deQueueRear(a){
    return list.remove(list.size() - 1);
}
Copy the code

Gets the elements at the head and tail of a double-ended queue

public T front(a){
    return list.get(0);
}

public T rear(a){
    return list.get(list.size() - 1);
}
Copy the code

The test class

public class DequeTest {

    Deque<Integer> deque = null;

    @Before
    public void init(a){
        deque = new Deque<>();
        deque.enQueueRear(10);
        deque.enQueueRear(20);
        deque.enQueueRear(30);
        System.out.println("Init Queue：" + deque);
    }


    @Test
    public void enQueueRear(a) {
        deque.enQueueRear(40);
        System.out.println("After enQueueRear: " + deque);
        
    }

    @Test
    public void deQueueFront(a) {
        deque.enQueueFront(0);
        System.out.println("After deQueueFront: " + deque);
    }

    @Test
    public void enQueueFront(a) {
        deque.enQueueFront(40);
        System.out.println("After enQueueFront: " + deque);
    }

    @Test
    public void deQueueRear(a) {
        deque.deQueueRear();
        System.out.println("After deQueueRear: " + deque);
    }

    @Test
    public void front(a) {
        System.out.println("Front:" + deque.front());
    }

    @Test
    public void rear(a) {
        System.out.println("Rear:"+ deque.rear()); }}Copy the code

Add toString to the Deque class

@Override
public String toString(a) {
    return "Deque{" +
            "list=" + list +
            '} ';
}
Copy the code

Execute all test methods in the test class

Fourth, circular queue

The bottom layer of the loop queue is implemented using an array, which has a front attribute, specifying an index in the array as the head of the queue. Front refers to the index in the array, which is of type int. Front does not necessarily mean the position of index 0

Delete element demo

When the queue head deletes an element, it moves front back one place. When the queue head deletes an element again, it moves front back one place. Front is always smaller than the size of the array

Add element demo

When adding an element, we add the element to the end of the array. The front position is always the same. When there is no space on the right side, we loop through the left side of the array to add an element

Adding to an array when there is no space on the left of the array requires dynamic expansion. A loop in a loop queue is a loop when adding elements.

Circular queues have the same methods as normal queues

Circular queue implementation

public class CircleQueue<T> {

    private int size;
    private T[] elements;

    public static final int DEFAULT_CAPACITY = 10;

    // Defines the length of the array
    public CircleQueue(a){
        elements = (T[]) new Object[DEFAULT_CAPACITY];
    }
    public int size(a){
        return size;
    }

    public boolean isEmpty(a){
        return size == 0; }}Copy the code

Gets the queue header element

public T front(a){
   return elements[front];
}
Copy the code

Append element whose index is smaller than the array size

public void enQueue(T element){
    elements[(front + size) % elements.length] = element;
    size++;
}
Copy the code

Removes the queue header element. Front is smaller than the array size

public T deQueue(a){
    // Get the correct element first
    T frontEle = elements[front];
    // Empty the header element
    elements[front] = null;
    // The head of the queue should move back once
    // front++;
    front = (front + 1) % elements.length;
    / / the length - 1
    size--;
    // return the header element
    return frontEle;
}
Copy the code

Clear the elements in the queue, iterate over all the elements, set to NULL

public void clear(a){
    for (int i = 0; i < elements.length; i++) {
        elements[i] = null;
    }
    size = 0;
    front = 0;
}
Copy the code

Adding test classes

public class CircleQueueTest {

    CircleQueue<Integer> queue = null;

    @Before
    public void init(a){
        queue = new CircleQueue<>();
        queue.enQueue(11);
        queue.enQueue(22);
        queue.enQueue(33);
        System.out.println("Init CircleQueue: " + queue);
    }

    @Test
    public void front(a) {

        System.out.println("CircleQueue Front: " + queue.front());
    }

    @Test
    public void enQueue(a) {

        queue.enQueue(55);
        System.out.println("After enQueue: " + queue);
    }

    @Test
    public void deQueue(a) {
        queue.deQueue();
        System.out.println("After deQueue: "+ queue); }}Copy the code

Add toString method

@Override
public String toString(a) {
    return "CircleQueue{" +
            "front=" + front +
            ", size=" + size +
            ", elements=" + Arrays.toString(elements) +
            '} ';
}
Copy the code

Execute all test methods

Special case test

@Test
public void deQueueAndEnQueue(a) {
    for (int i = 0; i < 3; i++) {
        queue.deQueue();
    }
    System.out.println("After deQueue: " + queue);
    for (int i = 0; i < 4; i++) {
        queue.enQueue(i + 100);
    }
    System.out.println("After enQueue: " + queue);
    for (int i = 0; i < 8; i++) {
        queue.deQueue();
    }
    System.out.println(queue);
}
Copy the code

Adding capacity Expansion methods

private void expansionCapacity(int newCapacity){
    int oldCapacity = elements.length;
    if (oldCapacity >= size + 1) return;

    // Create an array of new capacities
    // newCapacity = oldCapacity + (oldCapacity >> 1);
    T[] newElements = (T[]) new Object[newCapacity];
    // Copy the element
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[(i + front) % elements.length];
    }
    // Points to a new memory space
    elements = newElements;
    front = 0;
    System.out.println("Capacity expansion succeeded." + oldCapacity + "Extend to" + newCapacity);
}
Copy the code

Modify the enQueue method code

public void enQueue(T element){
    expansionCapacity(elements.length + (elements.length >> 1));
    elements[(front + size) % elements.length] = element;
    size++;
}
Copy the code

Expansion test code

@Test
public void testExpansion(a) {
    queue.deQueue();
    System.out.println(queue);
    for (int i = 0; i < 3; i++) {
        queue.enQueue(i);
    }

    System.out.println(queue);
    for (int i = 0; i < 3; i++) {
        queue.deQueue();
    }
    System.out.println("After deQueue: " + queue);
    for (int i = 0; i < 4; i++) {
        queue.enQueue(i + 100);
    }
    System.out.println("After enQueue: " + queue);
    for (int i = 0; i < 8; i++) {
        queue.deQueue();
    }
    System.out.println(queue);
}
Copy the code

Perform the test

5. Loop double – ended queue

A circular queue that can be added and deleted at both ends

Create a new CircleDeque

public class CircleDeque<T> {

    private int front;
    private int size;
    private T[] elements;

    public static final int DEFAULT_CAPACITY = 10;

    // Defines the length of the array
    public CircleDeque(a){
        elements = (T[]) new Object[DEFAULT_CAPACITY];
    }
    public int size(a){
        return size;
    }
    
    public boolean isEmpty(a){
        return size == 0;
    }

    public void clear(a){
        for (int i = 0; i < elements.length; i++) {
            elements[index(i)] = null;
        }
        size = 0;
        front = 0;
    }

    public int index(int index){
        return (front + index) % elements.length;
    }

    private void expansionCapacity(int newCapacity){
        int oldCapacity = elements.length;
        if (oldCapacity >= size + 1) return;

        // Create an array of new capacities
        // newCapacity = oldCapacity + (oldCapacity >> 1);
        T[] newElements = (T[]) new Object[newCapacity];
        // Copy the element
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[(i + front) % elements.length];
        }
        // Points to a new memory space
        elements = newElements;
        front = 0;
        System.out.println("Capacity expansion succeeded." + oldCapacity + "Extend to" + newCapacity);
    }

    @Override
    public String toString(a) {
        return "CircleQueue{" +
                "front=" + front +
                ", size=" + size +
                ", elements=" + Arrays.toString(elements) +
                '} '; }}Copy the code

Gets the header and tail elements

public T front(a){
    return elements[front];
}

public T rear(a){
    return elements[index(front + size - 1)];
}
Copy the code

Joining the queue from the tail and removing the queue from the head are consistent with the method of two-ended queuing

// Enter the queue from the rear
public void enQueueRear(T element){
    expansionCapacity(elements.length + (elements.length >> 1));
    elements[(front + size) % elements.length] = element;
    size++;
}

// Exit from the head
public T deQueueFront(a){
    // Get the correct element first
    T frontEle = elements[front];
    // Empty the header element
    elements[front] = null;
    // The head of the queue should move back once
    // front++;
    front = (front + 1) % elements.length;
    / / the length - 1
    size--;
    // return the header element
    return frontEle;
}
Copy the code

If front is 0, then insert position -1, there is no index -1 in the array, use -1 + array length to create the index in the real array, index method needs to add judgment

public int index(int index){
    index += front;
    if (index < 0) {return index + elements.length;
    }
    return (front + index) % elements.length;
}
Copy the code

From the tail out of the team and from the head into the team method

// Exit from the rear
public T deQueueRear(a){
    // Get the real index
    int rearIndex = index(size - 1);
    T rear = elements[rearIndex];
    elements[rearIndex] = null;
    size--;
    return rear;
}

// Enter the team from the head
public void enQueueFront(T element){
    expansionCapacity(elements.length + (elements.length >> 1));
    front = index(front - 1);
    elements[front] = element;
    size ++;
}
Copy the code

New Test class

public class CircleDequeTest {

    CircleDeque<Integer> deque = null;

    @Before
    public void init(a){
        deque = new CircleDeque<>();
        for (int i = 0; i < 8; i++) {
            deque.enQueueRear(i + 10);
        }

        System.out.println("After Init" + deque);
    }

    @Test
    public void front(a) {
        System.out.println("CircleDeque Front: " + deque.front());
    }

    @Test
    public void rear(a) {
        System.out.println("CircleDeque Rear: " + deque.rear());
    }

    @Test
    public void enQueueRear(a) {
        deque.enQueueRear(18);
        System.out.println("After enQueueRear:" + deque);
    }

    @Test
    public void deQueueFront(a) {
        deque.deQueueFront();
        System.out.println("After deQueueFront: " + deque);
    }

    @Test
    public void deQueueRear(a) {
        deque.deQueueRear();
        System.out.println("After deQueueRear: " + deque);
    }

    @Test
    public void enQueueFront(a) {
        deque.enQueueFront(9);
        System.out.println("After enQueueFront: "+ deque); }}Copy the code

Perform the test