您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

雙端隊列（Deque）原理與 C++ 循環數組實現詳解

編輯：C++ 入門

什麼是雙端隊列？

雙端隊列（Deque，Double-Ended Queue）是一種特殊的隊列，允許在兩端進行插入（入隊）和刪除（出隊）操作。相對於普通隊列只能「尾進頭出」，雙端隊列提供了更靈活的數據操作方式。

核心操作

push_front / push_back：左右兩端插入元素
pop_front / pop_back：左右兩端移除元素
front / back：訪問兩端元素
empty / full / size：狀態查詢

循環數組實現策略

為了提高空間利用率，採用「首尾相連」的循環數組結構：

left 指向左端第一個有效元素
right 指向右端下一個可插入位置
隊空條件：left == right
隊滿條件：(left - 1 + MAX) % MAX == right 或 (right - left + MAX) % MAX == MAX - 1

完整 C++ 類實現

#include <iostream>
#include <iomanip>
using namespace std;

const int MAX = 10;
typedef int ElemType;

class Deque {
private:
    int size;           // 當前元素個數
    ElemType *base;     // 數組基址
    int left, right;    // 左端、右端指針
    
public:
    Deque() : base(new ElemType[MAX]), left(0), right(0), size(0) {}
    ~Deque() { delete[] base; }
    
    int getSize() const { return size; }
    bool empty() const { return left == right; }
    bool full() const { return (left - 1 + MAX) % MAX == right; }
    
    // 獲取指定端元素（0=左，1=右）
    bool topAt(ElemType& data, int end) {
        if (empty()) return false;
        if (end == 0) data = base[left];
        else data = base[(right - 1 + MAX) % MAX];
        return true;
    }
    
    // 指定端插入
    bool pushAt(ElemType data, int end) {
        if (full()) return false;
        if (end == 0) {
            left = (left - 1 + MAX) % MAX;
            base[left] = data;
        } else {
            base[right] = data;
            right = (right + 1) % MAX;
        }
        ++size;
        return true;
    }
    
    // 指定端刪除
    bool popAt(int end) {
        if (empty()) return false;
        if (end == 0) left = (left + 1) % MAX;
        else right = (right - 1 + MAX) % MAX;
        --size;
        return true;
    }
    
    // 從指定端遍歷打印
    void print(int end) const {
        if (empty()) { cout << "空隊列，無法遍歷！" << endl; return; }
        if (end == 0) {
            for (int i = left; i != right; i = (i + 1) % MAX)
                cout << setw(4) << base[i];
        } else {
            for (int i = right; i != left; ) {
                i = (i - 1 + MAX) % MAX;
                cout << setw(4) << base[i];
            }
        }
        cout << endl;
    }
    
    void clear() { left = right = 0; size = 0; }
};

主程序測試

void check(int& end) {
    while (cin >> end && !(end == 0 || end == 1))
        cout << "端號不對，重新輸入：";
}

void input(Deque& deque) {
    int end; cout << "在指定端入隊，0左端，1右端："; check(end);
    ElemType data; cout << "輸入數據，輸入0結束" << endl;
    while (cin >> data && data) deque.pushAt(data, end);
}

void traverse(Deque& deque) {
    int end; cout << "從指定端遍歷："; check(end);
    deque.print(end);
}

int main() {
    cout << "******雙端隊列演練******" << endl;
    Deque deque;
    cout << "新建雙端隊列" << endl;
    cout << "隊列是否為空：" << (deque.empty() ? "Yes!" : "No!") << endl;
    
    input(deque); traverse(deque);
    input(deque); traverse(deque);
    
    ElemType data; int end;
    cout << "獲取指定端的頭元素："; check(end);
    deque.topAt(data, end) ? cout << data << endl : cout << "隊空！" << endl;
    
    cout << "刪除指定端的頭元素："; check(end);
    deque.popAt(end) ? cout << "刪除成功" << endl : cout << "隊空！" << endl;
    traverse(deque);
    
    cout << "清空隊列，隊列是否為空：";
    deque.clear();
    cout << (deque.empty() ? "Yes!" : "No!") << endl;
    
    system("pause"); return 0;
}