ข้ามไปเนื้อหา

ไลบรารีแม่แบบมาตรฐานของภาษาซีพลัสพลัส/deque

จาก วิกิตำรา

deque เป็น data structure ที่มีความสามารถคล้าย queue แต่สามารถดำเนินการกับข้อมูลทั้งนำข้อมูลเข้าและเอาข้อมูลออก ทั้งด้านหน้าและด้านปลายได้ทั้งคู่ (ถ้า queue จะดำเนินการนำข้อมูลเข้าได้ที่ปลาย และนำข้อมูลออกที่ด้านหน้าได้เท่านั้น)

ADT ของ deque ต้องการเพียงการจัดการกับข้อมูลส่วนด้านหน้าและปลายเท่านั้น ซึ่งอาจใช้ list ในการเขียนก็ได้ แต่ deque ของ STL ได้เพิ่มความสามารถ random access ทำให้สามารถเข้าถึงข้อมูลตัวใดๆได้ด้วย operator [] (เหมือน vector)

การใช้งานและการประกาศตัวแปร

[แก้ไข | แก้ไขต้นฉบับ]

ต้องนำเข้า header file "deque" โดย #include <deque>

ให้ T คือชนิดข้อมูลใดๆ และ var คือชื่อตัวแปร มีรูปแบบการประกาศตัวแปร deque โดย deque <T> var;

คำอธิบาย เป็นการเพิ่มข้อมูลชนิด T ลงทางด้านปลายของ deque ใช้เวลา
พารามิเตอร์ มีเพียงตัวเดียวคือข้อมูลชนิด T ที่ต้องการจะใส่ลง deque ทางด้านปลาย
คืนค่า ไม่มี
ฟังก์ชั่นต้นแบบ void push_back(T);
ข้อควรระวัง ไม่มี
คำอธิบาย เป็นการเพิ่มข้อมูลชนิด T ลงทางด้านหน้าของ deque ใช้เวลา O
พารามิเตอร์ มีเพียงตัวเดียวคือข้อมูลชนิด T ที่ต้องการจะใส่ลง deque ทางด้านหน้า
คืนค่า ไม่มี
ฟังก์ชั่นต้นแบบ void push_front(T);
ข้อควรระวัง ไม่มี
คำอธิบาย เป็นการลบข้อมูลชนิด T ทางด้านปลายของ deque ใช้เวลา
พารามิเตอร์ ไม่มี
คืนค่า ไม่มี
ฟังก์ชั่นต้นแบบ void pop_back();
ข้อควรระวัง หาก size ของ deque เป็น 0 จะเกิด error
คำอธิบาย เป็นการลบข้อมูลชนิด T ทางด้านหน้าของ deque ใช้เวลา
พารามิเตอร์ ไม่มี
คืนค่า ไม่มี
ฟังก์ชั่นต้นแบบ void pop_front();
ข้อควรระวัง หาก size ของ deque เป็น 0 จะเกิด error
คำอธิบาย เป็นการหาค่าที่อยู่ด้านหน้าของ deque ใช้เวลา
พารามิเตอร์ ไม่มี
คืนค่า ข้อมูลชนิด T ที่อยู่ด้านหน้าของ deque
ฟังก์ชั่นต้นแบบ T front();
ข้อควรระวัง หาก size ของ deque เป็น 0 จะเกิด error
คำอธิบาย เป็นการหาค่าที่อยู่ด้านปลายของ deque ใช้เวลา
พารามิเตอร์ ไม่มี
คืนค่า ข้อมูลชนิด T ที่อยู่ด้านปลายของ deque
ฟังก์ชั่นต้นแบบ T back();
ข้อควรระวัง หาก size ของ deque เป็น 0 จะเกิด error
คำอธิบาย เป็นการหาว่าขณะนี้ deque มีขนาดเท่าไหร่ ใช้เวลา
พารามิเตอร์ ไม่มี
คืนค่า จำนวนเต็ม บอกถึงขนาดของ deque
ฟังก์ชั่นต้นแบบ int size();
ข้อควรระวัง ไม่มี
คำอธิบาย เป็นการหาว่าขณะนี้ deque ว่างหรือไม่ ใช้เวลา
พารามิเตอร์ ไม่มี
คืนค่า
  • ค่า true เมื่อ deque ว่าง (ขนาดเป็น 0)
  • ค่า false เมื่อ deque ไม่ว่าง (ขนาดมากกว่า 0)
ฟังก์ชั่นต้นแบบ bool empty();
ข้อควรระวัง ไม่มี
คำอธิบาย เป็นการหาค่าของข้อมูลช่องที่ต้องการแบบ random access ซึ่งใช้เวลา O(1)

ตัวอย่างการใช้งาน ดูที่นี่

พารามิเตอร์ มีเพียงตัวเดียวคือ จำนวนเต็มในช่วง แสดงถึงช่องที่ต้องการหาค่า
คืนค่า ข้อมูลชนิด T ที่ต้องการหาค่า
ฟังก์ชั่นต้นแบบ T operator[](int);
ข้อควรระวัง ไม่มี

ตัวอย่างโค้ด

[แก้ไข | แก้ไขต้นฉบับ]
#include <cstdio>
#include <deque>

using namespace std;

struct ST{
    int a,b;
};

int main(){
    deque <int> Q;                     // []
    Q.push_back(13);                   // [13]
    Q.push_back(12);                   // [13,12]
    Q.pop_front();                     // [12]
    Q.push_front(11);                  // [11,12]
    Q.pop_back();                      // [11]
    Q.push_back(5);                    // [11,5]
    printf("%d", Q.back());            // => 5
    printf("%d", Q.front());           // => 11
    for(int i = 0; i < 4; i++)
        Q.push_back(i);
                                       // [11,5,0,1,2,3]
    Q.push_front(-1);                  // [-1,11,5,0,1,2,3]
    for(int i = 0; i < Q.size(); i++)
        printf("%d ", Q[i]);           // => -1 11 5 0 1 2 3
    while(not Q.empty()) Q.pop_back(); // []
    Q.pop_back()                       // => Error
    Q.pop_front()                      // => Error
    Q.front()                          // => Error
    Q.back()                           // => Error
                                       
    ST tmp;                            
    deque <ST> T;                      // []
    tmp.a = 5;                         
    tmp.b = 3;                         
    T.push_back(tmp);                  // [(5,3)]
    printf("%d\n", T.front().b);       // => 3
    return 0;
}
พัฒนา 75% ตั้งแต่ 21 กุมภาพันธ์ 2556 stack
พัฒนา 75% ตั้งแต่ 21 กุมภาพันธ์ 2556 queue
พัฒนา 75% ตั้งแต่ 21 กุมภาพันธ์ 2556 priority_queue
พัฒนา 75% ตั้งแต่ 21 กุมภาพันธ์ 2556 deque
พัฒนา 75% ตั้งแต่ 21 กุมภาพันธ์ 2556 vector
พัฒนา 25% ตั้งแต่ 21 กุมภาพันธ์ 2556 map
พัฒนา 0% ตั้งแต่ 21 กุมภาพันธ์ 2556 set