이중 연결 목록을 사용한 Deque 구현

문제 정책

“이중 연결 목록을 사용하여 Deque 구현”문제는 다음 기능을 구현해야 함을 나타냅니다. 데케 또는 이중으로 종료 된 대기열 연결 목록,

1. insertFront (x) : Deque 시작 부분에 요소 x 추가
2. insertEnd (x) : Deque 끝에 요소 x 추가
3. deleteFront () : Deque 시작 부분에서 요소 삭제
4. deleteEnd () : Deque 끝에서 요소 삭제
5. getFront () : Deque 시작 부분의 요소를 반환합니다.
6. getEnd () : Deque 끝에있는 요소를 반환합니다.
7. isEmpty () : Deque가 비어 있는지 여부를 반환합니다.
8. size () : Deque의 크기를 반환
9. erase () : Deque의 모든 요소를 ​​삭제합니다.

예

insertFront(5)
insertEnd(10)
insertEnd(11)
insertFront(19)
getFront()
getEnd()
deleteEnd()
getEnd()
deleteFront()
getFront()
size()
isEmpty()
erase()
isEmpty()

19
11
10
5
2
false
true

암호알고리즘

이중 연결 목록을 사용하여 Deque를 구현합니다. 앞과 뒤 두 개의 포인터를 유지합니다. 앞쪽은 이중 연결 목록의 앞을 가리키고 뒤쪽은 끝을 가리 킵니다. 또한 우리는 정수 Deque에 노드 수를 저장하는 크기입니다.

에 삽입, 삭제및 시작부터 요소를 얻다 우리는 앞 바늘.

에 삽입, 삭제및 끝에서 요소를 얻다 우리는 후방 바늘.

핀

insertFront (x)

Deque 앞에 요소를 삽입하려면 다음을 수행하십시오.

1. 필요한 값으로 새 노드를 만들고 노드라고합니다.
2. 전면이 null이면 전면과 후면을 노드와 같게 만듭니다.
3. 그렇지 않으면 노드를 전면 앞에 삽입하고 노드를 새 전면으로 표시합니다.
4. 크기 증가

시간 복잡성 O (1)

의사 코드

Create a new node with required value and call it node
if (front == null) {
  front = rear = node
} else {
  node.next = front
  front.prev = node
  front = node
}
size++

insertEnd (x)

Deque 끝에 요소를 삽입하려면 다음을 수행하십시오.

1. 필요한 값으로 새 노드를 만들고 노드라고합니다.
2. rear가 null이면 전면과 후면을 노드와 동일하게 만듭니다.
3. 그렇지 않으면 노드 뒤에 노드를 삽입하고 노드를 새 후면으로 표시하십시오.
4. 크기 증가

시간 복잡성 O (1)

의사 코드

Create a new node with required value and call it node
if (rear == null) {
  front = rear = node
} else {
  rear.next = node
  node.prev = rear
  rear = node
}
size++

deleteFront ()

Deque 앞에서 요소를 삭제하려면 다음을 수행하십시오.

1. front가 null이면 삭제할 요소가없는 경우 반환하기 만하면됩니다.
2. 전면이 후면과 같으면 노드가 1 개 뿐이고 전면과 후면을 null로 만듭니다.
3. 그렇지 않으면 front를 front.next와 같게 만들고 front.prev를 삭제합니다.
4. 크기 감소

시간 복잡성 = O (1)

의사 코드

if (front == null) {
  return
}
if (front == rear) {
  front = rear = null
} else {
  temp = front
  front = front.next
  front.prev = null
  deallocate space for temp
}
size--

deleteEnd ()

Deque 끝에서 요소를 삭제하려면 다음을 수행하십시오.

1. rear가 null이면 삭제할 노드가없는 경우 반환하면됩니다.
2. rear가 front와 같으면 노드가 하나 뿐이고 front와 rear를 null로 만듭니다.
3. 그렇지 않으면 rear.prev로 만들고 rear.next를 삭제하십시오.
4. 크기 감소

시간 복잡성 = O (1)

의사 코드

if (rear == null) {
  return;
}
if (rear == front) {
  front = rear = null
} else {
  temp = rear
  rear = rear.prev
  rear.next = null
  deallocate space for temp
}
size--

getFront ()

