سرکلر صف کا استعمال کرتے ہوئے Deque کا نفاذ


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون GE صحت کا خیال گوگل مائیکروسافٹ
لڑی لنکڈ لسٹ قطار

مسئلہ یہ بیان

"سرکلر صف کا استعمال کرتے ہوئے ڈیوکی کا نفاذ" سرکلر صف کا استعمال کرتے ہوئے ڈیک (ڈبل ختم شدہ قطار) کے درج ذیل کاموں کو نافذ کرنے کے لئے کہتا ہے ،

  1. insertFront (x) : ڈیک کے سامنے والے عنصر کو داخل کریں
  2. insertRear (x) : ڈیک کے عقب میں ایک عنصر داخل کریں
  3. ڈیلیٹ فرنٹ () : Deque کے سامنے سے ایک عنصر کو حذف کریں
  4. حذف کریں () : Deque کے عقبی حصے سے عنصر کو حذف کریں
  5. گیٹ فرنٹ () : Deque کے سامنے موجود عنصر کو واپس کریں
  6. getRear () : ڈیک کے عقب میں موجود عنصر کو واپس کریں
  7. خالی ہے() : واپس کریں یا نہیں Deque خالی ہے
  8. بھرا ہے() : واپس کریں یا نہیں Deque بھرا ہوا ہے

مثال کے طور پر

ان پٹ
insertFront (5)
insertRear (10)
insertRear (11)
insertFront (19)
گیٹ فرنٹ ()
getRear ()
بھرا ہے()
حذف کریں ()
getRear ()
ڈیلیٹ فرنٹ ()
گیٹ فرنٹ ()
خالی ہے()

آؤٹ پٹ
19
11
جھوٹی
10
5
جھوٹی

سرکلر صف کا استعمال کرتے ہوئے ڈیک کے نفاذ کے لئے الگورتھم

لاگو کرنے کے لئے Deque ایک سرکلر سرنی کا استعمال کرتے ہوئے ہمیں سرنی میں دو پوائنٹر سامنے اور پیچھے کا ٹریک رکھنے کی ضرورت ہے۔ تمام کاروائیاں ان دو پوائنٹرز پر ہوں گی۔
سرکلر صف کے معنی ذیل کی شبیہہ سے سمجھے جا سکتے ہیں

سرکلر صف کا استعمال کرتے ہوئے Deque کا نفاذ

اس شبیہہ میں عقبی حص frontہ کے پیچھے ہے ، یعنی جب پیچھے سرنی کے آخر میں تھا اور سرنی کے آغاز میں کچھ خالی سلاٹ تھے ، لہذا عقبی حصے میں عنصر ڈالنے سے عقب 0 پر آنے کا سبب بنے گا۔ ، اس کی وجہ یہ ہے کہ سرکلر صف فطرت میں سرکلر ہے۔

سائز این کی ایک صف تیار کریں ، جہاں ن Deque کا زیادہ سے زیادہ سائز ہو اور ڈیوک پر کسی بھی کارروائی سے قبل ، سامنے اور پیچھے کو -1 کے طور پر شروع کریں۔
چونکہ سرنی سرکلر انکریمنٹ فرنٹ یا ریئر ہوتی ہے جب وہ سرنی کے آخر میں موجود ہوتے ہیں تو وہ انہیں نقطہ آغاز تک لے جاتے ہیں اور اسی طرح سامنے اور پیچھے کم ہوتے وقت جب وہ نقطہ آغاز پر ہوتے ہیں تو انہیں آخری سرے پر لے جاتا ہے۔ صف.

insertFront (x)

  1. اگر سرنی بھری ہو تو ، عنصر داخل نہیں کیا جاسکتا۔
  2. اگر ڈیک (یا صف) میں کوئی عنصر موجود نہیں ہیں ، یعنی ، سامنے کے برابر -1 ، انکریمنٹ فرنٹ اور ریئر ، اور آر آر [فرنٹ] کو x کے بطور سیٹ کریں۔
  3. بصورت دیگر بطور محاذ اور آرر [فرنٹ] کو بطور ایکس۔

وقت کی پیچیدگی = O (1)

insertRear ()

  1. اگر سرنی بھری ہو تو ، عنصر داخل نہیں کیا جاسکتا۔
  2. اگر ڈیک میں کوئی عناصر موجود نہیں ہیں ، یعنی ، پیچھے کے برابر -1 ، انکریمنٹ فرنٹ اور رئیر اور سیٹ آر آر [ریئر] کو بطور ایکس۔
  3. بصورت دیگر انکرمنٹ ریئر اور سیٹ آر آر [ریئر] کو بطور ایکس

وقت کی پیچیدگی = O (1)

ڈیلیٹ فرنٹ ()

  1. اگر Deque خالی ہے ، واپس آ جائیں۔
  2. اگر ڈیک میں صرف ایک عنصر موجود ہے ، یعنی ، سامنے کے برابر ہے ، سامنے اور عقب کو -1 کے برابر ہے۔
  3. دوسری طرف انکریمنٹ 1۔

وقت کی پیچیدگی = O (1)

حذف کریں ()

  1. اگر Deque خالی ہے ، واپس آ جائیں۔
  2. اگر ڈیک میں صرف ایک عنصر موجود ہے ، یعنی ، پیچھے کے برابر ہوتا ہے ، سامنے اور پیچھے کو -1 کے برابر کرتا ہے۔
  3. دوسری کمی کے پیچھے 1۔

وقت کی پیچیدگی = O (1)

گیٹ فرنٹ ()

  1. اگر Deque خالی ہے ، واپس آ جائیں۔
  2. دوسری واپسی کا ارر [سامنے]۔

وقت کی پیچیدگی = O (1)

getRear ()

  1. اگر Deque خالی ہے ، واپس آ جائیں۔
  2. دوسری واپسی کا ارر [پیچھے]۔

وقت کی پیچیدگی = O (1)

خالی ہے()

اگر سامنے برابر -1 کے برابر ہے Deque خالی ہے ، ورنہ ایسا نہیں ہے۔

وقت کی پیچیدگی = O (1)

بھرا ہے()

اگر (پیچھے + 1)٪ n سامنے کے برابر ہے تو Deque بھرا ہوا ہے ، ورنہ ایسا نہیں ہے۔ یہاں ن Deuk کا زیادہ سے زیادہ سائز ہے۔

وقت کی پیچیدگی = 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

سرکلر سرنی کا استعمال کرتے ہوئے ڈیک کے نفاذ کے لئے C ++ کوڈ

#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