დეკის განხორციელება ორმაგად დაკავშირებული სიის გამოყენებით


Რთული ტური საშუალო
ხშირად ეკითხებიან Adobe ალაცია Amazon American Express დე შოუ ფაქტები Fourkites GE Healthcare Google ოქსიგენის საფულე Qualcomm Spotify სპრინკლერი UHG Optum ვუკერი Xome ZScaler
დიქეიკი მიბმული სია Queue თეორია

პრობლემის განცხადება

პრობლემა "დეკის განხორციელება ორმაგად დაკავშირებული სიის გამოყენებით" აცხადებს, რომ თქვენ უნდა შეასრულოთ შემდეგი ფუნქციები დეკე ან ორმაგად დასრულდა რიგის გამოყენება ორმაგად დაკავშირებული სია,

  1. insertFront (x): დაამატე x ელემენტი Deque– ს დასაწყისში
  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– ს კვანძების რაოდენობას.

დან ჩასმა, წაშლა, ან თავიდანვე მიიღე ელემენტი ჩვენ ვიყენებთ წინა მაჩვენებელი

დან ჩასმა, წაშლა, ან მიიღეთ ელემენტი ბოლოდან ჩვენ ვიყენებთ უკანა მაჩვენებელი

დეკის განხორციელება ორმაგად დაკავშირებული სიის გამოყენებით

ჩასმა წინა (x)

დეკის წინა ელემენტის ჩასასმელად გააკეთეთ შემდეგი

  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++

ჩასმა ბოლო (x)

დეკის ბოლოს ელემენტის ჩასასმელად გააკეთეთ შემდეგი

  1. შექმენით ახალი კვანძი საჭირო მნიშვნელობით და უწოდეთ მას კვანძი.
  2. თუ უკანა მხარე არის 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. თუ წინა არის null, არ არსებობს ელემენტი, რომ წაშალოთ, უბრალოდ დაბრუნდით.
  2. თუ წინა ტოლია უკანა მხარეს, არის მხოლოდ 1 კვანძი, გააკეთეთ წინა და უკანა მხარე.
  3. სხვა, გააკეთე წინა ტოლი წინა. შემდეგი და წაშლა წინა. წინამორბედი
  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. თუ უკანა მხარე არის null, აღარ არსებობს კვანძი, რომ წაშალოთ, უბრალოდ დაბრუნდით.
  2. თუ უკანა წინა ტოლია, მხოლოდ ერთი კვანძია, გააკეთეთ წინა და უკანა მხარე.
  3. შემდეგ გააკეთე უკანა მხარე, როგორც უკანა. წინა და წაშალე უკანა. შემდეგი.
  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- ს წინა ელემენტი მითითებულია წინა მხრიდან, ასე რომ, თუ წინა არ არის null, დაბრუნდით წინ. მონაცემები

დროის სირთულე = O (1)

ფსევდო კოდი

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

getEnd ()

Deque- ის ბოლო ელემენტი უკანა მხარეს არის მითითებული, ასე რომ, თუ უკანა მხარე არ არის null, უკანა. მონაცემები

დროის სირთულე = O (1)

ფსევდო კოდი

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

ცარიელია()

თუ Deque ცარიელია წინა და უკანაც გაუქმდება, ასე რომ, თუ წინა არის null, დაბრუნდით true, სხვა შემთხვევაში დაბრუნდით false.

დროის სირთულე = O (1)

ფსევდო კოდი

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

ზომა ()

Deque- ს ზომა ინახება ცვლადში, სახელწოდებით 'size', ასე რომ, უბრალოდ დააბრუნეთ ზომა.

დროის სირთულე = O (1)

ფსევდო კოდი

return size

წაშლა ()

Deque- ს წაშლა ნიშნავს Deque- ს ყველა კვანძის წაშლას. ყველა კვანძის წასაშლელად გააკეთეთ შემდეგი,

  1. დააყენეთ უკანა მხარე, როგორც ნული.
  2. შექმენით დროებითი მაჩვენებლის დრო, მიუთითეთ წინა მხარეს.
  3. გაიარეთ Deque– ში და გაიმეორეთ მე –4 ნაბიჯი, ანუ წინა არ არის null განმეორებითი ნაბიჯი 4.
  4. დააყენეთ temp როგორც წინა, წინა როგორც წინა. შემდეგი და გამოყავით სივრცე ტემპერატურისთვის.
  5. დაბოლოს, დააყენეთ დრო, როგორც null და წინა, როგორც null და დააყენეთ ზომა, როგორც 0.

დროის სირთულე = O (n), სადაც 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