循環配列を使用したDequeの実装


難易度 ミディアム
よく聞かれる Amazon (アマゾン) GEヘルスケア Googleポリシー マイクロソフト
配列 リンクリスト キュー

問題文

「循環配列を使用したDequeの実装」では、循環配列を使用してDeque(両端キュー)の次の機能を実装するように求められます。

  1. insertFront(x) :Dequeの前に要素xを挿入します
  2. insertRear(x) :Dequeの背面に要素xを挿入します
  3. deleteFront() :Dequeの前面から要素を削除します
  4. deleteRear() :Dequeの背面から要素を削除します
  5. getFront() :Dequeの前にある要素を返します
  6. getRear() :Dequeの背面にある要素を返します
  7. isEmpty() :Dequeが空かどうかを返します
  8. 一杯() :Dequeがいっぱいかどうかを返します

入力
insertFront(5)
insertRear(10)
insertRear(11)
insertFront(19)
getFront()
getRear()
一杯()
deleteRear()
getRear()
deleteFront()
getFront()
isEmpty()

出力
19
11
false
10
5
false

循環配列を使用してDequeを実装するためのアルゴリズム

実装する デック 円形配列を使用して、配列内の前後のXNUMXつのポインターを追跡する必要があります。 すべての操作は、これらXNUMXつのポインターに対して行われます。
円形配列の意味は下の画像で理解できます

循環配列を使用したDequeの実装

この画像では、後部が前部の後ろにあります。つまり、後部が配列の最後にあり、配列の先頭に空のスロットがいくつかあったため、後部に要素を挿入すると、後部が位置0になります。 、これは円形であるためです 配列 本質的に円形です。

サイズnの配列を作成します。ここで、nはDequeの最大サイズであり、Dequeでの操作の前に、前面と背面を-1として初期化します。
アレイは円形であるため、アレイの最後にある場合は前後にインクリメントされ、開始点に移動します。同様に、開始点にあるときに前後にデクリメントすると、最後に移動します。 配列.

insertFront(x)

  1. 配列がいっぱいの場合、要素を挿入できません。
  2. Deque(または配列)に要素がない場合、つまりfrontが-1に等しい場合は、frontとrearをインクリメントし、arr [front]をxとして設定します。
  3. それ以外の場合は、frontをデクリメントし、arr [front]をxに設定します。

時間の複雑さ = O(1)

insertRear()

  1. 配列がいっぱいの場合、要素を挿入できません。
  2. Dequeに要素がない場合、つまり、rearが-1に等しい場合は、frontとrearをインクリメントし、arr [rear]をxとして設定します。
  3. それ以外の場合は、rearをインクリメントし、arr [rear]をxに設定します。

時間計算量= O(1)

deleteFront()

  1. Dequeが空の場合は、戻ります。
  2. Dequeに要素が1つしかない場合、つまり、frontがrearに等しい場合は、frontとrearを-XNUMXに設定します。
  3. それ以外の場合は、フロントを1ずつ増やします。

時間計算量= O(1)

deleteRear()

  1. Dequeが空の場合は、戻ります。
  2. Dequeに要素が1つしかない場合、つまり、rearがfrontに等しい場合は、frontとrearを-XNUMXに設定します。
  3. それ以外の場合は、リアを1デクリメントします。

時間計算量= O(1)

getFront()

  1. Dequeが空の場合は、戻ります。
  2. それ以外の場合はarr [front]に戻ります。

時間計算量= O(1)

getRear()

  1. Dequeが空の場合は、戻ります。
  2. それ以外の場合は、arr [rear]に戻ります。

時間計算量= O(1)

isEmpty()

frontが-1に等しい場合、Dequeは空です。それ以外の場合は、空ではありません。

時間計算量= O(1)

一杯()

(rear + 1)%nがfrontに等しい場合、Dequeはいっぱいです。そうでない場合は、いっぱいではありません。 ここで、nはDequeの最大サイズです。

時間計算量= O(1)

循環配列を使用してDequeを実装するためのJavaコード

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を実装するためのC ++コード

#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