Cài đặt Deque (Double Ended Queue) trong C++

Deque (Double Ended Queue) cho phép chèn/xóa ở cả hai đầu: front và rear.

Các thao tác chính

• insert_at_beg() – Chèn vào đầu.
• insert_at_end() – Chèn vào cuối.
• delete_fr_front() – Xóa từ đầu.
• delete_fr_rear() – Xóa từ cuối.

Ví dụ minh họa (menu-driven)

#include <iostream>
using namespace std;
#define SIZE 10

class Deque {
    int a[SIZE], f, r;
public:
    Deque() : f(-1), r(-1) {}
    void insert_at_beg(int x);
    void insert_at_end(int x);
    void delete_fr_front();
    void delete_fr_rear();
    void show();
};

void Deque::insert_at_end(int x) {
    if (r >= SIZE-1) { cout << "Overflow\n"; return; }
    if (f == -1) f = r = 0;
    else r++;
    a[r] = x; cout << "Da chen cuoi: " << x << endl;
}
void Deque::insert_at_beg(int x) {
    if (f == -1) { f = r = 0; a[r] = x; cout << "Da chen dau: " << x << endl; }
    else if (f > 0) { a[--f] = x; cout << "Da chen dau: " << x << endl; }
    else cout << "Overflow (khong the chen dau)\n";
}
void Deque::delete_fr_front() {
    if (f == -1) { cout << "Underflow\n"; return; }
    cout << "Da xoa dau: " << a[f] << endl;
    if (f == r) f = r = -1;
    else f++;
}
void Deque::delete_fr_rear() {
    if (f == -1) { cout << "Underflow\n"; return; }
    cout << "Da xoa cuoi: " << a[r] << endl;
    if (f == r) f = r = -1;
    else r--;
}
void Deque::show() {
    if (f == -1) { cout << "Deque rong\n"; return; }
    for (int i=f; i<=r; i++) cout << a[i] << ' ';
    cout << endl;
}

int main() {
    Deque d; int ch, x;
    do {
        cout << "\n1.Chen dau\n2.Chen cuoi\n3.Hien thi\n4.Xoa dau\n5.Xoa cuoi\n6.Thoat\nChon: ";
        cin >> ch;
        switch(ch) {
            case 1: cout << "Gia tri: "; cin >> x; d.insert_at_beg(x); break;
            case 2: cout << "Gia tri: "; cin >> x; d.insert_at_end(x); break;
            case 3: d.show(); break;
            case 4: d.delete_fr_front(); break;
            case 5: d.delete_fr_rear(); break;
            case 6: return 0;
            default: cout << "Lua chon khong hop le\n";
        }
    } while(true);
}

Kết quả (mẫu)

1.Chen dau
2.Chen cuoi
3.Hien thi
4.Xoa dau
5.Xoa cuoi
6.Thoat
Chon: 1
Gia tri: 7
Da chen dau: 7
...
Chon: 3
7 6 4
...