Deque의 앞 요소는 앞쪽을 가리 키므로 front가 null이 아니면 front.data를 반환합니다.

시간 복잡성 = O (1)

의사 코드

if (front != null) {
  return front.data
}
return -1

getEnd ()

Deque의 끝 요소는 뒤쪽을 가리 키므로 rear가 null이 아니면 rear.data를 반환하십시오.

시간 복잡성 = O (1)

의사 코드

if (rear != null) {
  return rear.data
}
return -1

비었다()

Deque가 비어 있으면 앞면과 뒷면이 모두 null이되므로 front가 null이면 true를 반환하고 그렇지 않으면 false를 반환합니다.

시간 복잡성 = O (1)

의사 코드

if (front == null) {
  return true
}
return false

크기()

Deque의 크기는 'size'라는 변수에 저장되므로 단순히 size를 반환합니다.

시간 복잡성 = O (1)

의사 코드

return size

삭제()

Deque 지우기는 Deque의 모든 노드를 삭제하는 것을 의미합니다. 모든 노드를 삭제하려면 다음을 수행하십시오.

1. 뒤쪽을 null로 설정합니다.
2. 앞을 가리키는 임시 포인터 온도를 만듭니다.
3. Deque에서 횡단하고 4 단계를 반복합니다. 즉, front가 null이 아닌 동안 4 단계를 반복합니다.
4. temp를 front로, front를 front.next로 설정하고 temp 공간을 할당 해제합니다.
5. 마지막으로 temp를 null로, front를 null로 설정하고 size를 0으로 설정합니다.

시간 복잡성 = 의 위에), 여기서 n은 Deque의 노드 수입니다.

의사 코드

rear = null
Node temp = front
while (front != null) {
  temp = front
  front.prev = null
  front = front.next
  deallocate space for temp
}
temp = front = null
size = 0

암호

이중 연결 목록을 사용하여 Deque 구현을위한 Java 코드

class DequeUsingDoublyLinkedList {
    // class representing Node of a doubly linked list
    static class Node {
        int data;
        Node next, prev;

        public Node(int data) {
            this.data = data;
        }
    }

    // front points to start of Deque and rear points to the end of Deque
    private static Node front = null;
    private static Node rear = null;
    private static int size = 0;

    private static void insertFront(int x) {
        // Create a new Node with required parameters
        Node node = new Node(x);
        if (front == null) {
            // This is the first node to be inserted
            front = rear = node;
        } else {
            // Add the node before front
            node.next = front;
            front.prev = node;
            // update front
            front = node;
        }
        // Increment size
        size++;
    }

    private static void insertEnd(int x) {
        // Create a new Node with required parameters
        Node node = new Node(x);
        if (rear == null) {
            // This is the first node to be inserted
            front = rear = node;
        } else {
            // Insert the node after rear
            rear.next = node;
            node.prev = rear;
            // update rear
            rear = node;
        }
        // Increment size
        size++;
    }
    private static void deleteFront() {
        if (front == null) {
            // no node to delete
            return;
        }
        if (front == rear) {
            // only 1 node is present
            front = rear = null;
        } else {
            // delete front and move front ahead
            front = front.next;
            front.prev = null;
            // Garbage Collector will automatically delete first node
            // as no pointer is pointing to it
        }
        // decrement size
        size--;
    }

    private static void deleteEnd() {
        if (rear == null) {
            // no node to delete
            return;
        }
        if (rear == front) {
            // only 1 node is present
            front = rear = null;
        } else {
            // delete rear and move rear backwards
            rear = rear.prev;
            rear.next = null;
            // Garbage Collector will automatically delete last node
            // as no pointer is pointing to it
        }
        // decrement size
        size--;
    }

    private static int getFront() {
        if (front != null) {
            // front points to first element in Deque, return its data
            return front.data;
        }
        // no node is present
        return -1;
    }

    private static int getEnd() {
        if (rear != null) {
            // rear points to last element in Deque, return its data
            return rear.data;
        }
        // no node is present
        return -1;
    }

    private static boolean isEmpty() {
        if (front == null) {
            return true;
        }
        return false;
    }
    
    private static int size() {
        return size;
    }
    
