STL deque

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

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

การใช้งาน

ต้องเรียกใช้ header file "deque" และเรียกใช้ namespace std

#include <deque>
 
using namespace std;

การประกาศตัวแปร

ให้ T คือ datatype ใดๆ และ var คือชื่อตัวแปร มีรูปแบบการประกาศตัวแปร deque ดังนี้

deque <T> var;

method

push_back

คำอธิบาย เป็นการเพิ่มข้อมูลชนิด T ลงทางด้านปลายของ deque ใช้เวลา O$(1)$
parameter มีเพียงตัวเดียวคือข้อมูลชนิด T ที่ต้องการจะใส่ลง deque ทางด้านปลาย
return ไม่มี
prototype void push_back(T);

push_front

คำอธิบาย เป็นการเพิ่มข้อมูลชนิด T ลงทางด้านหน้าของ deque ใช้เวลา O$(1)$
parameter มีเพียงตัวเดียวคือข้อมูลชนิด T ที่ต้องการจะใส่ลง deque ทางด้านหน้า
return ไม่มี
prototype void push_front(T);

pop_back

คำอธิบาย เป็นการลบข้อมูลชนิด T ทางด้านปลายของ deque ใช้เวลา $O(1)$
ข้อควรระวัง : หาก size ของ deque เป็น 0 จะเกิด error
parameter ไม่มี
return ไม่มี
prototype void pop_back();

pop_front

คำอธิบาย เป็นการลบข้อมูลชนิด T ทางด้านหน้าของ deque ใช้เวลา $O(1)$
ข้อควรระวัง : หาก size ของ deque เป็น 0 จะเกิด error
parameter ไม่มี
return ไม่มี
prototype void pop_front();

front

คำอธิบาย เป็นการหาค่าที่อยู่ด้านหน้าของ deque ใช้เวลา $O(1)$
ข้อควรระวัง : หาก size ของ deque เป็น 0 จะเกิด error
parameter ไม่มี
return ข้อมูลชนิด T ที่อยู่ด้านหน้าของ deque
prototype T front();

back

คำอธิบาย เป็นการหาค่าที่อยู่ด้านปลายของ deque ใช้เวลา $O(1)$
ข้อควรระวัง : หาก size ของ deque เป็น 0 จะเกิด error
parameter ไม่มี
return ข้อมูลชนิด T ที่อยู่ด้านปลายของ deque
prototype T back();

size

คำอธิบาย เป็นการหาว่าขณะนี้ deque มีขนาดเท่าไหร่ ใช้เวลา $O(1)$
parameter ไม่มี
return จำนวนเต็ม บอกถึงขนาดของ deque
prototype int size();

empty

คำอธิบาย เป็นการหาว่าขณะนี้ deque ว่างหรือไม่ ใช้เวลา $O(1)$
parameter ไม่มี
return ค่า true เมื่อ deque ว่าง (ขนาดเป็น 0)
ค่า false เมื่อ deque ไม่ว่าง (ขนาดมากกว่า 0)
prototype bool empty();

operator

[]

คำอธิบาย เป็นการหาค่าของข้อมูลช่องที่ต้องการแบบ random access ซึ่งใช้เวลา O(1)
ตัวอย่างการใช้งาน ดูที่ code STL deque
operand มีเพียงตัวเดียวคือ จำนวนเต็มในช่วง [0,size) แสดงถึงช่องที่ต้องการหาค่า
return ข้อมูลชนิด T ที่ต้องการหาค่า
prototype T operator[](int);

code STL deque

#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(!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;
}
stl
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License