Татбиқи Deque бо истифодаи массиви даврӣ  


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon GE Тандурустӣ Google Microsoft
тартиботи ҳарбӣ Рӯйхати алоқаманд навбат

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

"Татбиқи Deque бо истифодаи массиви даврӣ" дархост мекунад, ки вазифаҳои зерини Deque (Навбати дуҷониба) бо истифодаи массиви даврӣ иҷро карда шаванд,

  1. insertFront (х) : гузоред унсури х дар пеши Deque
  2. insertRear (x) : гузоред унсури х дар паси Deque
  3. deleteFront () : элементро аз пеши Deque нест кунед
  4. deleteRear () : унсурро аз қафои Deque нест кунед
  5. getFront () : баргардонидани унсури дар назди Deque мавҷудбуда
  6. getRear () : баргардонидани унсури дар пушти Deque мавҷудбуда
  7. isEmpty () : баргардонед, агар Deque холӣ бошад ё не
  8. isFull () : баргардед ё не, пур аз Deque

мисол  

вуруди
insertFront (5)
дохилкунӣ (10)
дохилкунӣ (11)
insertFront (19)
getFront ()
getRear ()
isFull ()
deleteRear ()
getRear ()
deleteFront ()
getFront ()
isEmpty ()

Натиҷаи
19
11
бардурӯғ
10
5
бардурӯғ

Алгоритми татбиқи Deque бо истифодаи массиви даврӣ  

Барои татбиқ Дек бо истифода аз массиви даврӣ, мо бояд пайгирии ду нишоннамои пеш ва қафоро дар массив нигоҳ дорем. Ҳама амалиётҳо дар ин ду нишондиҳанда хоҳанд буд.
Маънои массиви давриро бо тасвири зер фаҳмида метавонед

Татбиқи Deque бо истифодаи массиви даврӣ

Дар ин тасвир пушти сар пушти сар аст, яъне вақте пушти сар дар охири массив буд ва дар оғози массив якчанд ҷойҳои холӣ мавҷуд буданд, бинобар ин гузоштани элемент дар қафо боиси ақиб дар ҳолати 0 қарор мегирад , ин аз он сабаб аст, ки даврашакл аст асал характери даврагӣ дорад.

ҳамчунин нигаред
Top K унсурҳои зуд-зуд

Массиви андозаи n -ро эҷод кунед, ки n андозаи максималии Deque аст ва пеш ва ҳаракат дар Deque пеш ва пасро ҳамчун -1 оғоз кунед.
Азбаски массив афзоиши даврӣ мебошад, вақте ки онҳо дар охири массив ҳузур доранд, онҳоро ба нуқтаи ибтидоӣ мебарад ва ҳамин тавр пеш ва пуштаро кам мекунад, вақте ки онҳо дар нуқтаи ибтидоӣ ҳастанд, онҳоро то охири хат асал.

insertFront (х)

  1. Агар массив пурра бошад, элементро ҷойгир кардан ғайриимкон аст.
  2. Агар дар Deque (ё массив) ягон унсур набошад, яъне пеш баробар аст -1, афзоишро пеш ва қафо ва arr [front] -ро x таъин кунед.
  3. Пеши дигари камшаванда ва arr [front] -ро ҳамчун x таъин кунед.

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

insertRear ()

  1. Агар массив пурра бошад, элементро ҷойгир кардан ғайриимкон аст.
  2. Агар дар Deque ягон унсуре мавҷуд набошад, яъне қафо ба -1 баробар аст, пеш ва қафоро афзоиш диҳед ва arr [паси] -ро x насб кунед.
  3. Арзиши дигари қафо ва arr [пушти] -ро x насб кунед.

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

deleteFront ()

  1. Агар Deque холӣ бошад, баргардед.
  2. Агар дар Deque танҳо як унсур мавҷуд бошад, яъне пеш ба ақиб баробар аст, пеш ва қафоро ҳамчун -1 муқаррар кунед.
  3. Пешрафти дигар аз ҷониби 1.

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

deleteRear ()

  1. Агар Deque холӣ бошад, баргардед.
  2. Агар дар Deque танҳо як унсур мавҷуд бошад, яъне қафо ба пеш баробар аст, пеш ва қафоро ҳамчун -1 гузошт.
  3. Дигар камшавии дигар аз ҷониби 1.

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

getFront ()

  1. Агар Deque холӣ бошад, баргардед.
  2. Бозгашти arr [front].

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

getRear ()

  1. Агар Deque холӣ бошад, баргардед.
  2. Дигар arr [return].
ҳамчунин нигаред
Ҳисоби ҷуфтҳои индекс бо унсурҳои баробар дар массив

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

isEmpty ()

Агар фронт ба -1 баробар бошад, Дек холӣ аст, вагарна он нест.

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

isFull ()

Агар (паси + 1)% n ба пеш баробар бошад, пас Deque пур аст, вагарна он чунин нест. Дар ин ҷо n андозаи ниҳоии Deque аст.

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

Кодекси Java барои татбиқи Deque бо истифодаи массиви даврӣ  

class ImplementationOfDequeUsingCircularArray {
    // Maximum size of Deque
    private static final int MAX_SIZE = 100;
    // Array to implement Deque
    private static int deque[];
    // Variables to represent front and rear of dequeue
    private static int front = -1;
    private static int rear = -1;

