This article is a record of LeetCode641 problem design loop double – end queue idea. (PS: THERE will be another article in the future, when I get the implementation of the bidirectional linked list clear, one pointer is still clear, two Pointers pre and Next look a little dizzy, wait for me to digest.)

Let’s look at the problem:

Design and implement a double – ended queue. Your implementation needs to support the following:

MyCircularDeque(k) : constructor, double-ended queue size k. InsertFront () : Adds an element to the head of a double-ended queue. Returns true on success. InsertLast () : Adds an element to the end of a double-ended queue. Returns true on success. DeleteFront () : Removes an element from the head of a double-ended queue. Returns true on success. DeleteLast () : Removes an element from the end of a two-ended queue. Returns true on success. GetFront () : Gets an element from the head of a two-ended queue. If the two-end queue is empty, -1 is returned. GetRear () : Gets the last element of a two-ended queue. If the two-end queue is empty, -1 is returned. IsEmpty () : checks whether the double-ended queue isEmpty. IsFull () : checks whether the two-end queue isFull. Example:

MyCircularDeque circularDeque = new MycircularDeque(3); Circulardeque.insertlast (1); // Set the capacity to 3 circulardeque.insertlast (1); // Return true circulardeque.insertlast (2); / / return true circularDeque. InsertFront (3); / / return true circularDeque. InsertFront (4); // Already full, return false circulardeque.getrear (); Circulardeque.isfull (); // Return true circulardeque.deletelast (); / / return true circularDeque. InsertFront (4); // Return true circulardeque.getFront (); / / return 4

It is well known that stacks and queues are restricted data structures, which are often used in some business scenarios. Stacks and queues can be implemented using two basic data structures: arrays and linked lists. Today we’ll start by looking at how to design a looping double-ended queue using arrays.

class MyCircularDeque {

    private int[] items;
    private int count;
    private int head;
    private int tail;

    public MyCircularDeque(int k) {
        this.count = k+1;
        this.items = new int[count];
        this.head = 0;
        this.tail = 0;
    }

    public boolean insertFront(int value) {
        if (isFull()) {
            return false;
        }
        head = (head - 1 + count) % count;
        items[head] = value;
        return true;
    }

    public boolean insertLast(int value) {
        if (isFull()) {
            return false;
        }
        items[tail] = value;
        tail = (tail + 1) % count;
        return true;
    }

    public boolean deleteFront(a) {
        if (isEmpty()) {
            return false;
        }
        head = (head + 1) % count;
        return true;
    }

    public boolean deleteLast(a) {
        if (isEmpty()) {
            return false;
        }
        tail = (tail - 1 + count) % count;
        return true;
    }

    public int getFront(a) {
        if (isEmpty()) {
            return -1;
        }
        return items[head];
    }

    public int getRear(a) {
        if (isEmpty()) {
            return -1;
        }
        return items[(tail - 1 + count) % count];
    }

    public boolean isEmpty(a) {
        return head == tail;
    }

    public boolean isFull(a) {
        return (tail + 1) % count == head; }}Copy the code

First of all, you can imagine the circular queue as a ring, which is connected at the beginning and the end. Moreover, the position of its elements is always moving with the insertion and deletion, so the efficiency is actually low. The insertion of elements will involve data migration, so the industrial queue is generally realized by linked list.

Then explain a few member variables:

  • Items [], the array that is actually used to store data
  • Count, the exact size of the entire array
  • Head, the subscript position of the header pointer
  • Tail: subscript position of the tail pointer. The last element is subscript (tail-1+count)%count, so it’s a waste of space.

To design this, we first consider the constructor, because there are k elements and tail takes up one more position, so we actually need k+1 space. Head and tail both start at 0.

Instead of inserting and deleting, let’s look at the two basic functions, isEmpty() and isFull(), which will be much easier to write after we define them.

The condition for isEmpty() is easy to imagine: head==tail; .

(tail+1)%count==head; (tail+1)%count==head; The reason for modulo count is that tail+1 can exceed count, and head is actually at 0. Keep in mind that the %count operation is often used to evaluate the subscript of a circular queue.

These two basic implementations are much easier to implement than the others.

InsertFront (value) checks if the queue is full, returns false if it is, and otherwise sets the value stored in head-1 to value. We need to consider that head-1 is negative when head=0, so we need head-1+count to make it positive count in modulo.

InsertLast (value) does the same thing, but you can think about it yourself.

(head+1)%count (head+1)%count (head+1)%count (head+1)%count (head+1)%count (head+1)%count (head+1)%count (head+1)%count The reason is that we access all the elements of the array through head and tail, and if head and tail can’t access it, it doesn’t really matter what the element is. ** You might say does it matter when you insert, but the answer is no, because when you insert, it doesn’t matter what value was in memory before.

DeleteLast () = (tail-1+count)%count = (tail-1+count)%count

GetFront () checks whether the queue is empty, returns -1, otherwise returns Items[head].

Item [(tail-1+count)%count] = items[(tail-1+count)%count]

Write in the last

Array implementation is much less efficient than linked list implementation because array insertion and deletion will involve subsequent data migration, which is time-consuming. Linked list implementations are much faster.