Внедряване на Deque с помощта на кръгов масив


Ниво на трудност M
Често задавани в Амазонка GE Healthcare Google Microsoft
Array Свързан списък Опашка

Декларация за проблема

„Внедряване на Deque с помощта на кръгов масив“ изисква да се изпълнят следните функции на Deque (Двойно завършена опашка) с помощта на кръгов масив,

  1. вмъкване отпред (x) : поставете елемент x в предната част на Deque
  2. insertRear (x) : поставете елемент x в задната част на Deque
  3. deleteFront () : изтриване на елемент от предната страна на Deque
  4. deleteRear () : изтриване на елемент от задната страна на Deque
  5. getFront () : връща елемента, присъстващ в предната част на Deque
  6. getRear () : връща елемента, присъстващ в задната част на Deque
  7. празно е() : връща дали Deque е празен или не
  8. е пълен() : върнете дали Deque е пълен или не

Пример

Вход
вмъкване отпред (5)
insertRear (10)
insertRear (11)
вмъкване отпред (19)
getFront ()
getRear ()
е пълен()
deleteRear ()
getRear ()
deleteFront ()
getFront ()
празно е()

Продукция
19
11
фалшив
10
5
фалшив

Алгоритъм за изпълнение на Deque с помощта на кръгов масив

За изпълнение Deque използвайки кръгъл масив, ние трябва да следим два указателя отпред и отзад в масива. Всички операции ще бъдат върху тези два указателя.
Значението на кръговия масив може да се разбере от изображението по-долу

Внедряване на Deque с помощта на кръгов масив

На това изображение задната част е отпред, т.е. когато задната част е в края на масива и има няколко празни слота в началото на масива, така че вмъкването на елемент отзад ще доведе до задната позиция да дойде в позиция 0 , това е така, защото кръговото масив има кръгов характер.

Създайте масив с размер n, където n е максималният размер на Deque и инициализирайте отпред и отзад като -1 преди всяка операция върху Deque.
Тъй като масивът е кръгово нарастване отпред или отзад, когато те присъстват в края на масива, ще ги отведе до началната точка и по подобен начин намаляването отпред и отзад, когато са в началната точка, ще ги отведе до края на масив.

вмъкване отпред (x)

  1. Ако масивът е пълен, елементът не може да бъде вмъкнат.
  2. Ако в Deque (или масив) няма елементи, т.е. фронтът е равен на -1, нараства отпред и отзад и задава arr [front] като x.
  3. В противен случай намалете отпред и задайте arr [отпред] като x.

Сложност във времето = O (1)

insertRear ()

  1. Ако масивът е пълен, елементът не може да бъде вмъкнат.
  2. Ако в Deque няма елементи, т.е.зад е равен на -1, увеличете отпред и отзад и задайте arr [задна] като x.
  3. В противен случай се увеличава отзад и се задава arr [отзад] като x.

Сложност във времето = O (1)

deleteFront ()

  1. Ако Deque е празен, върнете се.
  2. Ако в Deque има само един елемент, т.е. отпред е равно на заден, задайте отпред и отзад като -1.
  3. Друго увеличение отпред с 1.

Сложност във времето = O (1)

deleteRear ()

  1. Ако Deque е празен, върнете се.
  2. Ако в Deque има само един елемент, т.е.зад е равен отпред, задайте отпред и отзад като -1.
  3. Друго намаление отзад с 1.

Сложност във времето = O (1)

getFront ()

  1. Ако Deque е празен, върнете се.
  2. Друг обратен обръч [отпред].

Сложност във времето = O (1)

getRear ()

  1. Ако Deque е празен, върнете се.
  2. Друг обратен обръщане [отзад].

Сложност във времето = O (1)

празно е()

Ако фронтът е равен на -1, Deque е празен, в противен случай не е.

Сложност във времето = O (1)

е пълен()

Ако (отзад + 1)% n е равно на предната част, тогава Deque е пълен, в противен случай не е така. Тук n е максималният размер на Deque.

Сложност във времето = O (1)

Java код за внедряване на Deque с помощта на кръгов масив

class ImplementationOfDequeUsingCircularArray {
    // Maximum size of Deque
    private static final int MAX_SIZE = 100;
    // Array to implement Deque
    private static int deque[];
    // Variables to represent front and rear of dequeue
    private static int front = -1;
    private static int rear = -1;

    private static void insertFront(int x) {
        // if array is not full
        if (!isFull()) {
            // case 1 : there are no elements
            // increment front and rear and add element at arr[front]
            if (front == -1) {
                front = rear = 0;
                deque[front] = x;
            }
            // else, decrement front circularly and add the
            // new element at arr[front]
            else {
                if (front == 0) {
                    front = MAX_SIZE - 1;
                } else {
                    front--;
                }
                deque[front] = x;
            }
        }
    }

