വൃത്താകൃതിയിലുള്ള അറേ ഉപയോഗിച്ച് ഡെക്ക് നടപ്പിലാക്കൽ


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ GE ഹെൽത്ത്കെയർ ഗൂഗിൾ മൈക്രോസോഫ്റ്റ്
അറേ ലിങ്ക്ഡ്-ലിസ്റ്റ് വരി

പ്രശ്നം പ്രസ്താവന

“വൃത്താകൃതിയിലുള്ള അറേ ഉപയോഗിച്ച് ഡെക്ക് നടപ്പിലാക്കൽ” വൃത്താകൃതിയിലുള്ള അറേ ഉപയോഗിച്ച് ഒരു ഡീക്യൂവിന്റെ (ഇരട്ട എന്റഡ് ക്യൂ) ഇനിപ്പറയുന്ന പ്രവർത്തനങ്ങൾ നടപ്പിലാക്കാൻ ആവശ്യപ്പെടുന്നു,

  1. insertFront (x) : ഡെക്യൂവിന്റെ മുൻവശത്ത് x എന്ന ഘടകം ചേർക്കുക
  2. insertRear (x) : ഡെക്യൂവിന്റെ പിൻഭാഗത്ത് x എന്ന ഘടകം ചേർക്കുക
  3. deleteFront () : Deque ന് മുന്നിൽ നിന്ന് ഒരു ഘടകം ഇല്ലാതാക്കുക
  4. deleteRear () : ഡെക്യൂവിന്റെ പിന്നിൽ നിന്ന് ഒരു ഘടകം ഇല്ലാതാക്കുക
  5. getFront () : ഡെക്യൂവിന്റെ മുൻവശത്തുള്ള ഘടകം തിരികെ നൽകുക
  6. getRear () : ഡെക്യൂവിന്റെ പിന്നിലുള്ള ഘടകം തിരികെ നൽകുക
  7. ശൂന്യമാണ്() : ഡെക്ക് ശൂന്യമാണോ അല്ലയോ എന്ന് മടങ്ങുക
  8. നിറഞ്ഞു() : ഡെക്ക് നിറഞ്ഞിട്ടുണ്ടോ ഇല്ലയോ എന്ന് മടങ്ങുക

ഉദാഹരണം

ഇൻപുട്ട്
insertFront (5)
insertRear (10)
insertRear (11)
insertFront (19)
getFront ()
getRear ()
നിറഞ്ഞു()
deleteRear ()
getRear ()
deleteFront ()
getFront ()
ശൂന്യമാണ്()

ഔട്ട്പുട്ട്
19
11
തെറ്റായ
10
5
തെറ്റായ

വൃത്താകൃതിയിലുള്ള അറേ ഉപയോഗിച്ച് ഡെക്ക് നടപ്പിലാക്കുന്നതിനുള്ള അൽഗോരിതം

നടപ്പാക്കാൻ Deque ഒരു വൃത്താകൃതിയിലുള്ള അറേ ഉപയോഗിച്ച് അറേയിലെ മുന്നിലും പിന്നിലും രണ്ട് പോയിന്റർ ഞങ്ങൾ സൂക്ഷിക്കേണ്ടതുണ്ട്. എല്ലാ പ്രവർത്തനങ്ങളും ഈ രണ്ട് പോയിന്ററുകളിലായിരിക്കും.
വൃത്താകൃതിയിലുള്ള അറേയുടെ അർത്ഥം ചുവടെയുള്ള ചിത്രത്തിന് മനസിലാക്കാൻ കഴിയും

വൃത്താകൃതിയിലുള്ള അറേ ഉപയോഗിച്ച് ഡെക്ക് നടപ്പിലാക്കൽ

ഈ ഇമേജിൽ‌ പിൻ‌വശം മുൻ‌ഭാഗത്തിന് പിന്നിലുണ്ട്, അതായത് പിൻ‌ അറേയുടെ അവസാനത്തിലായിരിക്കുമ്പോഴും അറേയുടെ തുടക്കത്തിൽ‌ ചില ശൂന്യമായ സ്ലോട്ടുകൾ‌ ഉണ്ടായിരുന്നതിനാലും, പിൻ‌ഭാഗത്ത് ഒരു മൂലകം ഉൾപ്പെടുത്തുന്നത് പിൻ‌ സ്ഥാനം 0 , കാരണം സർക്കുലർ ശ്രേണി വൃത്താകൃതിയിലുള്ളതാണ്.

വലിപ്പം n ന്റെ ഒരു ശ്രേണി സൃഷ്ടിക്കുക, ഇവിടെ n എന്നത് ഡെക്യൂവിന്റെ പരമാവധി വലുപ്പമാണ്, കൂടാതെ ഡെക്യൂവിലെ ഏതെങ്കിലും പ്രവർത്തനത്തിന് മുമ്പായി മുന്നിലും പിന്നിലും -1 ആയി സമാരംഭിക്കുക.
അറേ വൃത്താകൃതിയിലുള്ള ഇൻക്രിമെന്റ് ഫ്രണ്ട് അല്ലെങ്കിൽ റിയർ ആയതിനാൽ അറേയുടെ അവസാനം അവ ആരംഭ സ്ഥാനത്തേക്ക് കൊണ്ടുപോകും, ​​അതുപോലെ തന്നെ ആരംഭ പോയിന്റിലായിരിക്കുമ്പോൾ മുന്നിലും പിന്നിലും കുറയുന്നത് അവരെ അവസാന സ്ഥാനത്തേക്ക് കൊണ്ടുപോകും ശ്രേണി.

