Амалисозии Deque бо истифодаи Рӯйхати дуҷониба алоқаманд


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Adobe Аля Amazon Амрико Express DE Шо Маълумот Фуркайтҳо GE Тандурустӣ Google Ҳамёни Oxigen Qualcomm Spotify Спринклр Optum UHG Вукер Xome ZScaler
Декю Рӯйхати алоқаманд навбат Теория

Изҳороти мушкилот

Мушкилоти "Татбиқи Deque бо истифодаи Рӯйхати дуҷонибаи алоқаманд" мегӯяд, ки шумо бояд вазифаҳои зеринро иҷро кунед Дек ё Истифодаи дубора бо навбат дубора хотима ёфт рӯйхати алоқаманд,

  1. insertFront (x): Элемент хро дар оғози Deque илова кунед
  2. insertEnd (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 бо истифодаи Рӯйхати дуҷониба алоқаманд

insertFront (х)

Барои дохил кардани як унсур дар пеши 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++

insertEnd (х)

Барои ворид кардани унсур дар охири 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++

deleteFront ()

Барои нест кардани унсур аз пеши Deque, амалҳои зеринро иҷро кунед

  1. Агар пеши нул бошад, ягон элементе нест карда намешавад, танҳо баргардед.
  2. Агар фронт ба қафо баробар бошад, танҳо 1 гиреҳ мавҷуд аст, пеш ва қафоро нул кунед.
  3. Дар акси ҳол, пешро ба front.next баробар кунед ва front.prev -ро нест кунед
  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--

deleteEnd ()

Барои нест кардани унсур аз охири Deque, амалҳои зеринро иҷро кунед

  1. Агар қафо нул бошад, гиреҳе нест карда намешавад, танҳо баргардед.
  2. Агар қафо ба пеш баробар бошад, танҳо як гиреҳ вуҷуд дорад, пеш ва қафо нул кунед.
  3. Дигар қафоро ҳамчун back.prev созед ва rear.next -ро нест кунед.
  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 аз тарафи пеш ишора карда мешавад, аз ин рӯ, агар front front.data баргардад

Мураккабии вақт = О (1)

Кодекси псевдо

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

getEnd ()

Унсури охири Deque бо пушти сар ишора карда мешавад, аз ин рӯ, агар пушти сифр баргардонида намешавад

Мураккабии вақт = О (1)

Кодекси псевдо

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

isEmpty ()

Агар Deque холӣ бошад, ҳам пеш ва ҳам ақибнишин хоҳанд буд, аз ин рӯ агар фронт null return true бошад, вагарна false false бармегардад.

Мураккабии вақт = О (1)

Кодекси псевдо

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

андоза ()

Андозаи Deque дар тағирёбанда бо номи "андоза" ҳифз карда мешавад, аз ин рӯ андозаи онро баргардонед.

Мураккабии вақт = О (1)

Кодекси псевдо

return size

нест кардан ()

Тозакунии Deque маънои нест кардани тамоми гиреҳҳои Deque мебошад. Барои нест кардани ҳамаи гиреҳҳо инҳоро иҷро кунед,

  1. Қафоро ҳамчун сифр таъин кунед.
  2. Ҳарорате муваққатӣ бо ишора ба пеш эҷод кунед.
  3. Дар Deque ҳаракат кунед ва қадами 4-ро такрор кунед, яъне дар ҳолати пеш қадами такрории нул 4 нест.
  4. Темпро ҳамчун пеш, пешро ҳамчун front.next насб кунед ва барои temp ҷой ҷудо кунед.
  5. Дар ниҳоят temp ҳамчун null ва front ҳамчун 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

рамз

Рамзи Java барои татбиқи 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