Реалізація Deque за допомогою кругового масиву


Рівень складності Medium
Часто запитують у Амазонка GE Healthcare Google Microsoft
масив Зв’язаний список Чергу

Постановка проблеми

«Впровадження Deque за допомогою кругового масиву» просить реалізувати наступні функції Deque (Подвійно закінчена черга) за допомогою кругового масиву,

  1. insertFront (x) : вставити елемент x спереду Deque
  2. insertRear (x) : вставте елемент x у задній частині Deque
  3. deleteFront () : видалити елемент з передньої частини Deque
  4. deleteRear () : видалити елемент із задньої сторони Deque
  5. getFront () : повернути елемент, присутній в передній частині Deque
  6. getRear () : повернути елемент, який знаходиться в задній частині Deque
  7. пусто() : повертає, чи не є Deque порожнім
  8. isFull () : повертає, незаповнено чи ні

Приклад

вхід
вставити спереду (5)
insertRear (10)
insertRear (11)
вставити спереду (19)
getFront ()
getRear ()
isFull ()
deleteRear ()
getRear ()
deleteFront ()
getFront ()
пусто()

Вихід
19
11
false
10
5
false

Алгоритм реалізації Deque за допомогою кругового масиву

Впровадити Deque використовуючи круговий масив, нам потрібно відстежувати два покажчика спереду та ззаду в масиві. Всі операції відбуватимуться на цих двох покажчиках.
Значення кругового масиву можна зрозуміти на зображенні нижче

Реалізація Deque за допомогою кругового масиву

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

Створіть масив розміром n, де n - максимальний розмір Deque та ініціалізуйте фронт та зад як -1 перед будь-якою операцією на Deque.
Оскільки масив має круговий приріст спереду або ззаду, коли вони присутні в кінці масиву, вони перенесуть їх до початкової точки, і аналогічно зменшенню спереду і ззаду, коли вони знаходяться у вихідній точці, вони проведуть їх до кінця масив.

insertFront (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)

isFull ()

Якщо (тил + 1)% n дорівнює фронту, тоді Deque заповнений, інакше це не так. Тут n - максимальний розмір Деке.

Складність часу = 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

Код С ++ для реалізації 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