insertFront (x)

  1. അറേ നിറഞ്ഞിട്ടുണ്ടെങ്കിൽ, ഘടകം ചേർക്കാൻ കഴിയില്ല.
  2. Deque (അല്ലെങ്കിൽ അറേ) യിൽ ഘടകങ്ങളൊന്നുമില്ലെങ്കിൽ, അതായത്, ഫ്രണ്ട് -1 ന് തുല്യമാണ്, മുന്നിലും പിന്നിലും ഇൻക്രിമെന്റ്, അര [ഫ്രണ്ട്] x ആയി സജ്ജമാക്കുക.
  3. മറ്റൊരു കുറവ് ഫ്രണ്ട്, അര [ഫ്രണ്ട്] x ആയി സജ്ജമാക്കുക.

സമയ സങ്കീർണ്ണത = O (1)

insertRear ()

  1. അറേ നിറഞ്ഞിട്ടുണ്ടെങ്കിൽ, ഘടകം ചേർക്കാൻ കഴിയില്ല.
  2. ഡെക്യൂവിൽ ഘടകങ്ങളൊന്നുമില്ലെങ്കിൽ, അതായത്, പിൻ -1 ന് തുല്യമാണ്, മുന്നിലും പിന്നിലും ഇൻക്രിമെന്റ് ചെയ്യുക, അര [പിൻ] x ആയി സജ്ജമാക്കുക.
  3. അല്ലെങ്കിൽ ഇൻക്രിമെന്റ് റിയർ, അര [റിയർ] x ആയി സജ്ജമാക്കുക.

സമയ സങ്കീർണ്ണത = O (1)

deleteFront ()

  1. Deque ശൂന്യമാണെങ്കിൽ, മടങ്ങുക.
  2. ഡെക്യൂവിൽ ഒരു ഘടകം മാത്രമേ ഉള്ളൂവെങ്കിൽ, അതായത്, ഫ്രണ്ട് റിയറിന് തുല്യമാണ്, ഫ്രണ്ട്, റിയർ -1 എന്നിങ്ങനെ സജ്ജമാക്കുക.
  3. മറ്റൊരു ഇൻക്രിമെന്റ് ഫ്രണ്ട് 1.

സമയ സങ്കീർണ്ണത = O (1)

deleteRear ()

  1. Deque ശൂന്യമാണെങ്കിൽ, മടങ്ങുക.
  2. ഡെക്യൂവിൽ ഒരു ഘടകം മാത്രമേ ഉള്ളൂവെങ്കിൽ, അതായത്, പിൻഭാഗം ഫ്രണ്ടിന് തുല്യമാണ്, മുന്നിലും പിന്നിലും -1 ആയി സജ്ജമാക്കുക.
  3. മറ്റൊന്ന് 1 ന്റെ കുറവ്.

സമയ സങ്കീർണ്ണത = O (1)

getFront ()

  1. Deque ശൂന്യമാണെങ്കിൽ, മടങ്ങുക.
  2. അല്ലെങ്കിൽ മടക്കയാത്ര [മുന്നിൽ].

സമയ സങ്കീർണ്ണത = O (1)

getRear ()

  1. Deque ശൂന്യമാണെങ്കിൽ, മടങ്ങുക.
  2. അല്ലെങ്കിൽ മടക്കയാത്ര [പിൻ].

സമയ സങ്കീർണ്ണത = O (1)

ശൂന്യമാണ്()

ഫ്രണ്ട് -1 ന് തുല്യമാണെങ്കിൽ ഡെക്ക് ശൂന്യമാണ്, അല്ലാത്തപക്ഷം.

സമയ സങ്കീർണ്ണത = O (1)

നിറഞ്ഞു()

(പിൻ + 1)% n മുൻവശത്തിന് തുല്യമാണെങ്കിൽ ഡെക്ക് നിറഞ്ഞിരിക്കുന്നു, അല്ലാത്തപക്ഷം. ഇവിടെ n എന്നത് ഡെക്യൂവിന്റെ പരമാവധി വലുപ്പമാണ്.

സമയ സങ്കീർണ്ണത = O (1)

വൃത്താകൃതിയിലുള്ള അറേ ഉപയോഗിച്ച് ഡെക്ക് നടപ്പിലാക്കുന്നതിനുള്ള ജാവ കോഡ്

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

വൃത്താകൃതിയിലുള്ള അറേ ഉപയോഗിച്ച് ഡെക്ക് നടപ്പിലാക്കുന്നതിനുള്ള സി ++ കോഡ്

#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