गोलाकार एर्रे प्रयोग गरी Deque को कार्यान्वयन


कठिनाई तह मध्यम
बारम्बार सोधिन्छ अमेजन जीई हेल्थकेयर गुगल माइक्रोसफ्ट
एरे लिंक्ड-सूची लाम

समस्या वक्तव्य

"गोलाकार एर्रेको प्रयोगले Deque को कार्यान्वयन" ले ड्यूकको निम्नलिखित कार्यहरू कार्यान्वयन गर्न सोध्छ (डब्ल्यु एन्डेड लाम) परिपत्र एरे प्रयोग गरेर,

  1. insertFront (x) : Deque को अगाडि एक एलिमेन्ट x घुसाउनुहोस्
  2. insertRear (x) : Deque को पछाडि एलिमेन्ट x घुसाउनुहोस्
  3. डिलीटफ्रन्ट () : Deque को अगाडिबाट एक तत्व मेट्नुहोस्
  4. मेट्नुहोस् रियर () : Deque को पछाडिको एक तत्व मेट्नुहोस्
  5. getFront () : Deque को अगाडि उपस्थित तत्व फिर्ता
  6. getRear () : Deque को पछाडि उपस्थित तत्व फिर्ता
  7. खाली छ() : फर्कनुहोस् कि Deque खाली छ वा छैन
  8. isFull () : Deque भरिएको छ वा छैन फिर्ता

उदाहरणका

आगत
insertFront ())
InsertRear (१०)
InsertRear (१०)
insertFront ())
getFront ()
getRear ()
isFull ()
मेट्नुहोस् रियर ()
getRear ()
डिलीटफ्रन्ट ()
getFront ()
खाली छ()

उत्पादन
19
11
झूटा
10
5
झूटा

गोलाकार एर्रे प्रयोग गरेर Deque को कार्यान्वयनको लागि एल्गोरिथ्म

कार्यान्वयन गर्न केको बारेमा गोलाकार एरे प्रयोग गरेर हामीलाई एर्रेमा दुई पोइन्टर अगाडि र पछाडि ट्र्याक राख्नु पर्छ। सबै अपरेशनहरू यी दुई सूचकहरूमा हुनेछन्।
गोलाकार एर्रेको अर्थ तलको छवि द्वारा बुझ्न सकिन्छ

गोलाकार एर्रे प्रयोग गरी Deque को कार्यान्वयन

यस छविमा रियर अगाडि पछाडि छ, त्यो हो जब पछाडिको एर्रेको अन्त्यमा थियो र एर्रेको सुरूवातमा केही खाली स्लटहरू थिए त्यसैले पछि एलिमेन्ट्स घुसाउँदा पछाडि पछाडि पछाडि 0 हुने गर्छ। , यो किनभने परिपत्र array प्रकृतिमा गोलाकार हो।

आकार एनको एर्रे सिर्जना गर्नुहोस्, जहाँ एन Deque को अधिकतम साइज हो र अगाडि र पछाडि -१ को रूप मा इनिसियलाइज गर्नुहोस्, Deque मा कुनै अपरेशन अघि।
जसरी एरे गोलाकार वृद्धि फ्रन्ट वा पछाडि हुन्छ जब तिनीहरू एर्रेको अन्त्यमा उपस्थित हुन्छन् तिनीहरूलाई सुरूवात बिन्दुमा लैजान्छ र समान रूपमा अघि र पछाडि घट्ने क्रममा जब तिनीहरू सुरूको बिन्दुमा हुन्छन् तिनीहरूलाई अन्तको अन्तमा लैजान्छ array.

insertFront (x)

  1. यदि एर्रे भरिएको छ भने, तत्व घुसाउन सकिदैन।
  2. यदि त्यहाँ डेक (वा एर्रे) मा कुनै तत्वहरू छैनन्, त्यो हो, अगाडि बराबर -१, वृद्धि फ्रन्ट र रियर, र एर [फ्रन्ट] x को रूपमा सेट गर्दछ।
  3. अर्को कमी फ्रन्ट र सेट एर [फ्रन्ट] एक्स को रूपमा।

समय जटिलता = O (१)

InsertRear ()

  1. यदि एर्रे भरिएको छ भने, तत्व घुसाउन सकिदैन।
  2. यदि त्यहाँ Deque मा कुनै तत्व छैन, कि, पछाडि बराबर -१, वृद्धि फ्रन्ट र रियर र सेट एर [रियर] x को रूपमा।
  3. अर्को वृद्धि इन्ट्रिमेन्ट पछाडि र एर [रियर] x को रूपमा सेट गर्नुहोस्।

समय जटिलता = O (१)

डिलीटफ्रन्ट ()

  1. यदि Deque खाली छ, फर्कनुहोस्।
  2. यदि त्यहाँ डेक मा केवल एक तत्व छ, त्यो हो, सामने रिल बराबर, सेट अगाडी र पछाडि -1 को रूप मा।
  3. १ द्वारा दोस्रो वृद्धि।

समय जटिलता = O (१)

मेट्नुहोस् रियर ()

  1. यदि Deque खाली छ, फर्कनुहोस्।
  2. यदि त्यहाँ एक मात्र तत्व Deque मा छ, त्यो, पछाडि बराबर अगाडि सेट, अगाडि र पछाडि -1 को रूप मा सेट।
  3. १ र पछि घट्दो पछाडि।

समय जटिलता = O (१)

getFront ()

  1. यदि Deque खाली छ, फर्कनुहोस्।
  2. अर्को फिर्ती एर [फ्रन्ट]।

समय जटिलता = O (१)

getRear ()

  1. यदि Deque खाली छ, फर्कनुहोस्।
  2. अन्य फिर्ती एर [रियर]।

समय जटिलता = O (१)

खाली छ()

यदि फ्रन्ट बराबर हो भने -१ डेक खाली छ, अन्यथा छैन।

समय जटिलता = O (१)

isFull ()

यदि (पछाडि + १)% n अगाडिको बराबर छ भने डेक पूर्ण छ, अन्यथा यो छैन। यहाँ एन Deque को अधिकतम आकार छ।

समय जटिलता = O (१)

गोलाकार एर्रे प्रयोग गरेर 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