    private static void insertRear(int x) {
        // if array is not full
        if (!isFull()) {
            // if this is the first element to be inserted
            // increment front and rear and add element at arr[rear]
            if (rear == -1) {
                front = rear = 0;
                deque[rear] = x;
            }
            // else increment rear circularly and add
            // new element at arr[rear]
            else {
                if (rear == MAX_SIZE - 1) {
                    rear = 0;
                } else {
                    rear++;
                }
                deque[rear] = x;
            }
        }
    }

    private static void deleteFront() {
        // if array is not empty
        if (!isEmpty()) {
            // if there is only 1 element
            // make front and rear as -1
            if (front == rear) {
                front = rear = -1;
            }
            // else increment front circularly
            else {
                if (front == MAX_SIZE - 1) {
                    front = 0;
                } else {
                    front++;
                }
            }
        }
    }

    private static void deleteRear() {
        // if array is not empty
        if (!isEmpty()) {
            // if there is only 1 element
            // make front and rear as -1
            if (front == rear) {
                rear = front = -1;
            }
            // else decrement rear circularly
            else {
                if (rear == 0) {
                    rear = MAX_SIZE - 1;
                } else {
                    rear--;
                }
            }
        }
    }

    private static int getFront() {
        // if array is not empty return arr[front]
        if (!isEmpty()) {
            return deque[front];
        }
        return -1;
    }

    private static int getRear() {
        // if array is not empty return arr[rear]
        if (!isEmpty()) {
            return deque[rear];
        }
        return -1;
    }

    private static boolean isEmpty() {
        // if front is -1 then deque is empty
        if (front == -1) {
            return true;
        }
        return false;
    }

    private static boolean isFull() {
        // if front is 1 ahead of rear then
        // deque is full
        if ((rear + 1) % MAX_SIZE == front) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
         deque = new int[MAX_SIZE];

         // Example
        insertFront(5);
        insertRear(10);
        insertRear(11);
        insertFront(19);
        System.out.println(getFront());
        System.out.println(getRear());
        System.out.println(isFull());
        deleteRear();
        System.out.println(getRear());
        deleteFront();
        System.out.println(getFront());
        System.out.println(isEmpty());
    }
}
19
11
false
10
5
false

C ++ код за внедряване на Deque с помощта на кръгов масив

#include <iostream>
using namespace std;

// Maximum size of Deque
const int MAX_SIZE = 100;
// Array to implement Deque
int deque[MAX_SIZE];
// Variables to represent front and rear of dequeue
int front = -1;
int rear = -1;

bool isEmpty() {
    // if front is -1 then deque is empty
    if (front == -1) {
        return true;
    }
    return false;
}

bool isFull() {
    // if front is 1 ahead of rear then
    // deque is full
    if ((rear + 1) % MAX_SIZE == front) {
        return true;
    }
    return false;
}

void insertFront(int x) {
    // if array is not full
    if (!isFull()) {
        // case 1 : there are no elements
        // increment front and rear and add element at arr[front]
        if (front == -1) {
            front = rear = 0;
            deque[front] = x;
        } 
        // else, decrement front circularly and add the
        // new element at arr[front]
        else {
            if (front == 0) {
                front = MAX_SIZE - 1;
            } else {
                front--;
            }
            
            deque[front] = x;
        }
    }
}

void insertRear(int x) {
    // if array is not full
    if (!isFull()) {
        // if this is the first element to be inserted
        // increment front and rear and add element at arr[rear]
        if (rear == -1) {
            front = rear = 0;
            deque[rear] = x;
        } 
        // else increment rear circularly and add
        // new element at arr[rear]
        else {
            if (rear == MAX_SIZE - 1) {
                rear = 0;
            } else {
                rear++;
            }
            
            deque[rear] = x;
        }
    }
}

void deleteFront() {
    // if array is not empty
    if (!isEmpty()) {
        // if there is only 1 element
        // make front and rear as -1
        if (front == rear) {
            front = rear = -1;
        } 
        // else increment front circularly
        else {
            if (front == MAX_SIZE - 1) {
                front = 0;
            } else {
                front++;
            }
        }
    }
}

void deleteRear() {
    // if array is not empty
    if (!isEmpty()) {
        // if there is only 1 element
        // make front and rear as -1
        if (front == rear) {
            front = rear = -1;
        } 
        // else decrement rear circularly
        else {
            if (rear == 0) {
                rear = MAX_SIZE - 1;
            } else {
                rear--;
            }
        }
    }
}

int getFront() {
    // if array is not empty return arr[front]
    if (!isEmpty()) {
        return deque[front];
    }
    return -1;
}

int getRear() {
    // if array is not empty return arr[rear]
    if (!isEmpty()) {
        return deque[rear];
    }
    return -1;
}

int main() {
    // Example
    insertFront(5);
    insertRear(10);
    insertRear(11);
    insertFront(19);
    cout<<getFront()<<endl;
    cout<<getRear()<<endl;
    if (isFull()) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    deleteRear();
    cout<<getRear()<<endl;
    deleteFront();
    cout<<getFront()<<endl;
    if (isEmpty()) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
19
11
false
10
5
false