Implement a two-end Deque hand by hand

Happy New Year, everybody. Did you go out?

Today’s two-endian queue principle is simple, but very powerful, perfect for holiday reading. The complete code is at the end.

An array is a very useful data structure. For most programming languages, arrays tend to be stored in a contiguous memory space (JS arrays are not). It supports fast access to any indexed element (start value + index * offset). It allows us to access any value in the array in order one time.

However, everything is good and everything is bad, and inserting and deleting elements in native arrays can be a headache, especially at the beginning of an array. If we need to insert an element at the beginning, all the elements need to be moved back one bit to make room.

Today, our array-based implementation of a double-endian queue (Deque) solves these problems, allowing us to insert and delete elements at the beginning and end of an array with an average time of O(1).

Of course, that’s just a feature of it. We can also easily implement stack and circular queues based on our implementation of the two-endian queue.

First, let’s look at the main functions of our queue by interface:

public interface Deque<E> {
    int getSize(a);
    void isEmpty(a);
    void addFront(E e);
    void addLast(E e);
    E removeFront(a);
    E removeLast(a);
    E getFront(a);
    E getLast(a);
}
Copy the code

We just use addLast and removeLast to make it a stack. We just use addLast and removeFront to turn it into a queue.

Now that we’ve defined our interfaces, we can get a sense of what our dual-endian queues can do. Now we’re going to implement them one by one. Before we can implement each method, we need to emit our constructor:

public class ArrayDeque<E> {
    private E[] data;
    private int front;
    private int tail;
    private int size;

    public ArrayDeque(int capacity) {
        data = (E[]) new Object[capacity];
        front = tail = size = 0;
    }
    
    public ArrayDeque(a) {
        this(10); }}Copy the code

Now, I don’t know why some variables are defined, but it doesn’t matter, we’ll see.

We use the size variable to hold the size of our queue and change it as we add and remove it. Let’s start with the simplest getSize method:

public int getSize(a) {
    return size;
}
Copy the code

And then there’s the size variable, which we’re going to use to determine whether the queue is empty or full.

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

What about when it’s full? There is only one condition:

size == data.length
Copy the code

Some of you may have noticed that we kept the front and tail variables for initialization. In fact, we can declare null or full according to the relative position of the head pointer and the tail pointer. We’re using the size variable, so it’s a little bit easier, and we’re not wasting any space, and we’re not wasting any space. For those of you who are interested, consider how to operate using head and tail Pointers.

We’re going to use front to point to the first element of our queue, not necessarily the first element of our array. Use tail to point to the last element of our queue, not necessarily the last element of our array.

When we add elements at the beginning of the queue, front moves “left”;

When we remove an element at the beginning of the queue, front moves “right”;

When we add an element to the end of the queue, tail moves “right”;

When we delete an element at the end of the queue, tail moves “left”;

Either front or tail is similar to a round-robin graph, regardless of whether the queue is full or empty. And when I go to the left, I go back to the end of the array. If you go right to the end, you go back to the beginning of the array.

Let’s look at how to add an element at the beginning of an array, and there are two ways to do that.

When front does not point to index 0:

In the current case, inserting an element is simply an assignment at index 1. I’m going to increase size by 1.

whenfrontWhen the index is 0:

Our next front should be the last position in the array, data.length-1.

Here is the code we added:

public void addFront(E e) {
    if (size == data.length) {
        resize(2 * data.length); 
    }

    front = front == 0 ? data.length - 1 : front - 1;
    data[front] = e;
    size++;
}
Copy the code

What is resize? Its main function is to dynamically expand or shrink, so in our case, when the queue is full, we expand it by twice, and when the queue actually holds only a quarter of the elements, we shrink it by half.

Some of you are going to ask, why didn’t you just shrink to a half when you had a half? This is to avoid frequent scaling and scaling at the 1/2 point of the array. When the queue is full, we will expand the queue, and the expanded element only stands half of the total capacity. At this time, deleting one element triggers the reduction of the size, and so on. So we’re going to shrink at a quarter.

