원형 배열을 사용한 Deque 구현

난이도 중급
자주 묻는 질문 아마존 GE 헬스 케어 구글 Microsoft
배열 연결된 목록 조회수 36

문제 정책

“원형 배열을 이용한 Deque 구현”은 원형 배열을 이용한 Deque (Dubly Ended Queue)의 다음 기능을 구현하도록 요청하고 있습니다.

  1. insertFront (x) : Deque 앞에 요소 x 삽입
  2. insertRear (x) : Deque 뒤쪽에 요소 x 삽입
  3. deleteFront () : Deque 전면에서 요소 삭제
  4. deleteRear () : Deque 뒷면에서 요소 삭제
  5. getFront () : Deque 앞에있는 요소를 반환합니다.
  6. getRear () : Deque 뒤쪽에있는 요소를 반환합니다.
  7. 비었다() : Deque가 비어 있는지 여부를 반환합니다.
  8. 가득() : Deque가 가득 찼는 지 여부를 반환합니다.

입력
insertFront (5)
insertRear (10)
insertRear (11)
insertFront (19)
getFront ()
getRear ()
가득()
deleteRear ()
getRear ()
deleteFront ()
getFront ()
비었다()

산출
19
11
그릇된
10
5
그릇된

원형 배열을 사용한 Deque 구현 알고리즘

구현 데케 원형 배열을 사용하여 배열의 앞뒤 두 포인터를 추적해야합니다. 모든 작업은이 두 포인터에 있습니다.
원형 배열의 의미는 아래 이미지로 이해할 수 있습니다.

원형 배열을 사용한 Deque 구현

이 이미지에서 후면은 전면 뒤에 있습니다. 즉 후면이 어레이의 끝에 있고 어레이 시작 부분에 빈 슬롯이 있었기 때문에 후면에 요소를 삽입하면 후면이 위치 0에있게됩니다. , 이것은 원형이기 때문입니다 정렬 본질적으로 원형입니다.

크기 n의 배열을 만들고, 여기서 n은 Deque의 최대 크기이며, Deque에서 작업을 수행하기 전에 전면과 후면을 -1로 초기화합니다.
어레이가 어레이의 끝에있을 때 전면 또는 후면이 원형 증분이므로 시작점으로 이동하고 시작점에있을 때 전면 및 후면을 감소 시키면 끝으로 이동합니다. 정렬.

insertFront (x)

  1. 배열이 가득 차면 요소를 삽입 할 수 없습니다.
  2. Deque (또는 배열)에 요소가없는 경우 즉, front는 -1이고 앞뒤를 증가시키고 arr [front]를 x로 설정합니다.
  3. 그렇지 않으면 front를 감소시키고 arr [front]를 x로 설정합니다.

시간 복잡성 = O (1)

insertRear ()

  1. 배열이 가득 차면 요소를 삽입 할 수 없습니다.
  2. Deque에 요소가없는 경우, 즉 rear가 -1이면 앞뒤를 증가시키고 arr [rear]를 x로 설정합니다.
  3. 그렇지 않으면 후방을 증가시키고 arr [rear]를 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. 그렇지 않으면 arr [front]를 반환합니다.

시간 복잡성 = O (1)

getRear ()

  1. Deque가 비어 있으면 반환하십시오.
  2. 그렇지 않으면 arr [rear]를 반환합니다.

시간 복잡성 = O (1)

비었다()

front가 -1이면 Deque는 비어 있고 그렇지 않으면 비어 있습니다.

시간 복잡성 = O (1)

가득()

(후면 + 1) % n이 전면과 같으면 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
Translate »