Имплементација на Deque со употреба на двојно поврзана листа


Ниво на тешкотија Медиум
Често прашувано во Adobe Вознемиреност Амазон american Express ДЕ Шо Факти Фуркити ГЕ здравство Google Оксигенски паричник Квалком Spotify Прскалка UHG Optum Вукер Xome ZScaler
Деквиве Поврзан список редот Теорија

Изјава за проблем

Проблемот „Имплементација на Deque со употреба на двојно поврзана листа“ наведува дека треба да ги имплементирате следниве функции на Деке или Двојно заврши редицата со користење на двојно поврзана листа,

  1. insertFront (x): Додадете елемент x на почетокот на Deque
  2. insertEnd (x): Додадете елемент x на крајот на Deque
  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.

До вметнете, избришетеили добиете елемент од почеток ние го користиме пред покажувач

До вметнете, избришетеили добиете елемент од крајот ние го користиме задните покажувач

Имплементација на Deque со употреба на двојно поврзана листа

вметнете пред (x)

За да вметнете елемент на предната страна на Deque, направете го следново

  1. Создадете нов јазол со потребната вредност и наречете го јазол.
  2. Ако предниот дел е нула, направете ги предниот и задниот дел да бидат еднакви на јазолот.
  3. Друго, вметнете го јазолот пред предната страна и означете го јазолот како нов фронт.
  4. Големина на зголемување

Временска комплексност О (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++

вметнете крај (x)

За да вметнете елемент на крајот од Deque, направете го следново

  1. Создадете нов јазол со потребната вредност и наречете го јазол.
  2. Ако задниот дел е нула, направете го предниот и задниот дел е еднаков на јазолот.
  3. Друго, вметнете го јазолот по задниот дел и означете го јазолот како нов заден дел.
  4. Големина на зголемување

Временска комплексност О (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++

избришиFront ()

За да избришете елемент од предниот дел на Deque, направете го следново

  1. Ако предниот дел е ништовен, нема елемент за бришење, едноставно вратете се.
  2. Ако предниот дел е еднаков на задниот дел, има само 1 јазол, направете ги предните и задните нула.
  3. Друго, направете го предниот дел е еднаков на предниот дел. Следниот и избришете го предниот дел
  4. Големина на декрет

Временска сложеност = О (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--

избришете го крајот ()

За да избришете елемент од крајот на Deque, направете го следново

  1. Ако задниот дел е нула, нема јазол за бришење, едноставно вратете се.
  2. Ако задниот дел е еднаков на предниот дел, има само еден јазол, направете ги предните и задните нула.
  3. Друго направете го задниот дел како заден дел. Претходниот и избришете го задниот дел.
  4. Големина на декрет

Временска сложеност = О (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 е насочен напред, па ако предниот дел не е ништовен, вратете се напред

Временска сложеност = О (1)

Псевдо код

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

getEnd ()

Крајниот елемент на Deque е означен со заден дел, па ако задниот дел не е ништовен, вратете се назад.податоци

Временска сложеност = О (1)

Псевдо код

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

е празно()

Ако Deque е празен, и предниот и задниот дел ќе бидат ништовни, па ако предната е нула, вратете точно, инаку вратете неточно.

Временска сложеност = О (1)

Псевдо код

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

големина ()

Големината на Deque е зачувана во променливата наречена „големина“, затоа едноставно вратете ја големината.

Временска сложеност = О (1)

Псевдо код

return size

избрише ()

Бришење на Deque значи бришење на сите јазли на Deque. За да ги избришете сите јазли, направете го следново

  1. Поставете го задниот дел како ништовен.
  2. Создадете привремен темпер на покажувачот, покажувајќи напред.
  3. Поминете низ Deque и повторете го чекорот 4, односно додека предниот дел не е ништовен, повторете го чекор 4.
  4. Поставете го температурата како пред, предниот како предниот. Следно и одвојте го просторот за температурата.
  5. Конечно поставете temp како нула и напред како null и поставете ја големината како 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 користејќи список со двојно поврзаност

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

C ++ код за имплементација на Deque користејќи список со двојно поврзаност

#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