การใช้งาน Deque โดยใช้อาร์เรย์แบบวงกลม


ระดับความยาก กลาง
ถามบ่อยใน อเมซอน GE Healthcare Google ไมโครซอฟท์
แถว รายการที่เชื่อมโยง คิว

คำชี้แจงปัญหา

“ การใช้งาน Deque โดยใช้อาร์เรย์แบบวงกลม” ขอให้ใช้ฟังก์ชันต่อไปนี้ของ Deque (Doubly Ended Queue) โดยใช้อาร์เรย์แบบวงกลม

  1. แทรกด้านหน้า (x) : แทรกองค์ประกอบ x ที่ด้านหน้าของ Deque
  2. แทรกด้านหลัง (x) : ใส่องค์ประกอบ x ที่ด้านหลังของ Deque
  3. ลบด้านหน้า () : ลบองค์ประกอบจากด้านหน้าของ Deque
  4. ลบRear () : ลบองค์ประกอบจากด้านหลังของ Deque
  5. getFront () : ส่งคืนองค์ประกอบที่อยู่ด้านหน้าของ Deque
  6. getRear () : ส่งคืนองค์ประกอบที่มีอยู่ที่ด้านหลังของ Deque
  7. มันว่างเปล่า() : กลับมาว่า Deque ว่างเปล่าหรือไม่
  8. เต็ม() : กลับมาว่า Deque เต็มหรือไม่

ตัวอย่าง

อินพุต
แทรกด้านหน้า (5)
แทรกด้านหลัง (10)
แทรกด้านหลัง (11)
แทรกด้านหน้า (19)
getFront ()
getRear ()
เต็ม()
ลบRear ()
getRear ()
ลบด้านหน้า ()
getFront ()
มันว่างเปล่า()

เอาท์พุต
19
11
เท็จ
10
5
เท็จ

อัลกอริทึมสำหรับการนำ Deque ไปใช้โดยใช้อาร์เรย์แบบวงกลม

เพื่อนำไปใช้ เดเก การใช้อาร์เรย์แบบวงกลมเราจำเป็นต้องติดตามตัวชี้สองตัวด้านหน้าและด้านหลังในอาร์เรย์ การดำเนินการทั้งหมดจะอยู่ในสองพอยน์เตอร์
ความหมายของอาร์เรย์แบบวงกลมสามารถเข้าใจได้จากรูปภาพด้านล่าง

การใช้งาน Deque โดยใช้อาร์เรย์แบบวงกลม

ในภาพนี้ด้านหลังอยู่ด้านหลังด้านหน้านั่นคือเมื่อด้านหลังอยู่ที่ส่วนท้ายของอาร์เรย์และมีช่องว่างบางส่วนในจุดเริ่มต้นของอาร์เรย์ดังนั้นการแทรกองค์ประกอบที่ด้านหลังจะทำให้ด้านหลังอยู่ที่ตำแหน่ง 0 นี่เป็นเพราะวงกลม แถว เป็นวงกลมในธรรมชาติ

สร้างอาร์เรย์ขนาด n โดยที่ n คือขนาดสูงสุดของ Deque และเริ่มต้นด้านหน้าและด้านหลังเป็น -1 ก่อนการดำเนินการใด ๆ บน Deque
เนื่องจากอาร์เรย์เป็นแบบวงกลมที่เพิ่มขึ้นด้านหน้าหรือด้านหลังเมื่ออยู่ที่ส่วนท้ายของอาร์เรย์จะนำไปที่จุดเริ่มต้นและการลดลงของด้านหน้าและด้านหลังในทำนองเดียวกันเมื่ออยู่ที่จุดเริ่มต้นจะนำไปที่จุดสิ้นสุดของ แถว.

แทรกด้านหน้า (x)

  1. หากอาร์เรย์เต็มจะไม่สามารถแทรกองค์ประกอบได้
  2. หากไม่มีองค์ประกอบใน Deque (หรืออาร์เรย์) นั่นคือ front เท่ากับ -1 เพิ่มส่วนหน้าและส่วนหลังและตั้งค่า arr [front] เป็น x
  3. อื่น ๆ ที่ลดลงด้านหน้าและตั้งค่า arr [front] เป็น x

ความซับซ้อนของเวลา = O (1)

แทรกด้านหลัง ()

  1. หากอาร์เรย์เต็มจะไม่สามารถแทรกองค์ประกอบได้
  2. หากไม่มีองค์ประกอบใน Deque นั่นคือด้านหลังเท่ากับ -1 เพิ่มส่วนหน้าและส่วนหลังและตั้งค่า arr [ด้านหลัง] เป็น x
  3. ด้านหลังส่วนเพิ่มอื่น ๆ และตั้งค่า arr [ด้านหลัง] เป็น x

ความซับซ้อนของเวลา = O (1)

ลบด้านหน้า ()

  1. หาก Deque ว่างเปล่าให้ส่งคืน
  2. หากมีเพียงองค์ประกอบเดียวใน Deque นั่นคือด้านหน้าเท่ากับด้านหลังให้ตั้งค่าด้านหน้าและด้านหลังเป็น -1
  3. อื่น ๆ เพิ่มขึ้นด้านหน้าทีละ 1

ความซับซ้อนของเวลา = O (1)

ลบRear ()

  1. หาก Deque ว่างเปล่าให้ส่งคืน
  2. หากมีเพียงองค์ประกอบเดียวใน Deque นั่นคือด้านหลังเท่ากับด้านหน้าให้ตั้งค่าด้านหน้าและด้านหลังเป็น -1
  3. ด้านหลังลดลงอีก 1

ความซับซ้อนของเวลา = O (1)

getFront ()

  1. หาก Deque ว่างเปล่าให้ส่งคืน
  2. อื่นกลับ arr [ด้านหน้า]

ความซับซ้อนของเวลา = O (1)

getRear ()

  1. หาก Deque ว่างเปล่าให้ส่งคืน
  2. อื่นกลับ arr [ด้านหลัง]

ความซับซ้อนของเวลา = O (1)

มันว่างเปล่า()

ถ้า front เท่ากับ -1 Deque ว่างเปล่ามิฉะนั้นจะไม่ใช่

ความซับซ้อนของเวลา = O (1)

เต็ม()

ถ้า (ด้านหลัง + 1)% n เท่ากับด้านหน้าแสดงว่า Deque เต็มแล้วมิฉะนั้นจะไม่เป็นเช่นนั้น นี่คือขนาดสูงสุดของ Deque

ความซับซ้อนของเวลา = O (1)

Java Code สำหรับการใช้งาน 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