پیاده سازی Deque با استفاده از لیست پیوندی دوگانه


سطح دشواری متوسط
اغلب در خشت خوشحال آمازون امریکن اکسپرس دی شاو واقعیت فورکایت GE بهداشت و درمان گوگل Oxigen Wallet سامسونگ 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 با استفاده از یک لیست پیوندی مضاعف. ما دو نشانگر جلو و عقب را حفظ می کنیم ، جایی که جلو به جلو از یک لیست مضاعف و نقاط عقب به انتها اشاره می کند. همچنین ما باید یک عدد صحیح size ، تعداد گره ها را در Deque ذخیره می کند.

به درج ، حذف، یا از ابتدا یک عنصر بدست آورید ما از جلو اشاره گر

به درج ، حذف، یا از انتها یک عنصر بگیرید ما از عقب اشاره گر

پیاده سازی Deque با استفاده از لیست پیوندی دوگانه

insertFront (x)

برای قرار دادن یک عنصر در جلوی Deque ، موارد زیر را انجام دهید

  1. یک گره جدید با مقدار مورد نیاز ایجاد کنید و آن را گره بنامید.
  2. اگر جلو تهی است ، جلو و عقب را با گره برابر کنید.
  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. اگر عقب تهی است ، جلو و عقب را برابر با گره کنید.
  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. اگر جلو خالی است ، هیچ عنصری برای حذف وجود ندارد ، به راحتی برگردانید.
  2. اگر جلو برابر با عقب است ، فقط 1 گره وجود دارد ، جلو و عقب را پوچ کنید.
  3. دیگر ، جلو را برابر با 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--

حذفEnd ()

برای حذف یک عنصر از انتهای Deque ، موارد زیر را انجام دهید

  1. اگر عقب خالی است ، گره ای برای حذف وجود ندارد ، به راحتی برگردید.
  2. اگر عقب برابر با جلو باشد ، فقط یک گره وجود دارد ، جلو و عقب را پوچ کنید.
  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 توسط جلو مشخص شده است ، بنابراین اگر جلو خالی است ، جلو را برگردانید. داده ها

پیچیدگی زمان = O (1)

کد شبه

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

getEnd ()

عنصر انتهایی Deque توسط عقب نشان داده می شود ، بنابراین اگر عقب خالی نیست ، به عقب برگردید. داده ها

پیچیدگی زمان = O (1)

کد شبه

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

خالی است()

اگر Deque خالی باشد ، جلو و عقب نیز پوچ خواهند بود ، بنابراین اگر جلو خالی است ، درست است ، غیرفعال کنید false.

پیچیدگی زمان = O (1)

کد شبه

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

اندازه()

اندازه Deque در متغیری به نام 'size' ذخیره می شود ، بنابراین به سادگی اندازه را برگردانید.

پیچیدگی زمان = O (1)

کد شبه

return size

پاک کردن()

پاک کردن Deque به معنی حذف تمام گره های Deque است. برای حذف همه گره ها موارد زیر را انجام دهید ،

  1. عقب را به صورت null تنظیم کنید.
  2. با اشاره به جلو ، یک نشانگر موقت ایجاد کنید.
  3. در Deque عبور کرده و مرحله 4 را تکرار کنید ، یعنی در حالی که جلو مرحله 4 نیست ، تکرار می شود.
  4. temp را به عنوان جلو ، جلو را به عنوان front.next تنظیم کرده و فضا را برای temp اختصاص دهید.
  5. در آخر temp را به صورت null و جلو را به صورت 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