    private static void insertFront(int x) {
        // if array is not full
        if (!isFull()) {
            // case 1 : there are no elements
            // increment front and rear and add element at arr[front]
            if (front == -1) {
                front = rear = 0;
                deque[front] = x;
            }
            // else, decrement front circularly and add the
            // new element at arr[front]
            else {
                if (front == 0) {
                    front = MAX_SIZE - 1;
                } else {
                    front--;
                }
                deque[front] = x;
            }
        }
    }

    private static void insertRear(int x) {
        // if array is not full
        if (!isFull()) {
            // if this is the first element to be inserted
            // increment front and rear and add element at arr[rear]
            if (rear == -1) {
                front = rear = 0;
                deque[rear] = x;
            }
            // else increment rear circularly and add
            // new element at arr[rear]
            else {
                if (rear == MAX_SIZE - 1) {
                    rear = 0;
                } else {
                    rear++;
                }
                deque[rear] = x;
            }
        }
    }

    private static void deleteFront() {
        // if array is not empty
        if (!isEmpty()) {
            // if there is only 1 element
            // make front and rear as -1
            if (front == rear) {
                front = rear = -1;
            }
            // else increment front circularly
            else {
                if (front == MAX_SIZE - 1) {
                    front = 0;
                } else {
                    front++;
                }
            }
        }
    }

    private static void deleteRear() {
        // if array is not empty
        if (!isEmpty()) {
            // if there is only 1 element
            // make front and rear as -1
            if (front == rear) {
                rear = front = -1;
            }
            // else decrement rear circularly
            else {
                if (rear == 0) {
                    rear = MAX_SIZE - 1;
                } else {
                    rear--;
                }
            }
        }
    }

    private static int getFront() {
        // if array is not empty return arr[front]
        if (!isEmpty()) {
            return deque[front];
        }
        return -1;
    }

    private static int getRear() {
        // if array is not empty return arr[rear]
        if (!isEmpty()) {
            return deque[rear];
        }
        return -1;
    }

    private static boolean isEmpty() {
        // if front is -1 then deque is empty
        if (front == -1) {
            return true;
        }
        return false;
    }

    private static boolean isFull() {
        // if front is 1 ahead of rear then
        // deque is full
        if ((rear + 1) % MAX_SIZE == front) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
         deque = new int[MAX_SIZE];

         // Example
        insertFront(5);
        insertRear(10);
        insertRear(11);
        insertFront(19);
        System.out.println(getFront());
        System.out.println(getRear());
        System.out.println(isFull());
        deleteRear();
        System.out.println(getRear());
        deleteFront();
        System.out.println(getFront());
        System.out.println(isEmpty());
    }
}
19
11
false
10
5
false

C ++ Кодекс барои татбиқи Deque бо истифодаи массиви даврӣ  

#include <iostream>
using namespace std;

// Maximum size of Deque
const int MAX_SIZE = 100;
// Array to implement Deque
int deque[MAX_SIZE];
// Variables to represent front and rear of dequeue
int front = -1;
int rear = -1;

bool isEmpty() {
    // if front is -1 then deque is empty
    if (front == -1) {
        return true;
    }
    return false;
}

bool isFull() {
    // if front is 1 ahead of rear then
    // deque is full
    if ((rear + 1) % MAX_SIZE == front) {
        return true;
    }
    return false;
}

void insertFront(int x) {
    // if array is not full
    if (!isFull()) {
        // case 1 : there are no elements
        // increment front and rear and add element at arr[front]
        if (front == -1) {
            front = rear = 0;
            deque[front] = x;
        } 
        // else, decrement front circularly and add the
        // new element at arr[front]
        else {
            if (front == 0) {
                front = MAX_SIZE - 1;
            } else {
                front--;
            }
            
            deque[front] = x;
        }
    }
}

void insertRear(int x) {
    // if array is not full
    if (!isFull()) {
        // if this is the first element to be inserted
        // increment front and rear and add element at arr[rear]
        if (rear == -1) {
            front = rear = 0;
            deque[rear] = x;
        } 
        // else increment rear circularly and add
        // new element at arr[rear]
        else {
            if (rear == MAX_SIZE - 1) {
                rear = 0;
            } else {
                rear++;
            }
            
            deque[rear] = x;
        }
    }
}

void deleteFront() {
    // if array is not empty
    if (!isEmpty()) {
        // if there is only 1 element
        // make front and rear as -1
        if (front == rear) {
            front = rear = -1;
        } 
        // else increment front circularly
        else {
            if (front == MAX_SIZE - 1) {
                front = 0;
            } else {
                front++;
            }
        }
    }
}

void deleteRear() {
    // if array is not empty
    if (!isEmpty()) {
        // if there is only 1 element
        // make front and rear as -1
        if (front == rear) {
            front = rear = -1;
        } 
        // else decrement rear circularly
        else {
            if (rear == 0) {
                rear = MAX_SIZE - 1;
            } else {
                rear--;
            }
        }
    }
}

int getFront() {
    // if array is not empty return arr[front]
    if (!isEmpty()) {
        return deque[front];
    }
    return -1;
}

int getRear() {
    // if array is not empty return arr[rear]
    if (!isEmpty()) {
        return deque[rear];
    }
    return -1;
}

int main() {
    // Example
    insertFront(5);
    insertRear(10);
    insertRear(11);
    insertFront(19);
    cout<<getFront()<<endl;
    cout<<getRear()<<endl;
    if (isFull()) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    deleteRear();
    cout<<getRear()<<endl;
    deleteFront();
    cout<<getFront()<<endl;
    if (isEmpty()) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    
    return 0;
}
19
11
false
10
5
false