    private static void erase() {
        // mark rear as null
        rear = null;
        // traverse the doubly linked list
        while (front != null) {
            // delete all the prev pointers
            front.prev = null;
            front = front.next;
        }
        // After this deque looks like
        // a -> b -> c -> d ..., all the previous pointers are destroyed
        // No pointer is pointing to a, so Garbage collector will delete the whole Deque
        
        // set size as 0
        size = 0;
    }

    public static void main(String[] args) {
        // Example
        insertFront(5);                 // 5
        insertEnd(10);                  // 5 <-> 10
        insertEnd(11);                  // 5 <-> 10 <-> 11
        insertFront(19);                // 19 <-> 5 <-> 10 <-> 11
        System.out.println(getFront());
        System.out.println(getEnd());
        deleteEnd();                    // 19 <-> 5 <-> 10
        System.out.println(getEnd());
        deleteFront();                  // 5 <-> 10
        System.out.println(getFront());    
        System.out.println(size());
        System.out.println(isEmpty());
        erase();
        System.out.println(isEmpty());
    }
}

19
11
10
5
2
false
true

이중 연결 목록을 사용한 Deque 구현을위한 C ++ 코드

#include<bits/stdc++.h> 
using namespace std;

// class representing a tree node
class Node {
    public:
    int data;
    Node *next;
    Node *prev;
    
    Node(int d) {
        data = d;
        next = NULL;
        prev = NULL;
    }
};

// function to create a new node
Node* newNode(int x) {
    Node *node = new Node(x);
    return node;
}

// front points to start of Deque and rear points to the end of Deque
Node *front = NULL;
Node *rear = NULL;
// Variable representing size of Deque
int Size = 0;

void insertFront(int x) {
    // Create a new Node with required parameters
    Node *node = newNode(x);
    if (front == NULL) {
        // This is the first node to be inserted
        front = rear = node;
    } else {
        // Add the node before front
        node->next = front;
        front->prev = node;
        // update front
        front = node;
    }
    // Increment size
    Size++;
}

void insertEnd(int x) {
    // Create a new Node with required parameters
    Node *node = newNode(x);
    if (rear == NULL) {
        // This is the first node to be inserted
        front = rear = node;
    } else {
        // Insert the node after rear
        node->prev = rear;
        rear->next = node;
        // update rear
        rear = node;
    }
    // Increment size
    Size++;
}

void deleteFront() {
    if (front == NULL) {
        // no node to delete
        return;
    }
    if (front == rear) {
        // only 1 node is present
        front = rear = NULL;
    } else {
        // delete front and move front ahead
        Node *temp = front;
        front = front->next;
        front->prev = NULL;
        // deallocate the memory taken by temp
        delete(temp);
    }
    // Decrement size
    Size--;
}

void deleteEnd() {
    if (rear == NULL) {
        // no node to delete
        return;
    }
    if (front == rear) {
        // only 1 node is present
        front = rear = NULL;
    } else {
        // delete rear and move rear backwards
        Node *temp = rear;
        rear = rear->prev;
        rear->next = NULL;
        // deallocate the memory taken by temp
        delete(temp);
    }
    // Decrement size
    Size--;
}

int getFront() {
    if (front != NULL) {
        return front->data;
    }
    return -1;
}

int getEnd() {
    if (rear != NULL) {
        return rear->data;
    }
    return -1;
}

int size() {
    return Size;
}

bool isEmpty() {
    if (front == NULL) {
        return true;
    }
    return false;
}

void erase() {
    // mark rear as null
    rear = NULL;
    // traverse the doubly linked list
    while (front != NULL) {
        Node *temp = front;
        // delete all the prev pointers
        front->prev = NULL;
        front = front->next;
        // Deallocate the memory taken by temp
        delete(temp);
    }
    // Set size as 0
    Size = 0;
}

int main() {
    // Example
    insertFront(5);                 // 5
    insertEnd(10);                  // 5 <-> 10
    insertEnd(11);                  // 5 <-> 10 <-> 11
    insertFront(19);                // 19 <-> 5 <-> 10 <-> 11
    cout<<getFront()<<endl;
    cout<<getEnd()<<endl;
    deleteEnd();                    // 19 <-> 5 <-> 10
    cout<<getEnd()<<endl;
    deleteFront();                  // 5 <-> 10
    cout<<getFront()<<endl;     
    cout<<size()<<endl;
    if (isEmpty()) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    erase();
    if (isEmpty()) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}

19
11
10
5
2
false
true