private void resize(int newCapacity) {
    E[] newData = (E[]) new Object[newCapacity];

    for (int i = 0; i < data.length; i++) {
        newData[i] = data[(front + i) % data.length];
    }

    data = newData;
    front = 0;
    tail = size;
}
Copy the code

Note that we need to reset front and tail after copying.

Let’s examine how to delete an element at the beginning of an array:

In this case, removing an element is simple: make the element currently pointed to by front equal to null and add 1 to front.

Another case we need to consider when our front points to the last element is that the overall order of the elements in our queue is: 3, 6, 5, 1, 2,3. Delete front and set front to null and set front to index 0.

There are two cases, but the code for both is the same:

public E removeFront(a) {
    if (isEmpty()) {
        throw new IllegalArgumentException("Deque is empty");
    }

    E ret = data[front];

    data[front] = null;
    front += (front + 1) % data.length;
    size--;

    if (getSize() == data.length / 4 && getSize() / 2! =0) {
        resize(data.length / 2);
    }

    return ret;
}
Copy the code

We have analyzed the beginning of adding and removing elements. That leaves two more: adding and removing elements at the end of the array. Understand the above process, actually these two methods are relatively simple, but the operation pointer changes to tail, some students can not, please ask in the comment section, I am there.

public void addLast(E e) {
    if (getSize() == data.length) {
        resize(2 * data.length);
    }

    data[tail] = e;
    tail = (tail + 1) % data.length;
    size++;
}
Copy the code

public E removeLast(a) {
    if (isEmpty()) {
        throw new IllegalArgumentException("Deque is empty");
    }

    tail = tail == 0 ? data.length - 1 : tail - 1;

    E ret = data[tail];
    data[tail] = null;
    size--;

    if (getSize() == data.length / 4 && getSize() / 2! =0) {
        resize(data.length / 2);
    }

    return ret;
}
Copy the code

So, we have analyzed a two-ended queue, the complete code is as follows:

public class ArrayDeque<E> {
    private E[] data;
    private int front;
    private int tail;
    private int size;

    public ArrayDeque(int capacity) {
        data = (E[]) new Object[capacity];
        front = tail = size = 0;
    }

    public ArrayDeque(a) {
        this(10);
    }

    public int getSize(a) {
        return size;
    }

    public void addFront(E e) {
        if (getSize() == data.length) {
            resize(2 * data.length);
        }

        front = front == 0 ? data.length - 1 : front - 1;
        data[front] = e;
        size++;
    }

    public void addLast(E e) {
        if (getSize() == data.length) {
            resize(2 * data.length);
        }

        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];

        for (int i = 0; i < data.length; i++) {
            newData[i] = data[(front + i) % data.length];
        }

        data = newData;
        front = 0;
        tail = size;
    }

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

    public E removeFront(a) {
        if (isEmpty()) {
            throw new IllegalArgumentException("Deque is empty");
        }

        E ret = data[front];

        data[front] = null;
        front += (front + 1) % data.length;
        size--;

        if (getSize() == data.length / 4 && getSize() / 2! =0) {
            resize(data.length / 2);
        }

        return ret;
    }

    public E removeLast(a) {
        if (isEmpty()) {
            throw new IllegalArgumentException("Deque is empty");
        }

        tail = tail == 0 ? data.length - 1 : tail - 1;

        E ret = data[tail];
        data[tail] = null;
        size--;

        if (getSize() == data.length / 4 && getSize() / 2! =0) {
            resize(data.length / 2);
        }

        return ret;
    }

    public E getFront(a) {
        if (isEmpty()) {
            throw new IllegalArgumentException("Deque is empty");
        }
        return data[front];
    }

    public E getLast(a) {
        if (isEmpty()) {
            throw new IllegalArgumentException("Deque is empty");
        }

        return data[tail == 0 ? data.length - 1 : tail - 1]; }}Copy the code